Murakkab saralash algoritmlari

---

Dasturlash 2
Mustaqil ish-6 
Guruh:921-22 
Rustamov Umidbek 
Murakkab saralash algoritmlari 
Saralashdan maqsad- tartiblangan to’plamda kerakli elementni topishni 
osonlashtirishdan iborat. 
Saralashning tadbiqi: 
Dasturlarni translyatsiya qlishda;
Malumotlar majmuasini tashqi xotirada tashkil qlishda;
Kutubxonalar,kataloglar,ma’lumotlar bazasini yaratishda va boshq. 
Masalan array
Array = [“abc”, ”aa”, “abbb”, “a” ] -dastlabki tartibsiz xolat 
Array = [“a”,”aa”, “abbb”, “abc”] -alifbo bo’yicha saralash 
Array = [“a”, “aa”, “abc”, “abbb”] -uzunlik bo’yicha saralash 
Saralash algoritmlari va murakkabligi. 
Avvalo, algoritmlarni tadqiq qilishga, ularni imkon qadar tez ishlashi uchun 
optimallashtirish muhimdir. Bu ustida ishlayotganda, turli saralash uchun 
samarali usullarni o‘ylab topish imkoniyatiga ega bo‘lishingiz mumkin. 
Ko‘p jihatdan, barcha saralash algoritmlarni o‘rganish va ularni sinash kerak. 
Agar dasturlashning o‘zi haqida gapiradigan bo‘lsak, ba’zan kutilmagan 
qiyinchiliklar paydo bo‘lishi mumkin (C++ optimizatori juda yaxshi). Biroq, qaysi 

---

testlarni va qanday miqdorda amalga oshirilishi kerakligini hal qilish qiyin emas. 
Men ko‘rsata olmaydigan yagona narsa-bu deyarli 150 GB vaznga ega 
qiymatlarni saralash bo‘ldi.
Asosiy saralash algoritmlari tavsifi va ularni amalga oshirish usullari. Saralashni 
qisqacha va aniq ta’riflashga va murakkabligini belgilashga harakat qilaman. 
Murakkab ma’lumotlar tuzilmalarni foydalanishda(daraxt saralash kabi) odatda 
xotira katta miqdorda sarflanadi va eng yomon holatda boshqa xil faqat 
yordamchi qator yaratish kerak bo‘ladi. Barqarorlik (stabillik) saralash 
tushunchasi ham mavjud. Demak, elementlarning nisbiy tartibi teng bo‘lganda 
o‘zgarmaydi. 
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(n2), eng yaxshi holatda esa O(n) bo‘ladi. 
Void bubblesort(int* l, int* r) { 
Int sz = r – l; 
If (sz <= 1) return; 
Bool b = true; 
While (b) { b = false; 
For (int* i = l; i + 1 < r; i++) { 
If (*i > *(i + 1)) { 
Swap(*i, *(i + 1)); 
B = true;} 
}
r--;} 

---

Taroqsimon saralash (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(n2). O‘rtacha murakkabligi 
nima uchun juda aniqmas, amalda O(nlogn) kabi ko‘rinadi. 
Void combsort(int* l, int* r) { 
Int sz = r – l; 
If (sz <= 1) return; 
Double k = 1.2473309; 
Int step = sz – 1; 
While (step > 1) { 
For (int* i = l; i + step < r; i++) { 
If (*i > *(i + step)) 
Swap(*i, *(i + step)); 
} 
Step /= k; 
} 
Bool b = true; 
While (b) { 
B = false; for (int* i = l; i + 1 < r; i++) { 
If (*i > *(i + 1)) { 
Swap(*i, *(i + 1)); 
B = true;}}}} 

---

Misol: 
#include  
Using namespace std; 
Void bubbleSort(int arr[], int n) { 
For (int i = 0; i < n-1; i++) { 
For (int j = 0; j < n-i-1; j++) { 
If (arr[j] > arr[j+1]) { 
Int temp = arr[j]; 
Arr[j] = arr[j+1]; 
Arr[j+1] = temp; 
} 
} 
} 
} 
Int main() { 
Int arr[] = {5, 1, 4, 2, 8}; 
Int n = sizeof(arr)/sizeof(arr[0]); 
bubbleSort(arr, n); 
cout << “Sorted array: “; 
for (int i = 0; i < n; i++) { 
cout << arr[i] << “ “; 
} 
Cout << endl; 
Return 0; 
} 

---

Bu misol dastlabki tartibsiz massivni olishni va “bubbleSort” funksiyasi orqali 
o‘sishini namoyish etadi. “bubbleSort” funksiyasi massivni to‘g‘ri tartiblash 
uchun Bubble Sort algoritmini qo‘llaydi. 
Misoldagi “arr” massivi tartibsiz bo‘lib, {5, 1, 4, 2, 8} ko‘rinishida berilgan. “n” 
o‘zgaruvchi “arr” massivining uzunligini anglatadi. 
Bubble Sort algoritmi ikkita qadamdan iborat. Birinchi qadam, massivni 
o‘ngdan chapga yo‘nalishda o‘ta ota saralashdir. Ikkinchi qadam, massivni 
saralashga olib keluvchi algoritmdir. Bu misol dastlabki qadamlarni birma-bir 
bajargan har bir ichki “for” tsikliga ega. Ikkinchi qadamlar esa, massivni to‘g‘ri 
tartibga keltirish uchun “if” ko‘rsatmasi yordamida amalga oshiriladi. 
Natijada, “Sorted array:” satrida massiv to‘g‘ri tartibda ko‘rsatiladi.