8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja

Havo sharcha kabi saralash (Bubble sort). Massivda chapdan o‘ngga qarab amal bajariladi. Agar joriy element keyingisidan katta bo‘lsa, ularni almashtiramiz. Buni massiv tartiblanmaguncha bajaramiz. Eʻtibor bering, birinchi iterasiyadan keyin eng katta element massivning oxirida, to‘g‘ri joylashagan bo‘ladi. Ikkita iterasiyadan keyin ikkinchi eng katta element to‘g‘ri joylashgan bo‘ladi va hokazo. Ravshanki, n ta iterasiyadan ko‘p bo‘lmagandan keyin massiv tartiblangan bo‘ladi. Shunday qilib, eng yomon va o‘rtacha holatda murakkabligi O(n²), eng yaxshi holatda esa O(n) bo‘ladi.
Shaker saralash (Shaker sort, bundan tashqari, aralashgan saralash va koktel saralash sifatida tanilgan). Havo sharcha saralash oxirida kichik elementlar joylashtirilgan testlarda sekin ishlaydi (baʻzan "tashboqa" deb ataladi). Bu element algoritmning har bir qadamida chap tomonga faqat bitta pozitsiyaga harakat qiladi. Shuning uchun nafaqat chapdan o‘ngga, balki o‘ngdan chapga ham o‘tadi. Massivning tartiblanmagan qismini aniqlash uchun ikkita begin va end ko‘rsatikichni qo‘llab quvvatlaydi. Keyingi iterasiyada endga etganimizda undan birini ayiramiz va o‘ngdan chapga ko‘chamiz. Xuddi shunday, beginga etganimizda unga birini qo‘shamiz va chapdan o‘ngga ko‘chamiz . Algoritm havo sharcha saralash bilan bir xil murakkabligi bor, lekin real vaqtda yaxshi ishlaydi.
void shakersort(int* l, int* r) { int sz = r - l;
if (sz <= 1) return; bool b = true;
int* beg = l - 1; int* end = r - 1; while (b) {
b = false; beg++;
for (int* i = beg; i < end; i++) { if (*i > *(i + 1)) {
swap(*i, *(i + 1)); b = true;
}
}
if (!b) break;
end--;
for (int* i = end; i > beg; i--) { if (*i < *(i - 1)) {
swap(*i, *(i - 1)); b = true;
}}}}
Taroqsimon caralash (Comb sort). Shaker saralashning yana bir o‘zgartirilgani. "Toshbaqalar" dan qutulish uchun masofada turgan elementlarni qayta tashkil qilamiz. Keling, uni tuzatamiz va chapdan o‘ngga boramiz, bu masofada turgan elementlarni taqqoslaymiz, agar kerak bo‘lsa, ularni qayta tartibga solaylik. Shubhasiz, bu "toshbaqalar"ni tez qator boshiga olish imkonini beradi. Dastlab qator uzunligiga teng masofani olib, so‘ngra uni taxminan 1.247 ga teng bo‘lgan biror koeffitsientga bo‘lish maqbuldir. Masofa bir biriga teng bo‘lganda shaker saralash bajariladi. Eng yaxshisi, murakkabligi O(nlogn), eng yomoni, u O(n²). O‘rtacha murakkabligi nima uchun juda aniqmas, amalda O(nlogn) kabi ko‘rinadi.