Algoritm tushunchasi

17 Saralash algoritmlari. Pufaksimon saralash (Bubble sort)

Pufakchali saralash (Bubble sort) algoritmining C++ dastur
kodi. Ushbu algoritm ta’limiy hisoblanadi va samaradorligi pastligi
sababli amalda deyarli hech qachon qoʻllanilmaydi: u kichik elementlar
(ular "toshbaqalar" deb nomlanadi) massiv oxirida joylashgan testlarda
sekin ishlaydi. Biroq, koʻplab boshqa usullar bunga asoslangan,
masalan, Sheyker saralash va taroqsimon saralashlari.
Vaqt boʻyicha murakkabligi:
Eng yomon baho: O(n2)
Oʻrtacha baho: O(n2)
Eng yaxshi baho: O(n)
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n-1; i++)
{
swapped = false;
for (j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
swapped = true;
}
}
if (swapped == false)
break;
}
}
18 Saralash algoritmlari. Sheyker saralashi
Sheyker saralashi. Sheyker (kokteyl) saralashi - bu Pufakchali
(Bubble Sort) algoritmining varianti. Bubble sort algoritmi har doim
chapdan elementlarni aylanib oʻtadi va birinchi iteratsiyada eng katta
elementni toʻgʻri holatiga, ikkinchisida esa ikkinchi takrorlashda va
hokazo. Kokteyl saralash berilgan massiv orqali har ikki yoʻnalishda
ham muqobil ravishda harakatlanadi.
Algoritmning har bir takrorlanishi 2 bosqichga boʻlinadi:
Birinchi bosqich massivni xuddi Bubble Sort singari chapdan
oʻngga aylantiradi. Sikl davomida qoʻshni elementlar taqqoslanadi va
agar chapdagi qiymat oʻngdagi qiymatdan katta boʻlsa, qiymatlar
almashtiriladi. Birinchi takrorlash oxirida eng katta son massivning
oxirida boʻladi.
Ikkinchi bosqich massivni qarama-qarshi yoʻnalishda aylantiradi bu eng soʻnggi saralangan elementdan oldin va massivning boshiga
qaytish. Bu yerda qoʻshni elementlar taqqoslanadi va agar kerak boʻlsa
almashtiriladi.
void CocktailSort(int a[], int n)
{
bool swapped = true;
int start = 0;
int end = n - 1;
while (swapped)
{
swapped = false;
for (int i = start; i < end; ++i)
{
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
swapped = true;
}
}
58
if (!swapped)
break;
swapped = false;
--end;
for (int i = end - 1; i >= start; --i)
{
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
swapped = true;
}
}
++start;
} }
Vaqt boʻyicha murakkabligi:
Eng yomon baho: O(n2)
Oʻrtacha baho: O(n2)
Eng yaxshi baho: O(n)
19 Saralash algoritmlari. Taroqsimon saralash (Comb sort)
Taroqsimon saralash. Comb sort. Taroqsimon saralash –
“Pufakchali” saralashning yaxshiroq varianti. Uning gʻoyasi algoritmni
sekinlashtiradigan qator oxiridagi kichik qiymatlarga ega elementlarni
"yoʻq qilish". Agar pufakchali va Sheyker saralashlarida, massiv boʻylab
takrorlanganda qoʻshni elementlar taqqoslansa, u holda "tarash" paytida
avval taqqoslangan qiymatlar orasida yetarlicha katta masofa olinadi,
soʻngra u minimal darajaga tushadi. astlabki boʻshliq tasodifiy tanlanmasligi kerak, lekin maxsus qiymatni hisobga olgan holda - kamaytirish qiymati, uning optimal qiymati 1,247 ga teng. Dastlab elementlar orasidagi masofa massivning
kattaligiga 1,247 ga teng boʻladi; har bir keyingi bosqichda masofa yana
qisqartirish koeffitsiyentiga boʻlinadi - va shunga oʻxshash jarayon
algoritm oxirigacha davom etadi.
Vaqt boʻyicha murakkabligi:
Eng yomon baho: O(n2)
Oʻrtacha baho: Ω(n2/2p), p – inkrementlar miqdori
Eng yaxshi baho: O(n logn)
void combSort(int a[], int n)
{
int k = n;
bool swapped = true;
while (k != 1 || swapped == true)
{
k = getNextk(gap);
swapped = false;
for (int i=0; i
{
if (a[i] > a[i+k])
{
swap(a[i], a[i+k]);
swapped = true;
}
}
}
}
20 Saralash algoritmlari. Tanlash bo’yicha saralash (Selection sort)
Tanlash boʻyicha saralash (Selection sort). Birinchidan, siz
massivning kichik qismini koʻrib chiqishingiz va undagi maksimal (yoki
minimal) miqdorni topishingiz kerak. Keyin tanlangan qiymat birinchi
saralanmagan elementning qiymati bilan almashtiriladi. Ushbu qadam
massivning saralanmagan ichki qismlari tugamaguncha takrorlanishi
kerak.
Vaqt boʻyicha murakkabligi:
Eng yomon baho: O(n2)
Oʻrtacha baho: O(n2),
Eng yaxshi baho: O(n2)
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
for (i = 0; i < n-1; i++)
61
{
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]);
}
}
Ushbu algoritmlarning elementlari soni bir xil boʻlgan holatda
qanday vaqt ichida bajarilishi va sarflangan xotira hajmi haqidagi
qiyosiy jadval quyida berilgan.
Sinov oʻtkaziladigan kompyuter quyidagi xususiyatlarga ega: AMD
A6-3400M 4x1.4 GHz, 8 Gb operativ xotira, Windows 10 x64 build
10586.36.
21 Saralash algoritmlari. Birlashtirib saralash algoritmi (Merge sort). “Bo’lib tashla va hukmronlik qil” strategiyasi
Merge sort algoritmi. Birlashtirib saralash (Merge sort) –
tartiblashning tezkor bajariladigan algoritmlaridan biri. Ushbu tartiblash
“boʻlib tashla va hukmronlik qil” prinsipining yaxshi namunasidir.
Birinchidan, vazifa bir nechta kichik topshiriqlarga boʻlinadi. Keyin
ushbu vazifalar rekursiv chaqiruv yordamida yoki toʻgʻridan-toʻgʻri
ularning hajmi yetarlicha kichik boʻlsa hal qilinadi. Nihoyat, ularning
yechimlari birlashtirilib, asl muammoning echimi olinadi.
Algoritmning bajarilishi. Saralash muammosini hal qilish uchun
uch bosqich quyidagicha boʻladi:
1. Saralanadigan massiv taxminan bir xil oʻlchamdagi ikki qismga
boʻlinadi;
2. Olingan qismlarning har biri alohida saralanadi (masalan, xuddi
shu algoritm boʻyicha saralanadi);
3. Yarim kattalikdagi ikkita saralangan massivlar birlashtiriladi.
Bu eng mashhur saralash algoritmlaridan biri boʻlib, rekursiv
algoritmlarni yaratishda ishonchni rivojlantirishning ajoyib usuli
hisoblanadi.
“Boʻlib tashla va hukmronlik qil” strategiyasi. “Boʻlib tashla va
hukmronlik qil” strategiyasi yordamida muammoni qismiy jarayonlarga
ajratamiz. Har bir kichik topshiriq uchun yechimga ega boʻlsak, pastki
vazifalarni yechish uchun pastki vazifalardan olingan natijalarni
"birlashtiramiz".
Aytaylik, biz A massivni saralashni xohladik. Kichik vazifa bu p
indeksidan boshlanib, r indeksida tugagan, A [p..r] bilan belgilangan
kichik qismini ajratishdir.
“Boʻlib tashlash”. Agar q qiymati p va r orasida boʻlsa, biz A
[p..r] massivni ikkita A [p..q] va A [q + 1, r] kichik massivlarga
boʻlishimiz mumkin.
“Hukmronlik qilish”. “Hukmronlik qilish” bosqichida biz ikkala
A [p..q] va A [q + 1, r] kichik massivlarni saralashga harakat qilamiz.
Agar hali ham boshlangʻich darajaga yetib bormagan boʻlsak, yana
ikkala quyi qismni ajratib, ularni saralashga harakat qilamiz.
64
Birlashtirish bosqichi. Birlashtirish bosqichi asosiy pogʻonaga
yetib borganida va biz A [p..r] massivi uchun ikkita tartiblangan A [p..q]
va A [q + 1, r] kichik massivlarni olsak, natijalarni A [p..r] massiviga
birlashtiramiz. Bu ikkita tartiblangan A [p..q] va A [q + 1, r]
massivlarning birlashmasidir