9
Yuqorida keltirilgan uchala usulda ham almashtirishlar soni deyarli bir hil
bo’ladi.
To’g’ridan-to’g’ri qo’shish usuli bilan saralash
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.
