To’g’ridan-to’g’ri almashtirish usuli bilan saralash (pufaksimon)

11
Pufaksimon usulni yaxshilangan usuli bu sheyker saralash usuli bo’lib, har bir 
o’tishdan keyin sikl ichida yo’nalish o’zgartiriladi. 
Algoritm samaradorligi: 
taqqoslashlar soni M = 
n n
n
2 2
4
2
 
, 
almashtirishlar soni C
max
= 3
n
2
4
. 
Quyida biz ushbu saralash algoritmlaridan bir nechtasini ko`rib o`tamiz, 
shuningdek quick sort saralash algoritmiga keying rejamizda alohida to`xtalib 
o`tamiz va tushunishga harakat qilamiz.
Bubble sort saralash algoritmi qanday usulda saralash? Ushbu so`z pufakcha 
usulida saralash degan ma’noni anglatadi. Bu saralash usulida massiv 
elementlarining ikki qo`shni elementlari taqqoslanadi va agarda noto`g`ri joylashgan 
bo`lsa ularnung o`rinlari almashtiriladi. Umumiy 
n-1 
marta ushbu jarayon bajariladi. 
Har safar ikkita qo`shni element taqqoslanadi. Yuqoridagi jarayonda har bir element 
o`z o`rniga siljib boradi xuddi suvdagi pufakchaga o`xshab. Shu sababli ham uning 
nomi pufakcha usulida saralash deb nomlanadi. Bu algoritmning asosiy g‘oyasini 
yozish uchun tartiblanishi kerak bo‘lgan yozuvlar vertikal joylashgan massivda 
saqlanadi deb faraz qilamiz. Kalit maydonning kichik qiymatli yozuvlari «yengil» 

12
va shuning uchun pufakcha kabi ular yuqoriga «suzib chiqadi». Massiv bo‘ylab 
birinchi o‘tishda massivning birinchi yozuvi olinadi va uning kaliti navbatma-navbat 
keyingi yozuvlarning kalitlari bilan solishtirib boriladi. Agar nisbatan «og‘ir» kalitli 
yozuvlar uchrasa, u holda bu yozuvlar joyini almashtiradi. Nisbatan «yengil» 
yozuvlar uchraganda bu yozuv taqqoslash uchun etolon bo‘ladi va keyingi barcha 
yozuvlar shu kalit bilan solishtiriladi. Natijada eng kichik qiymatli kalit massivning 
eng yuqorisiga chiqadi. Massiv bo‘ylab ikkinchi o‘tishda massivning massivni 
birinchi o‘tishda topilgan yozuvdan keyin joylashgan og‘irligi bo‘yicha ikkinchi 
kalit olinadi. Massiv bo‘ylab ikkinchi va keyingi o‘tishlarda oldingi o‘tishlarda 
topilgan yozuvlarni ko‘rib chiqish shart emas, chunki ular qolgan yozuvlarga 
qaraganda kichik kalitlarga ega. 
Quyida bubble sort algoritmining 
c++ 
tilidagi dasturini keltiramiz: 
#include  
using namespace std; 
int main(){ int a[100], i, j, n, t; 
cin>>n; 
for(i=0; icin>>a[i]; 
for(i=n; i>=1; i--) 
{ for(j=0; jif(a[j]>a[j+1]) 
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } 
for(i=0; icout<return 0; } 
Yana bir saralash usuli insertion sort bo`lib, u ham massiv elementlarini 
saralashda qulay usullardan biri hisoblanadi. Insertion sort saralash algoritmida 
asosan boshidan boshlab 2 ta elementini keyin 3 ta so`ngra 4 ta va hakozo 
n
ta 
elementni tartiblanadi. (1) - qadamda dastlabki 2 ta element tartiblanganda faqat 2 
ta element, (2) - qadamda 3 ta element tartiblanganda esa 3 - element dastlabki 2 tasi 

13
bilan, (3) - qadamda 4 ta element tartiblanganda 4 - element dastlabki 3 tasi bilan va 
hakozo (

Download 0,98 Mb.