void CocktailSort(int a[], int n)

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)

Download 4,61 Mb.