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(n
2
)
Oʻrtacha baho: O(n
2
)
Eng yaxshi baho: O(n)
3. 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.
Dastlabki 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.
59
Vaqt boʻyicha murakkabligi:
Eng yomon baho: O(n
2
)
Oʻrtacha baho:
(n
2
/2
p
), p – inkrementlar miqdori
Eng yaxshi baho: O(n logn)
