5-dars: Saralash algoritmlari — Bubble, Selection, Insertion
Dars haqida
Davomiyligi: 90 daqiqa Maqsad: Talaba saralash muammosini tushunishi, Bubble, Selection va Insertion Sort algoritmlarini yozishi va ularni tezlik (Big O) bo'yicha taqqoslay olishi 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]Nima uchun kerak:
- Binary search uchun shart (4-darsda ko'rdik — faqat sortlangan massivda ishlaydi)
- Statistika (median topish)
- Ko'rsatish (top 10)
- Hisobot (alifbo, narx bo'yicha)
- Maksimum/minimum topish oson
2. Swap — almashtirish
Har qanday sort algoritmining asosiy amali — ikki elementni almashtirish:
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;Funksiya ko'rinishida (pointer ishlatadi — 7-darsda batafsil):
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}XOR swap
Ba'zilarda a ^= b; b ^= a; a ^= b; ko'rasiz. Ishlatmang — chigallik, foyda yo'q. Oddiy temp yondashuvi — eng yaxshi.
3. Bubble Sort
G'oya: qo'shni elementlarni taqqoslab — almashtirish. Har iteration'da eng katta element oxirga "ko'tariladi" — shuning uchun "bubble" (pufakcha).
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;
}
}
}
}- 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.
Qadam-baqadam: [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'qNatija: [2,5,1,8,9] — eng katta (9) oxirga ko'tarildi.
Iter 2 (i=1): [2,1,5,8,9] (9 ni tekshirmaymiz) Iter 3 (i=2): [1,2,5,8,9]Iter 4 (i=3): swap yo'q — sortlangan!
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
}
}4. Selection Sort
G'oya: har iteration'da qolganlar ichidan eng kichik elementni topib — navbatdagi joyga qo'yish.
void selection_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Eng kichik elementni topish
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// Swap
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}Qadam-baqadam: [64, 25, 12, 22, 11]
Iter 1: eng kichik = 11 → birinchi joyga: [11, 25, 12, 22, 64]
Iter 2: qolganidan eng kichik = 12: [11, 12, 25, 22, 64]
Iter 3: 22 → uchinchi joyga: [11, 12, 22, 25, 64]
Iter 4: 25 → joyida: [11, 12, 22, 25, 64]Bubble'dan farqi: swap juda kam — har iteration'da ko'pi bilan 1 ta (Bubble deyarli har taqqoslashda swap qilishi mumkin).
5. Insertion Sort
G'oya: qo'ldagi kartalarni saralash kabi — har yangi elementni sortlangan qismning kerakli joyiga qo'yish.
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// key dan kattalarni o'ngga ko'chirish
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}Qadam-baqadam: [64, 25, 12, 22, 11]
Iter 1 (25 ni qo'yish): [25, 64 | 12, 22, 11]
Iter 2 (12 ni qo'yish): [12, 25, 64 | 22, 11]
Iter 3 (22 ni qo'yish): [12, 22, 25, 64 | 11] ← 22 > 12 bo'lgach STOP
Iter 4 (11 ni qo'yish): [11, 12, 22, 25, 64]| chizig'ining chap tomoni — har doim sortlangan qism.
Insertion Sort qachon zo'r
Deyarli sortlangan massivlar uchun — eng tez: har element deyarli joyida, ichki sikl darrov to'xtaydi. Real ma'lumotlarda ko'pchilik qismi tartibda bo'ladi — Insertion juda samarali.
6. Tezlik — Big O
Uchala algoritm ham o'rtacha holatda O(n²) — kvadratik:
| n | Amallar (n²) |
|---|---|
| 10 | 100 |
| 100 | 10,000 |
| 1,000 | 1,000,000 |
| 10,000 | 100,000,000 |
n 10 baravar oshsa — vaqt 100 baravar oshadi. Kichik massivlar uchun OK, katta uchun juda sekin.
Tipik o'lchov (10,000 element):
Bubble: 0.500 s
Selection: 0.300 s
Insertion: 0.200 s
qsort: 0.001 s7. Taqqoslash jadvali
| Algoritm | Best | Average | Worst | Swaps | Stable |
|---|---|---|---|---|---|
| Bubble (optimized) | O(n) | O(n²) | O(n²) | ~n²/2 | Ha |
| Selection | O(n²) | O(n²) | O(n²) | ≤ n-1 | Yo'q |
| Insertion | O(n) | O(n²) | O(n²) | ~n²/2 | Ha |
Stable sort — teng elementlarning asl tartibi saqlanadi.
Qachon qaysi biri?
| Holat | Tanlov | Sabab |
|---|---|---|
| O'rganish, kichik massiv | Bubble | Eng sodda kod |
| Swap qimmat (katta elementlar) | Selection | Swap eng kam (≤ n-1) |
| Deyarli sortlangan ma'lumot | Insertion | O(n) ga yaqin ishlaydi |
| Real loyiha, katta massiv | qsort | O(n log n) |
8. To'liq dastur — uchala algoritm
#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++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int t = arr[j]; arr[j] = arr[j+1]; arr[j+1] = t;
}
}
}
}
void selection_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) min_idx = j;
}
int t = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = t;
}
}
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main(void) {
int original[] = {64, 25, 12, 22, 11, 90, 1, 45};
int n = 8;
int arr[8];
// Bubble
for (int i = 0; i < n; i++) arr[i] = original[i];
bubble_sort(arr, n);
printf("Bubble: "); print_array(arr, n);
// Selection
for (int i = 0; i < n; i++) arr[i] = original[i];
selection_sort(arr, n);
printf("Selection: "); print_array(arr, n);
// Insertion
for (int i = 0; i < n; i++) arr[i] = original[i];
insertion_sort(arr, n);
printf("Insertion: "); print_array(arr, n);
return 0;
}Natija — uchchalasida bir xil sortlangan massiv.
9. qsort — standart C funksiya
C standart kutubxonasida qsort bor — Quick Sort asosida, O(n log n):
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int main(void) {
int arr[] = {64, 25, 12, 22, 11};
int n = 5;
qsort(arr, n, sizeof(int), compare);
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}Real ishda — o'z sortingizni yozmang, qsort yoki tilga moslangan sort ishlating.
Boshqa mashhur algoritmlar (eslatma):
| Algoritm | Big O | Holat |
|---|---|---|
| Merge | O(n log n) | Stable, tez |
| Quick | O(n log n) average | Eng tez (qsort) |
| Heap | O(n log n) | In-place tez |
| Counting | O(n + k) | Cheklangan range |
Foundation'da — asosiy 3 ta. Universitetda — boshqalar.
10. Sort + Binary Search
Sortlashning asosiy foydasi — endi binary search ishlaydi:
int arr[] = {64, 25, 12, 22, 11, 90, 1, 45, 78, 33};
int n = 10;
// Avval sort
bubble_sort(arr, n);
// Endi binary search (4-darsdan)
int idx = binary_search(arr, n, 45);Darsdagi topshiriqlar
Topshiriq 1 — Bubble sort
bubble.c — dars matnidagi to'liq dastur (optimized versiya bilan).
Bonus: teskari (descending) versiya — faqat > ni < ga almashtirish.
Topshiriq 2 — Verbose
bubble-verbose.c — Bubble sortni yozing, lekin har bir tashqi iteratsiyadan keyin massivning joriy holatini chop etsin (masalan Iter 1: ...). Shunda algoritm qadamma-qadam qanday ishlashini kuzatish mumkin bo'ladi.
Algoritmni "ko'rish" — eng yaxshi o'rganish usuli.
Topshiriq 3 — Selection sort
selection.c — to'liq dastur. Qadam-baqadam natijani daftarda ham yurgizib ko'ring.
Topshiriq 4 — Insertion sort
insertion.c — to'liq dastur.
Topshiriq 5 — 3 algoritm
all-sorts.c — uchala algoritmni bitta dasturda taqqoslash (dars matnidagi to'liq dastur).
Topshiriq 6 — Sort + Search
sort-search.c:
- Massivni sort qilish
- Foydalanuvchi raqam beradi
- Binary search bilan topish (4-darsdan)
Topshiriq 7 — qsort
qsort-mashq.c — qsort ishlatish.
Bonus: descending sort (compare funksiyasini o'zgartirish).
Topshiriq 8 — Vaqt o'lchash
speed.c — #include <time.h> va clock() bilan 100, 1000, 10000 element uchun har algoritm vaqtini o'lchang:
n=100: Bubble ___ Selection ___ Insertion ___ qsort ___
n=1000: ...
n=10000: ...Big O ko'rinmoqdami?
Bonus: deyarli sortlangan massivda (sortlangan + 5 ta random swap) Insertion va Bubble'ni taqqoslang — Insertion qaysi holatda yaxshi?
Topshiriq 9 — GitHub
$ mkdir 5-oy-dars-5
$ git add . && git commit -m "feat: dars 5 - sorting algorithms" && git pushAsosiy tushunchalar (lug'at)
| Termin | Izoh |
|---|---|
| Sort | Saralash |
| Bubble Sort | Qo'shnilarni almashtirib saralash |
| Selection Sort | Eng kichikni topib joylash |
| Insertion Sort | Kerakli joyga qo'yish |
| Swap | Almashtirish |
| Ascending | Kichikdan kattaga |
| Descending | Kattadan kichikga |
| O(n²) | Kvadratik tezlik |
| Stable sort | Teng elementlar tartibi saqlanadi |
| In-place | Qo'shimcha xotirasiz |
| qsort | Standart C sort funksiyasi |
| Comparator | Taqqoslash funksiyasi |
| Quick / Merge Sort | O(n log n) — tezkor algoritmlar |