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.

Dark inverted insertion sorting

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(n²) 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.

InsertionSort

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;
}