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 (
