7
Bunday usul karta o’yinida keng qo’llaniladi. Elementlar (kartlar) hayolan “tayyor”
a(1),...,a(i-1) va boshlang’ich ketma-ketliklarga bo’linadi. Har bir qadamda (i=2 dan boshlanib,
har bir qadamda bir birlikka oshirib boriladi) boshlang’ich ketma-ketlikdan i-chi element ajratib
olinib tayyor ketma-ketlikning kerakli joyiga qo’shiladi.
Taklif qilinayotgan usulni quyidagi misolda ko’rib chiqamiz.
Faraz
qilaylik, kalit qiymati 4, 5, 3, 8, 1, 7 bo’lgan elementlar berilgan bo’lsin.
Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo’ladi. Taqqoslashlar
amalga oshirish mobaynida, navbatdagi a(j) element bilan solishtiriladi, keyin esa x bo’sh joyga
qo’yiladi yoki a( j ) o’nga suriladi va jarayon chapga “ketadi”. Shuni e’tiborga
olish lozimki,
saralash jarayoni quyidagi shartlarni birortasi bajarilganda yakunlanadi:
x elementi kalitidan kichik
kalitli a(j) element topildi.
tayyor ketma-ketlikning chap tomoni oxiriga yetib borildi.
algoritm samaradorligi
Faraz qilaylik,
taqqoslashlar soni S, o’rinlashtirishlar soni M bo’lsin.
Agar massiv
elementlari kamayish tartibida bo’lsa, u holda taqqqoslashlar soni eng katta bo’lib, u
2
1
max
n
n
C
ga teng bo’ladi, ya’ni
2
n
O
. O’rinlashtirishlar soni esa
)
1
(
3
max
max
n
C
M
ga teng
bo’ladi, ya’ni
2
n
O
. Agar berilgan massiv o’sish tartibida saralangan bo’lsa,
u holda
taqqoslashlar va o’rinlashtirishlar soni eng kichik bo’ladi, ya’ni
1
min
n
C
,
)
1
(
3
min
n
M
.
