3-dars: Saralash — Bubble Sort

Dars haqida

Davomiyligi: 90 daqiqa Maqsad: Talaba sort algoritmlari muhimligini, Bubble Sort algoritmini va swap funksiyani bilishi kerak.

1. Sort muammosi

Sort (saralash) — massivni tartibda joylashtirish (kichikdan kattaga yoki teskari).

Avval:   [5, 2, 8, 1, 9, 3]
Sort:    [1, 2, 3, 5, 8, 9]

2. Nima uchun sort?

• Binary search uchun shart
• Statistika (median topish)
• Ko'rsatish (top 10)
• Hisobot (alfabit, narx)
• Maksimum/minimum topish oson

3. Swap — almashtirish

Sort algoritmining asosiy amali:

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

Yoki — temp o'zgaruvchisi bilan to'g'ridan-to'g'ri:

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

XOR swap

Ba'zilarda a ^= b; b ^= a; a ^= b; ko'rasiz. Ishlatmang — chigallik, foyda yo'q.

Oddiy temp yondashuvi — eng yaxshi.

4. Bubble Sort g'oyasi

Qo'shni elementlarni taqqoslab — almashtirish.

[5, 2, 8, 1, 9, 3]

Iter 1:
5 > 2? Ha — almashtirish: [2, 5, 8, 1, 9, 3]
5 > 8? Yo'q
8 > 1? Ha: [2, 5, 1, 8, 9, 3]
8 > 9? Yo'q
9 > 3? Ha: [2, 5, 1, 8, 3, 9]

Iter 1 oxiri: [2, 5, 1, 8, 3, 9]  ← eng katta (9) oxirga "ko'tarildi"

Iter 2: ...

Har iteration'da — eng katta element oxirga "ko'tariladi". Shuning uchun "bubble".

5. Bubble Sort kod

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Tushuntirish

• Tashqi sikl i — N-1 marta (eng ko'p urinish)
• Ichki sikl j — har iteration'da bittaga kam (oxirga ko'tarilganlarni tekshirish kerak emas)
• arr[j] > arr[j+1] — qo'shnilar tartibda emasmi?
• Swap

6. Trace (qadamma-qadam)

arr = [5, 2, 8, 1, 9]

Iter 1 (i=0):

[5,2,8,1,9] → 5>2: [2,5,8,1,9]
[2,5,8,1,9] → 5>8: yo'q
[2,5,8,1,9] → 8>1: [2,5,1,8,9]
[2,5,1,8,9] → 8>9: yo'q

Natija: [2,5,1,8,9]

Iter 2 (i=1):

[2,5,1,8,9] → 2>5: yo'q
[2,5,1,8,9] → 5>1: [2,1,5,8,9]
[2,1,5,8,9] → 5>8: yo'q
(9 ni tekshirmaymiz)

Natija: [2,1,5,8,9]

Iter 3 (i=2):

[2,1,5,8,9] → 2>1: [1,2,5,8,9]
(qolganlari sortlangan)

Natija: [1,2,5,8,9]

Iter 4 (i=3):

[1,2,5,8,9] → 1>2: yo'q

Sortlangan!

7. Optimizatsiya — swapped flag

Massiv allaqachon sortlangan bo'lsa — erta to'xtatish:

void bubble_sort_optimized(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;  // bu iteration'da swap bo'ldimi?
        
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        
        if (!swapped) break;  // sortlangan, to'xtash
    }
}

8. Tezligi (Big O)

Holat	Tekshirishlar	Swaps
Eng yaxshi (sortlangan, optimized)	n	0
O'rtacha	n²	n² / 2
Eng yomon (teskari sortlangan)	n²	n² / 2

Big O: O(n²) — kvadratik.

n	Amallar
10	100
100	10,000
1,000	1,000,000
10,000	100,000,000

Bubble Sort — kichik massiv uchun OK. Katta uchun juda sekin.

9. To'liq dastur

#include <stdio.h>

void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

int main(void) {
    int arr[] = {64, 25, 12, 22, 11};
    int n = 5;
    
    printf("Avval: ");
    print_array(arr, n);
    
    bubble_sort(arr, n);
    
    printf("Keyin: ");
    print_array(arr, n);
    
    return 0;
}

Natija:

Avval: 64 25 12 22 11 
Keyin: 11 12 22 25 64

10. Sort + Binary Search

int arr[] = {64, 25, 12, 22, 11, 90, 1, 45, 78, 33};
int n = 10;

// Avval sort
bubble_sort(arr, n);

// Endi binary search
int idx = binary_search(arr, n, 45);

11. Visualizatsiya

Har iteration'dan keyin massivni chiqarish — yaxshi o'rganish usuli:

void bubble_sort_verbose(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        printf("Iter %d: ", i + 1);
        
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        
        print_array(arr, n);
    }
}

12. Teskari sort (descending)

Faqat > ni < ga o'zgartirish:

if (arr[j] < arr[j + 1]) {  // < o'rniga >
    // swap
}

Yoki — comparator funksiya bilan (kelajakdagi mavzu).

13. Sort va Search vaqti

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int n = 10000;
    int arr[10000];
    
    // Random to'ldirish
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100000;
    }
    
    // Sort vaqti
    clock_t start = clock();
    bubble_sort(arr, n);
    clock_t end = clock();
    double time = (double)(end - start) / CLOCKS_PER_SEC;
    
    printf("Bubble sort %d element: %.4f sekund\n", n, time);
    
    return 0;
}

10,000 element — taxminan 0.5 sekund.

100,000 element — 50 sekund.

1,000,000 — soatlar!

(Bu — keyingi darslarda yaxshilanadi)

Darsdagi topshiriqlar

1 — Bubble sort

bubble.c — Dars matnidagi to'liq dastur.

2 — Verbose

bubble-verbose.c — har iteration'dan keyin chiqarish.

3 — Optimized

bubble-opt.c — swapped flag bilan.

Avval va keyin vaqtni taqqoslash.

4 — Descending

bubble-desc.c — teskari (kattadan kichikga).

5 — Random data

random-sort.c:

1. 100 ta random element yaratish
2. Sort qilish
3. Avval va keyin chiqarish

6 — Sort + Search

sort-search.c:

1. Massivni sort qilish
2. Foydalanuvchi raqam beradi
3. Binary search bilan topish

7 — String sort

string-sort.c — alfabit bo'yicha:

char names[5][20] = {"Botir", "Akmal", "Dilshod", "Aziza", "Eldor"};

// strcmp bilan taqqoslash, strcpy bilan swap

(Bu — strcpy ishlatish kerak, chunki char massivlarini =/swap qilib bo'lmaydi)

8 — Vaqt o'lchash

speed.c:

100, 1000, 10000 element uchun bubble sort vaqtini o'lchang.

Natijalar:

100:    ___ ms
1000:   ___ ms
10000:  ___ ms

Nima sezdingiz? Big O ko'rinmoqdami?

9 — Swap funksiya

swap.c:

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

Bu — pointer ishlatadi (keyingi darslarda batafsil).

Sinab ko'ring:

int x = 5, y = 10;
swap(&x, &y);
printf("%d %d\n", x, y);  // 10 5

10 — GitHub

$ mkdir 5-oy-dars-3
$ git add . && git commit -m "feat: dars 3 - bubble sort" && git push

Lug'at

Termin	Izoh
Sort	Saralash
Bubble Sort	Pufakcha saralash
Swap	Almashtirish
Ascending	Kichikdan kattaga
Descending	Kattadan kichikga
O(n²)	Kvadratik tezlik
Stable sort	Teng elementlar tartibi saqlanadi
In-place	Qo'shimcha xotirasiz

Keyingi dars

4-dars: Selection va Insertion Sort →