Insertion Sort - Musobaqaviy dasturlash uchun C++ dasturlash tili

Modul 1: Dasturlashga kirish

Dasturlash nima?
Nega bizga dasturlash kerak?
Dasturlash muhitini sozlash

Modul 2: Birinchi dasturingiz

Hello World dasturi
Dastur tuzilishi
Masalalar

Modul 3: Kiritish/chiqarish va arifmetik operatorlar

Ma'lumotlarni kiritish/chiqarish
Arifmetik operatorlar
Masalalar

Modul 4: Shartli operatorlar

Taqqoslash operatorlari
Shart operatorlari
Masalalar
Masalalar

Modul 5: Ma'lumot turlari

Ma'lumot turlari
Masalalar
Masalalar
Masalalar
Masalalar

Modul 6: Takrorlash operatorlari

For sikli
While sikli
Masalalar
Masalalar
Masalalar
Masalalar

Modul 7: Massivlar

Massiv ta'rifi
Ko'p o'lchamli massivlar
Masalalar
Masalalar

Modul 8: Funksiyalar

Funksiya
Mash qilish uchun masalalar

Modul 9: Ichma-ich sikllar va ko'p o'lchamli massiv

Ichma-ich sikllar va ko‘p o‘lchovli massivlar
Mashq qilish uchun masalalar

Modul 10: Chiziqli qidiruv

Chiziqli qidiruv
Masalalar

Modul 11: STL ma'lumot tuzilmalari 1

STL ma'lumot tuzilmalari
Masalalar

Modul 12: Sodda saralash algoritmlari

Saralash tushunchasiga kirish
Bubble Sort
Selection Sort
Insertion Sort
Masalalar

Modul 13: STL ma'lumot tuzilmalari 1

STL ma'lumot tuzilmalari: set va map
Masalalar

Module 14: Brute-forces

Bruteforce'ga kirish
Masalalar

Module 15: Recursion

Rekursiyaga kirish
Masalalar

Module 16: Structs in C++

Structs

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Courses/Musobaqaviy dasturlash uchun C++ dasturlash tili/Modul 12: Sodda saralash algoritmlari/Insertion Sort

Insertion Sort

Insertion sort algoritmi

Algoritm $n-1$ ta iteratsiyadan iborat. $1 \leq i \leq n-1$ iteratsiyalarda biz uzunligi $i+1$ bo'lgan $a$ massivining prefiksini saralaymiz. Ya'ni, -iteratsiyadan oldin qism massiv saralangan bo'ladi, -iteratsiyadan keyin esa qism massiv saralangan bo'ladi. Buni qilish uchun ni qo'yish uchun to'g'ri joyni topish kifoya.

Up next

Masalalar

Mashq qilish uchun masalalar

i

i

a[1\ldots i]

i

a[1\ldots i+1]

a_{i+1}

Asimptotika: $O(N^2)$

for (int i = 1; i <= n - 1; i++) {
    for (int j = i + 1; j > 1; j--) {
        if (a[j - 1] > a[j]) {
            swap(a[j - 1], a[j]);
        } else {
            break;
        }
    }
}