Sortowanie przez wstawianie

Sortowanie przez wstawianie to również rodzaj techniki sortowania o złożoności czasowej O(n²), ale jest nieco bardziej zoptymalizowane niż sortowanie bąbelkowe.

W tym algorytmie tablica jest podzielona na dwie części. Jedna jest posortowana, a druga nieposortowana. Wybieramy element z nieposortowanej tablicy i umieszczamy go w posortowanej tablicy na właściwej pozycji.

Powtarzamy ten proces, aż wszystkie elementy zostaną posortowane.

1. Załóżmy, że mamy tablicę {8,4,1,5}. Uznajmy pierwszy element za posortowany, a wszystkie pozostałe za nieposortowane. Początkowo za posortowany uznawany jest element o indeksie 0.

2. Utwórz zmienną tymczasową i umieść w niej element o indeksie (i) (w tym przypadku jest to 4). Porównaj zmienną tymczasową z aktualnie posortowaną tablicą, która w tej chwili zawiera 8. Ponieważ 4<8, przesuń posortowaną tablicę w prawo, aż 4 znajdzie się na właściwej pozycji. W tym przypadku 8 trzeba przesunąć jeden raz. Teraz długość posortowanej tablicy wynosi 2.

3. Powtarzamy proces, aż cała tablica zostanie posortowana.

for(int i=1;i<n;i++){           //zacznij od pierwszego elementu, ponieważ uznajemy element o indeksie 0 za posortowany
    int temp=arr[i];
    
    int j=i-1;                  //aby sprawdzić wszystkie elementy po jego lewej stronie 
    
    while(arr[j]>temp && j>=0){ //przesuwaj elementy, dopóki są większe od temp, aż do pierwszego elementu
      arr[j+1]=arr[j];          //przesuń element o jedną pozycję w prawo
      j--;                      
    }
    
    arr[j+1]=temp;              //umieść temp we właściwym miejscu
  
}

Aby zobaczyć wizualizację sortowania przez wstawianie

Wizualizacja sortowania przez wstawianie