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

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";