4-dars: Saralash — Selection va Insertion Sort
Dars haqida
Davomiyligi: 90 daqiqa Maqsad: Talaba Selection Sort va Insertion Sort algoritmlarini bilishi, Bubble bilan taqqoslay olishi kerak.
1. Selection Sort
G'oya: har iteration'da eng kichik element topib — birinchi joyga qo'yish.
[64, 25, 12, 22, 11]
Iter 1: eng kichik = 11 → birinchi joyga
[11, 25, 12, 22, 64]
Iter 2: qolganidan eng kichik = 12 → ikkinchi joyga
[11, 12, 25, 22, 64]
Iter 3: 22 → uchinchi joyga
[11, 12, 22, 25, 64]
Iter 4: 25 → joyida (yoki swap)
[11, 12, 22, 25, 64]2. Selection Sort kod
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;
}
}
}3. Selection Sort tezligi
Big O: O(n²) — har holatda.
| Holat | Tekshirishlar | Swaps |
|---|---|---|
| Eng yaxshi | n² | 0 (yoki kam) |
| Eng yomon | n² | n-1 |
Bubble vs Selection:
- Tekshirishlar — bir xil
- Swaps — Selection kam (bubble — har taqqoslashda)
4. Insertion Sort
G'oya: kartochkalarni qo'lda saralash kabi. Har yangi element — kerakli joyga qo'yish.
[64, 25, 12, 22, 11]
Iter 1 (25 ni qo'yish):
[64, 25] → 25 < 64 → [25, 64]
Sortlangan: [25, 64], qolgan: 12, 22, 11
Iter 2 (12 ni qo'yish):
[25, 64, 12] → 12 < 64 → [25, 12, 64]
→ 12 < 25 → [12, 25, 64]
Sortlangan: [12, 25, 64]
Iter 3 (22 ni qo'yish):
[12, 25, 64, 22] → 22 < 64 → [12, 25, 22, 64]
→ 22 < 25 → [12, 22, 25, 64]
→ 22 > 12 → STOP
Sortlangan: [12, 22, 25, 64]
Iter 4 (11 ni qo'yish):
... → [11, 12, 22, 25, 64]5. Insertion Sort kod
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;
}
}6. Insertion Sort tezligi
| Holat | Tezlik |
|---|---|
| Eng yaxshi (sortlangan) | O(n) |
| O'rtacha | O(n²) |
| Eng yomon (teskari) | O(n²) |
Insertion Sort yaxshi
Deyarli sortlangan massivlar uchun — eng tez.
Misol: real ma'lumotda ko'pchilik tartibda — Insertion juda samarali.
7. 3 algoritm taqqoslash
| Algoritm | Best | Average | Worst | Swaps | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | n² | Ha |
| Selection | O(n²) | O(n²) | O(n²) | n | Yo'q |
| Insertion | O(n) | O(n²) | O(n²) | n² | Ha |
Stable sort — teng elementlarning asl tartibi saqlanadi.
8. 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++) {
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 — bir xil sortlangan massiv.
9. qsort — standart C funksiya
C standart kutubxonasida qsort funksiyasi bor — Quick Sort asosida.
#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;
}qsort — O(n log n) — eng tezlardan biri.
Real ishda — o'z sort yozmang, qsort yoki tilga moslangan sort ishlating.
10. Algoritm tezliklarini taqqoslash
#include <time.h>
int main(void) {
int n = 10000;
int arr[10000];
// Random
srand(time(NULL));
// Bubble
for (int i = 0; i < n; i++) arr[i] = rand() % 100000;
clock_t s = clock();
bubble_sort(arr, n);
printf("Bubble: %.3f s\n", (double)(clock() - s) / CLOCKS_PER_SEC);
// Selection
for (int i = 0; i < n; i++) arr[i] = rand() % 100000;
s = clock();
selection_sort(arr, n);
printf("Selection: %.3f s\n", (double)(clock() - s) / CLOCKS_PER_SEC);
// Insertion
for (int i = 0; i < n; i++) arr[i] = rand() % 100000;
s = clock();
insertion_sort(arr, n);
printf("Insertion: %.3f s\n", (double)(clock() - s) / CLOCKS_PER_SEC);
// qsort
for (int i = 0; i < n; i++) arr[i] = rand() % 100000;
s = clock();
qsort(arr, n, sizeof(int), compare);
printf("qsort: %.3f s\n", (double)(clock() - s) / CLOCKS_PER_SEC);
return 0;
}Tipik natija (10,000 element):
Bubble: 0.500 s
Selection: 0.300 s
Insertion: 0.200 s
qsort: 0.001 s11. Boshqa sort algoritmlari (eslatma)
| Algoritm | Big O | Holat |
|---|---|---|
| Bubble | O(n²) | O'qish uchun |
| Selection | O(n²) | Swap kam |
| Insertion | O(n²) | Deyarli sortlangan |
| 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 |
| Radix | O(nk) | Integer uchun |
| Tim sort | O(n log n) | Python, Java |
Foundation'da — asosiy 3 ta. Universitetda — boshqalar.
Darsdagi topshiriqlar
1 — Selection sort
selection.c — to'liq dastur.
2 — Insertion sort
insertion.c — to'liq dastur.
3 — Verbose
sort-verbose.c — har sort uchun iteration ko'rinishi.
4 — 3 algoritm
all-sorts.c — 3 algoritmni bitta dasturda taqqoslash.
5 — qsort
qsort-mashq.c — qsort ishlatish.
Bonus: descending sort (compare funksiyasi).
6 — Vaqt
speed.c — 100, 1000, 10000, 100000 element uchun.
Jadval ko'rinishida natijalarni yozing.
7 — String sort
string-sort.c — ismlar massivini alfabit bo'yicha:
char names[5][20] = {"Botir", "Akmal", "Dilshod", "Aziza", "Eldor"};strcmp va strcpy bilan.
8 — Struct preview
Talabalar ball bo'yicha sort:
int names_count = 5;
char names[5][20] = {"Botir", "Akmal", "Dilshod", "Aziza", "Eldor"};
int scores[5] = {75, 92, 60, 85, 70};
// names'ni scores bo'yicha sort qiling
// (parallel ikkita massiv)Murakkab — keyingi darslarda struct bilan oson.
9 — Almost sorted
almost.c:
- Sortlangan massiv (1, 2, 3, ..., 100)
- 5 ta tasodifiy elementni almashtirish
- Insertion va Bubble vaqti taqqoslash
Insertion qaysi holatda yaxshi?
10 — GitHub
$ mkdir 5-oy-dars-4
$ git add . && git commit -m "feat: dars 4 - selection/insertion sort" && git pushLug'at
| Termin | Izoh |
|---|---|
| Selection Sort | Eng kichikni topib joylash |
| Insertion Sort | Kerakli joyga qo'yish |
| Quick Sort | Eng tez (qsort) |
| Merge Sort | Stable, O(n log n) |
| Stable sort | Teng tartibi saqlanadi |
| In-place | Qo'shimcha xotirasiz |
| qsort | Standart C funksiya |
| Comparator | Taqqoslash funksiyasi |