Saralash (bubble, selection, insertion)

Massivdagi elementlarni ma'lum tartibda joylashtirishga saralash (sorting) deyiladi. Bu, ko'rinishidan, oddiy vazifa — lekin dasturlash va algoritmlar dunyosida saralash juda chuqur o'rganilgan mavzu.

Nima uchun saralash bu qadar muhim? Birinchidan, saralangan massivda binary search ishlatish mumkin — bu qidiruvni O(n) dan O(log n) ga tushiradi. Ikkinchidan, ko'plab algoritmlar kirishda saralangan massivni talab qiladi. Uchinchidan, foydalanuvchiga ko'rsatiladigan ro'yxatlar — mahsulotlar, natijalar, hodisalar — odatda saralanib ko'rsatiladi. Saralash barchaning tagida turadi.

Bu qismda uchta asosiy algoritmni ko'rib chiqamiz: bubble sort, selection sort va insertion sort. Ularning barchasi O(n²) vaqt murakkabligiga ega va katta massivlar uchun samarali emas. Lekin ularni o'rganish muhim — har biri alohida g'oyani ko'rsatadi, ushbu g'oyalar keyingi, tezroq algoritmlarning asosi bo'lib xizmat qiladi.

Saralashdan oldin: muhim tushunchalar

Qaysi tartibda?

Ko'pincha sonlar o'sish tartibida (kichikdan kattaga) saralanadi. Lekin saralash har doim shunday bo'lavermaydi: kamayish tartibida, alifbo tartibida, sana bo'yicha, narx bo'yicha — taqqoslash mezoni turlicha bo'lishi mumkin. Algoritm logikasi o'zgarmaydi; faqat ikkita element nimaga ko'ra taqqoslanishi o'zgaradi.

Barqaror saralash nima?

Massivda bir xil qiymatlardagi elementlar bo'lsa, ularning saralashdan keyingi tartibi ham muhim bo'lishi mumkin. Barqaror (stable) saralash bir xil qiymatli elementlarning eski tartibini saqlaydi. Barqaror bo'lmagan saralashda ularning tartibi o'zgarishi mumkin.

Masalan, talabalar o'rtacha ball bo'yicha saralangan. Ikkita talabaning o'rtacha bali bir xil. Barqaror saralash ularning alifbo tartibini (oldingi tartibni) saqlaydi. Barqaror bo'lmagan saralash esa ularni tasodifiy joylashtirishi mumkin.

Bu ko'p holatlarda muhim emas, lekin ayrim tizimlarda — masalan, amalda ikkita mezon bo'yicha saralash kerak bo'lganda — muhim ahamiyat kasb etadi.

Joyida saralash nima?

Joyida (in-place) saralash deyilganda massiv elementlari yangi, qo'shimcha massiv yaratmasdan qayta joylashtiriladi. Faqat bir-ikki ta o'zgaruvchi uchun qo'shimcha xotira sarflanadi. Bu xotira murakkabligini O(1) darajada ushlab turadi. Quyidagi uchta algoritm ham joyida saralaydi.

Bubble sort — ko'piklar ko'tariladi

Bubble sort o'zbek tiliga "ko'pik saralash" yoki "pufakchali saralash" deb tarjima qilish mumkin. Nom tasodifiy emas.

Suv idishini tasavvur qiling. Ostiga vazn qo'yib, keyin qo'yib yuborsangiz, u yuqoriga ko'tariladi. Bubble sort ham elementlarni xuddi shunday harakatlantiradi: katta qiymatlar har bosqichda biroz "yuqoriga" — ya'ni massivning oxiriga tomon — surilib boradi.

Algoritm

Massivda ketma-ket kelgan juft elementlarni taqqoslaydi. Chap element kattaroq bo'lsa, ularni joylashtiradi. Buni massivning oxirigacha bajaradi. Birinchi "o'tishdan" (pass) keyin eng katta element o'z joyiga — oxirga — yetib boradi. Ikkinchi o'tishda ikkinchi eng katta element o'z joyiga tushadi. Va hokazo.

FUNCTION bubble_sort(array)
    n = array uzunligi

    FOR i = 0 DAN n - 1 GACHA
        FOR j = 0 DAN n - i - 2 GACHA
            IF array[j] > array[j + 1]
                array[j] VA array[j + 1] JOYINI ALMASHTIR

    RETURN array

Nima uchun ichki takrorlash n - i - 2 gacha boradi? Chunki har bir o'tishdan keyin oxirdan i ta element allaqachon o'z joyida turadi — ularni yana tekshirishning hojati yo'q.

Bosqichma-bosqich tahlil

[5, 3, 8, 1] massivini saralaylik.

1-o'tish:

[5, 3, 8, 1]
 ↑  ↑
 5 > 3? Ha → almashtiriladi

[3, 5, 8, 1]
    ↑  ↑
    5 < 8? Yo'q → qoladi

[3, 5, 8, 1]
       ↑  ↑
       8 > 1? Ha → almashtiriladi

[3, 5, 1, 8]  ← 8 o'z joyiga yetdi

2-o'tish:

[3, 5, 1, 8]
 ↑  ↑
 3 < 5? Yo'q → qoladi

[3, 5, 1, 8]
    ↑  ↑
    5 > 1? Ha → almashtiriladi

[3, 1, 5, 8]  ← 5 o'z joyiga yetdi

3-o'tish:

[3, 1, 5, 8]
 ↑  ↑
 3 > 1? Ha → almashtiriladi

[1, 3, 5, 8]  ← saralandi

Optimizatsiya: erta to'xtash

Yuqoridagi algoritmda massiv to'liq saralangan bo'lsa ham takrorlash davom etadi. Bitta o'tishda hech qanday almashtirish bo'lmasa, massiv allaqachon saralangan demakdir — keyingi o'tishlarning hojati yo'q.

FUNCTION bubble_sort_optimized(array)
    n = array uzunligi

    FOR i = 0 DAN n - 1 GACHA
        almashtirildi = FALSE

        FOR j = 0 DAN n - i - 2 GACHA
            IF array[j] > array[j + 1]
                array[j] VA array[j + 1] JOYINI ALMASHTIR
                almashtirildi = TRUE

        IF almashtirildi = FALSE
            TO'XTAT

    RETURN array

Bu optimizatsiya eng yaxshi holat — allaqachon saralangan massiv — uchun murakkablikni O(n) ga tushiradi. Bitta o'tish bajariladi, almashtirish bo'lmaydi, algoritm to'xtaydi.

Bubble sortning murakkabligi

Holat	Vaqt murakkabligi	Izoh
Eng yaxshi (allaqachon saralangan)	`O(n)`	Faqat optimizatsiyalangan versiyada
O'rtacha	`O(n²)`	Tasodifiy joylashtirilgan massiv
Eng yomon (teskari saralangan)	`O(n²)`	Har bir element maksimal harakatlanyadi
Xotira murakkabligi	`O(1)`	Faqat bir nechta o'zgaruvchi ishlatiladi

Bubble sort barqaror: teng elementlarni almashtirmaydi, shuning uchun ularning tartibi saqlanadi.

Selection sort — eng kichikni tanlab olish

Selection sort ("tanlab olish saralash") boshqacha yo'l tutadi. U har safar massivning saralanmagan qismidan eng kichik elementni topadi va uni saralanmagan qismning boshiga joylashtiradi.

Fikran karta o'yini uchun kartalarni tartibga solayotganingizni tasavvur qiling. Qo'lingizdagi barcha kartalarni ko'rib, eng kichigini topasiz va uni chap tomonga o'tkizasiz. Keyin qolganlarning ichidan yana eng kichigini topasiz. Va hokazo. Aynan shu mantiq selection sort.

Algoritm

FUNCTION selection_sort(array)
    n = array uzunligi

    FOR i = 0 DAN n - 2 GACHA
        eng_kichik_index = i

        FOR j = i + 1 DAN n - 1 GACHA
            IF array[j] < array[eng_kichik_index]
                eng_kichik_index = j

        IF eng_kichik_index ≠ i
            array[i] VA array[eng_kichik_index] JOYINI ALMASHTIR

    RETURN array

Tashqi takrorlash har safar "saralanmagan qismning boshlanish nuqtasi" ini belgilaydi. Ichki takrorlash idan keyin eng kichik elementni qidiradi. Topilgandan keyin i-element bilan joyini almashtiradi.

Bosqichma-bosqich tahlil

[64, 25, 12, 22] massivini saralaylik.

i = 0:

[64, 25, 12, 22]
 ↑
 i = 0

Saralanmagan qismdan eng kichigini topamiz: 12 (index 2)
12 va 64 joyini almashtiramiz:

[12, 25, 64, 22]
 ✓

i = 1:

[12, 25, 64, 22]
     ↑
     i = 1

Saralanmagan qismdan eng kichigini topamiz: 22 (index 3)
22 va 25 joyini almashtiramiz:

[12, 22, 64, 25]
 ✓   ✓

i = 2:

[12, 22, 64, 25]
         ↑
         i = 2

Saralanmagan qismdan eng kichigini topamiz: 25 (index 3)
25 va 64 joyini almashtiramiz:

[12, 22, 25, 64]
 ✓   ✓   ✓   ✓  — saralandi

Selection sortning xususiyati: kamroq almashtirish

Selection sort har o'tishda faqat bitta almashtirish bajaradi — eng kichik element o'z joyiga o'tiriladi. Bubble sort esa bitta o'tishda ko'p almashtirishlar bajarishi mumkin. Agar almashtirish amalining o'zi qimmat bo'lsa (masalan, katta ob'ektlarni ko'chirish), selection sort bubble sortga qaraganda kamroq ish bajaradi.

Selection sortning murakkabligi

Holat	Vaqt murakkabligi	Izoh
Eng yaxshi	`O(n²)`	Allaqachon saralangan bo'lsa ham barcha tekshiruvlar bajariladi
O'rtacha	`O(n²)`
Eng yomon	`O(n²)`
Xotira murakkabligi	`O(1)`	Joyida ishlaydi

Selection sort barqaror emas — teng elementlarning tartibi o'zgarishi mumkin. Masalan, teng ikkita elementni almashtirish ularning eski tartibini buzadi.

Selection sortning muhim xususiyati: hech qachon O(n log n) ga yaxshilab bo'lmaydi. U doim O(n²) ta taqqoslash bajaradi — massiv saralangan bo'lsa ham, chunki u har safar qolgan qismning minimumini topishi kerak.

Insertion sort — qo'ldagi kartalarni tartibga solish

Insertion sort ("kiritish saralash") karta o'yinchilarining tabiiy odatiga o'xshaydi. Yangi karta olganingizda uni allaqachon tartibga solingan qo'lingizdagi kartalar orasiga to'g'ri joyga kiritasiz. Siz barchasini qayta tartiblamaysiz — faqat yangi kartaning o'rnini topasiz.

Insertion sort ham xuddi shu mantiqda ishlaydi. Massivni ikkiga bo'ladi: chap qism — allaqachon saralangan, o'ng qism — hali ko'rilmagan. Har bir yangi element saralangan qismning to'g'ri joyiga kiritiladi.

Algoritm

FUNCTION insertion_sort(array)
    n = array uzunligi

    FOR i = 1 DAN n - 1 GACHA
        joriy = array[i]
        j = i - 1

        WHILE j >= 0 VA array[j] > joriy
            array[j + 1] = array[j]
            j = j - 1

        array[j + 1] = joriy

    RETURN array

joriy — hozir joylashtiriladigan element. j indeks chapga ketib, joriydan katta elementlarni bir katak o'ngga suradi. joriy uchun to'g'ri joy topilganda u u yerga yoziladi.

Bosqichma-bosqich tahlil

[4, 2, 7, 1, 5] massivini saralaylik.

i = 1, joriy = 2:

Saralangan: [4]     Ko'rilmagan: [2, 7, 1, 5]

4 > 2? Ha → 4 o'ngga surish
[_, 4, 7, 1, 5]
2 ni 0-joyga qo'yish
[2, 4, 7, 1, 5]

Saralangan: [2, 4]

i = 2, joriy = 7:

Saralangan: [2, 4]  Ko'rilmagan: [7, 1, 5]

4 > 7? Yo'q → to'xtash
7 ni 2-joyda qoldir
[2, 4, 7, 1, 5]

Saralangan: [2, 4, 7]

i = 3, joriy = 1:

Saralangan: [2, 4, 7]  Ko'rilmagan: [1, 5]

7 > 1? Ha → 7 o'ngga
4 > 1? Ha → 4 o'ngga
2 > 1? Ha → 2 o'ngga
[_, 2, 4, 7, 5]
1 ni 0-joyga
[1, 2, 4, 7, 5]

Saralangan: [1, 2, 4, 7]

i = 4, joriy = 5:

Saralangan: [1, 2, 4, 7]  Ko'rilmagan: [5]

7 > 5? Ha → 7 o'ngga
4 > 5? Yo'q → to'xtash
[1, 2, 4, _, 7]
5 ni 3-joyga
[1, 2, 4, 5, 7]

Saralandi ✓

Deyarli saralangan massivlar uchun ideal

Insertion sortning muhim xususiyati: massiv allaqachon saralangan bo'lsa yoki deyarli saralangan bo'lsa, u juda tez ishlaydi.

Allaqachon saralangan massivda har bir element uchun ichki WHILE sikli bir marta ham ishlamaydi — joriy har doim saralangan qismning oxiridan katta bo'ladi. Faqat tashqi takrorlash ishlaydi: n - 1 ta tekshiruv. Shu sababli eng yaxshi holat O(n).

Amalda bu muhim: agar massivga yangi element oxiriga qo'shilgandan keyin saralash kerak bo'lsa (masalan, allaqachon saralangan ro'yxatga yangi yozuv qo'shildi), insertion sort O(n) da ishlaydi.

Insertion sortning murakkabligi

Holat	Vaqt murakkabligi	Izoh
Eng yaxshi (allaqachon saralangan)	`O(n)`	Har bir element uchun bitta taqqoslash
O'rtacha	`O(n²)`
Eng yomon (teskari saralangan)	`O(n²)`	Har bir element maksimal chapga surishi kerak
Xotira murakkabligi	`O(1)`	Joyida ishlaydi

Insertion sort barqaror: teng elementlarni o'tkazib yubormaydi, shu sababli ularning tartibi saqlanadi.

Uchala algoritmni taqqoslash

Xususiyat	Bubble sort	Selection sort	Insertion sort
Eng yaxshi holat	`O(n)`	`O(n²)`	`O(n)`
O'rtacha holat	`O(n²)`	`O(n²)`	`O(n²)`
Eng yomon holat	`O(n²)`	`O(n²)`	`O(n²)`
Xotira	`O(1)`	`O(1)`	`O(1)`
Barqarorlik	Barqaror	Barqaror emas	Barqaror
Almashtirishlar soni	Ko'p bo'lishi mumkin	Minimal (`O(n)` ta)	O'rtacha
Deyarli saralanganda	Tez (optimizatsiya bilan)	Sekin	Juda tez

Qaysi algoritmni qachon tanlash kerak?

Uchala algoritm ham O(n²) bo'lgani uchun katta massivlar uchun mos emas. Lekin kichik va maxsus hollarda o'z o'rinlari bor:

Kichik massivlar (10-50 element). Har uchala algoritm ham amalda tez ishlaydi — O(n²) faqat katta n uchun muammo.
Deyarli saralangan massiv. Insertion sort eng tez variant. Ozgina tartibsiz elementlarni joy-joyiga qo'yish uchun O(n) ga yaqin ishlaydi.
Almashtirish qimmat bo'lganda. Selection sort eng kam almashtirish bajaradi — O(n) ta. Agar elementlarni ko'chirish qimmat bo'lsa, shu afzallik ahamiyatli.
Kodning soddasi kerak bo'lganda. Bubble sort psevdokodi eng sodda yoziladi — o'quv va tushuntirish maqsadida qulay.

Katta massivlar uchun esa bu algoritmlarning o'rniga merge sort yoki quicksort tanlanadi — ular O(n log n) da ishlaydi va amalda ancha tezroq.

Tip

Amaliy dasturlashda ko'pchilik tillar saralash uchun tayyor funksiyalar taqdim etadi. Ular odatda O(n log n) algoritmlarni ichki ishlatadi. Lekin shu funksiyalardan foydalanishdan oldin ularning qanday ishlashini tushunish — qaysi holatlarda O(n²) ga tushib qolishi, barqarormi yoki emasligi — muhim.

Keng tarqalgan xatolar

Teskari tartibda taqqoslash

Kichikdan kattaga o'rniga kattadan kichikka saralash kerak bo'lganda taqqoslash shartini teskari qilish kifoya. Lekin bu o'zgartirishni qolgan mantiq bilan to'g'ri moslashtirmaslik xatolarga olib keladi.

Off-by-one xato

Bubble sortda ichki takrorlash n - i - 2 gacha borishi kerak — n - i - 1 gacha emas. Bir birlikka adashish oxirgi element uchun massiv chegarasidan tashqariga chiqishga olib keladi.

Boshlang'ich minimumni noto'g'ri belgilash

Selection sortda eng_kichik_index = i deb belgilash muhim. Agar uni 0 deb belgilasangiz, allaqachon saralangan qismni ham tekshirishga to'g'ri keladi.

Elementni to'g'ridan-to'g'ri yozib ketish

Insertion sortda joriy o'zgaruvchisiga elementni saqlash kerak. Aks holda, elementlarni o'ngga surish jarayonida joriy elementning qiymati ustiga yozib qo'yiladi va yo'qoladi.

Eng muhim xulosa

Bubble, selection va insertion sort — uchala algoritm ham bitta g'oyani turli ko'rinishda amalga oshiradi: har bir o'tishda massivni biroz "tartibli" qiladi va bu jarayonni takrorlaydi. Ular O(n²) bo'lgani uchun katta massivlarda ishlatilmaydi, lekin ularning mantig'ini tushunish muhim — merge sort va quicksort ham ushbu asosiy g'oyalar ustiga qurilgan.

Keyingi qismda biz ikki o'lchamli va rekursiv saralash algoritmlarini, jumladan merge sort va quicksortni ko'rib chiqamiz. Ular O(n log n) da ishlaydi va haqiqiy loyihalarda ishlatiladi.

📍 Toshkent, O'zbekiston
🗓️ 4-Avgust, 2026-yil
👤 Farrux Elomonov