“Dasturiy injiniring” fakulteti “MA‟lumotlar tuzilmasi va algoritmlar”

key=(+)/2, i=, 
j=. 

---

117 
6.3-rasm. Quicksort algoritmida o„rinlashtirish 
3.
Chapdagi i-elementni 
key
bilan solishtiramiz. Agar 
key
kichik bo„lsa, 
keyingi qadamga o„tamiz. Aks holda 
i++
va shu qadamni takrorlaymiz. 
4.
O„ngdagi 
j
-element bilan 
key
solishtiriladi. Agar 
key
katta bo„lsa, keyingi 
qadamga o„tamiz, aks holda 
j--
va shu qadamni takrorlaymiz. 
5.
i-
va 
j-
elementlarning o„rni almashtiriladi. Agar 
i<=j
bo„lsa, 3-qadamga 
o„tiladi. 
Birinchi o„tishdan keyin tanlangan element o„zining joyiga kelib joylashadi. 
6.
Endi shu ko„rilayotgan oraliqda 
key
kalitning chap tomonida elementlar 
mavjud bo„lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya‟ni ko„riladigan 
oraliq 
0
dan 
key-1
gacha deb belgilanadi va 2-qadamga o„tiladi. Aks holda keyingi 
qadamga o„tiladi. 
7.
Endi shu ko„rilayotgan oraliqda 
key
kalitning o„ng tomonida elementlar 
mavjud bo„lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya‟ni ko„riladigan 
oraliq 
key+1
dan 
n-1
gacha deb belgilanadi va 2-qadamga o„tiladi. Aks holda 
algoritm tugaydi. 
Shu algoritmga misol ko„rib chiqamiz.
Misol: Talabalar ism-sharifi va tartib raqamidan iborat jadvalni quicksort 
algoritmi bilan saralang va nechta o„rinlashtirish amalga oshirilganini aniqlang. 
Dastur kodi 
#include  
#include  
using namespace std; 
struct table{ 
int t; 
string FIO; 

---

118 
};
int q=0; 
void qs(table *a,int first,int last){ 
int i = first, j = last;table x =a[(first + last) / 2]; 
do { 
while (a[i].FIO < x.FIO) i++; 
while (a[j].FIO > x.FIO) j--; 
if(i <= j) { 
if (i < j){ swap(a[i], a[j]);q++;} 
i++; 
j--; 
} 
} while (i <= j); 
if (i < last) 
qs(a,i,last); 
if (first < j) 
qs(a,first,j); 
} 
int main(int args, char *argv[]) 
{ int n;cout<<"n=";cin>>n; 
table talaba[n]; 
for(int i=0;i
talaba[i].t=i+1; 
cin>>talaba[i].FIO; 
} 
qs(talaba,0,n-1); 
for(int i=0;i
cout<
cout<<"quicksort algoritmi "<
saraladi\n"; 

---

119 
system("PAUSE"); 
} 
Dastur natijasi: 
talabalar sonini kiriting=5 
5 ta talabalar FIO sini kiriting 
Farhod
Asror 
Sobir
Bobur
Vali
| 2 | Asror | 
| 4 | Bobur | 
| 1 | Farhod | 
| 3 | Sobir | 
| 5 | Vali | 
bu algoritm jadvalni 3 ta o‘rinlashtirishda saraladi 
Ishni bajarishga namuna 
Masalaning qo„yilishi – tabalarning ism, familiyalarini optimallashtirilgan 
pufaksimon usuli bilan tartibga keltirish dasturini tuzamiz va saralash nechta o„rin 
almashtirish bilan amalga oshirilganini aniqlaymiz.