Insertion sort

**Insertion sort — (Joylab saralash)** ham tartibsiz massiv elementlarini saralash uchun moʻljallangan. Uning ishlash algoritmi xuddi qoʻldagi kartani saralashga oʻxshab ketadi. Tartibsiz turgan kartalar ichidan birini olasiz va uni oʻzi turishi kerak boʻlgan joyga joylashtirib qoʻyasiz.

Insertion sort ham shu koʻrinishda ishlaydi. Algoritm oldin massiv boshidagi ikkita elementni saralab olib, massivning qolgan elementlarini shunga qarab oʻz oʻrniga joylashtirib chiqadi.

## Joylab saralashning xususiyatlari
Bu algoritm oddiy amalga oshirilgani uchun eng oddiy algoritmlardan biridir.
Insertion sort kichik maʼlumotlarni saralash uchun samarali.
Joylab saralash tabiatan moslashuvchan, yaʼni qisman saralangan maʼlumotlar toʻplamlari uchun mos keladi.

Insertion sort ham Selection sort va Bubble sort kabi O(n2) vaqt murakkabligi bilan ishlasa ham, lekin ulardan koʻra samaraliroq algoritm hisoblanadi. Aynan, massiv elementlari deyarli saralangan holatda Insertion sort algoritmi Merge sort yoki Quick sort algoritmidan ham koʻra tezroq ishlaydi.

## Joylab saralash algoritmining ishlashi
Misolni koʻrib chiqing: arr[]: {12, 11, 13, 5, 6}
   12   	   11   	   13   	   5   	   6   
;Birinchi oʻtish:
Dastlab, massivning dastlabki ikkita elementi joylash tartibida taqqoslanadi.
   12   	   11   	   13   	   5   	   6   
Bu yerda 12 11 dan katta, ular oʻsish tartibida emas va 12 oʻzining toʻgʻri joyida emas. Shunday qilib, 11 va 12 ning oʻrnini almashtiring.
Shunday qilib, hozircha 11 tartiblangan pastki qatorda saqlanadi.
   11   	   12   	   13   	   5   	   6   
;Ikkinchi oʻtish:
Endi keyingi ikkita elementga oʻting va ularni solishtiring
   11   	   12   	   13   	   5   	   6   
Bu yerda 13 12 dan katta, shuning uchun ikkala element ham oʻsish tartibida turibdi, almashtirish sodir boʻlmaydi. 12, shuningdek, 11 bilan birga tartiblangan pastki qatorda saqlanadi
;Uchinchi oʻtish:
Endi tartiblangan kichik massivda ikkita element mavjud, ular 11 va 12
Keyingi ikkita elementga oʻtish: 13 va 5
   11   	   12   	   13   	   5   	   6   
5 va 13 ikkalasi ham oʻz joyida emas, shuning uchun ularni almashtiring
   11   	   12   	   5   	   13   	   6   
Almashtirilgandan soʻng, 12 va 5 elementlar tartiblanmadi, shuning uchun yana almashtiriladi
   11   	   5   	   12   	   13   	   6   
Bu yerda yana 11 va 5 tartiblanmadi, shuning uchun yana almashtiring
   5   	   11   	   12   	   13   	   6   
bu yerda u oʻzining toʻgʻri holatida
;Toʻrtinchi oʻtish:
Endi tartiblangan kichik massivda mavjud boʻlgan elementlar 5, 11 va 12
Keyingi ikkita elementga oʻtish: 13 va 6
   5   	   11   	   12   	   13   	   6   
Shubhasiz, ular tartiblanmagan, shuning uchun ikkalasini almashtirishni amalga oshiring
   5   	   11   	   12   	   6   	   13   
Endi 6 12 dan kichik, shuning uchun yana almashtiring
   5   	   11   	   6   	   12   	   13   
Almashtirish 11 va 6 ni tartiblamaydi, shuning uchun yana almashtiring
   5   	   6   	   11   	   12   	   13   
Nihoyat, massiv toʻliq tartiblangan.

## Dasturi

```
#include <bits/stdc++.h>
using namespace std;
void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}
int main()
{
    int arr[] = { 12, 11, 13, 5, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, N);
    printArray(arr, N);
    return 0;
}
```

## Manbalar