Sortowanie przez wstawianie – co to jest, schemat blokowy oraz przykład zastosowania

Algorytmy sortowania to kluczowy element w procesie nauki programowania. Dzięki nim można zrozumieć wiele przydatnych technik wykorzystywanych przy tworzeniu pełnych programów. Jednym z najważniejszych algorytmów sortujących, który powinien znać każdy uczeń informatyki lub uczestnik zajęć z tego przedmiotu, jest sortowanie przez wstawianie.

Co to jest sortowanie przez wstawianie?

Sortowanie przez wstawianie (insertion sort) to algorytm, który wprowadza kolejne elementy na odpowiednie pozycje w już uporządkowanej części zbioru danych. Na początku pierwszy element jest traktowany jako posortowany, a kolejny jest umieszczany przed nim lub za nim, w zależności od wartości. W każdym następnym kroku nowy element jest porównywany z uporządkowanymi danymi i wstawiany we właściwe miejsce. Algorytm ten jest szczególnie efektywny przy niewielkich zbiorach danych. Co ciekawe, jest on elementem bardziej zaawansowanego algorytmu sortującego Shella.

Zalety sortowania przez wstawianie

• łatwy do zrozumienia oraz implementacji – szybko go zrozumiesz oraz wstawisz do swojego programu,
• stabilny – liczby o tej samej wartości pozostają na swoich miejscach,
• sprawnie działa na małych zbiorach danych – cechuje się wysoką wydajnością przy niewielkich tablicach/listach.

Wady sortowania przez wstawianie

• mało wydajny przy dużych zbiorach danych – szybkość wykonania znacząco spada w przypadku tego typu tablic/list.

Przykład użycia sortowania przez wstawianie

Poniżej znajduje się przykład sortowania listy/tablicy 3, 2, 7, 4, 6 w formie grafiki GIF oraz zapisu tekstowego. Wartości są sortowane w kolejności rosnącej.

Poniżej znajdziesz przykład użycia sortowania przez wstawianie w formie zapisu tekstowego. Zapoznanie się z nim pomoże Ci zrozumieć jego działanie.

Sortowanie przez wstawianie się zakończyło, zwracając posortowany zbiór liczb: 2 3 4 6 7. W przypadku 5 liczb potrzebne były do tego 4 cykle. Liczba cykli jest mniejsza o jeden od liczby danych w sortowanym zbiorze.

Ważne: Warto zauważyć, że w przypadku powyższego przykładu oraz gifa z przykładem zastosowano uproszczony zapis sortowania przez wstawianie. W ramach programu stosuje się dodatkową zmienną pomocniczą, w której zapisywana jest aktualnie sortowana liczba, i jedynie porównuje się ją z posortowaną częścią zbioru, bez zapisywania jej w nim. Dlatego wartość jest zapisana w zbiorze dopiero na docelowym miejscu, gdzie powinna trafić.

Implementacja algorytmu sortowanie przez wstawianie

Schemat blokowy i pseudokod sortowania przez wstawianie

funkcja SortowaniePrzezWstawianie(zbior, n)
    Dla i = 2, 3, 4,  …  n wykonuj
        pom ← zbior[i]
        j ← i - 1
        Dopóki j > 0 i zbior[j] > pom wykonuj
            zbior[j + 1] ← zbior[j]
            j ← j - 1
        zbior[j + 1] ← pom

Komentarze do pseudokodu sortowania przez wstawianie

• 1 linia – Funkcja zostaje zainicjowana, a jako argumenty przyjmuje zbior (tablicę/listę danych) oraz zmienną n, oznaczającą liczbę elementów do posortowania.  
• 2 linia – Pętla dla… wykonuj (for) rozpoczyna iterację od drugiego elementu tablicy zbior (indeks 2) i kontynuuje do ostatniego elementu (indeks n).  
• 3 linia – Bieżący element tablicy, znajdujący się pod indeksem i, zostaje przypisany do zmiennej tymczasowej pom.  
• 4 linia – Zmienna j otrzymuje wartość (i - 1), która posłuży do porównywania aktualnego elementu z poprzednimi w kolejnych krokach.  
• 5 linia – Pętla dopóki (while) sprawdza, czy j jest większe od zera oraz czy wartość zbior[j] przewyższa wartość zapisaną w pom.  
• 6 linia – Gdy oba warunki są spełnione, przesuwamy element o jeden indeks w prawo, tworząc miejsce dla elementu pom.  
• 7 linia – Zmniejszamy j o 1, by móc porównać pom z wcześniejszymi elementami.  
• 8 linia – Po zakończeniu pętli dopóki (while) element pom zostaje wstawiony na odpowiednią pozycję w posortowanej części tablicy.

def Sortowanie_Przez_Wstawianie(zbior, n): # Opcjonalną zmianą jest usunięcie argumentu n i sprawdzenie wewnątrz funkcji jaką liczbę elementów posiada lista zbior
	for i in range(1, n):
    	pom = zbior[i]
    	j = i - 1
    	# Przesunięcie elementów większych od zawartości zmiennej pom, żeby zrobić wolne miejsce dla pom
    	while j >= 0 and zbior[j] > pom:
        	zbior[j + 1] = zbior[j]
        	j -= 1
    	# Wstawienie zmiennej pomocniczej pom na prawidłową pozycję w posortowanej części listy (tablicy)
    	zbior[j + 1] = pom
 
# Deklaracja listy wartości zbior
zbior = [5, 3, 8, 2, 1, 7]
n = len(zbior)  # Pobranie liczby elementów listy (tablicy) - funkcja len zwraca liczbę elementów jaką zawiera konkretna lista
 
# Wywołanie funkcji sortowania przez wstawianie
Sortowanie_Przez_Wstawianie(zbior, n)
 
# Wyświetlanie listy (tablicy) po wykonanym sortowaniu przez wstawianie
print("Posortowana lista:", end=" ")
for element in zbior:
    print(element, end=" ")

#include <iostream>
using namespace std;

void Sortowanie_Przez_Wstawianie(int zbior[], int n) {
    //Opcjonalną zmianą jest usunięcie argumentu n i sprawdzenie wewnątrz funkcji jaką liczbę elementów posiada tablica zbior
    for (int i = 1; i < n; i++) {
        int pom = zbior[i];
        int j = i - 1;
        // Przesunięcie elementów większych od pom, aby zrobić miejsce dla pom
        while (j >= 0 && zbior[j] > pom) {
            zbior[j + 1] = zbior[j];
            j--;
        }
        // Wstawienie zmiennej pom na odpowiednią pozycję
        zbior[j + 1] = pom;
    }
}

int main() {
    // Deklaracja zbioru wartości
    int zbior[] = {5, 3, 8, 2, 1, 7};
    int n = sizeof(zbior) / sizeof(zbior[0]);  // Pobranie liczby elementów w tablicy, sizeof zwraca wielkość całej tablicy w bajtach, więc po podzieleniu jej przez rozmiar pojedynczego elementu, można uzyskać liczbę elementów

    // Wywołanie funkcji sortowania przez wstawianie
    Sortowanie_Przez_Wstawianie(zbior, n);

    // Wyświetlanie tablicy po sortowaniu
    cout << "Posortowana tablica: ";
    for (int i = 0; i < n; i++) {
        cout << zbior[i] << " ";
    }
    cout << endl;

    return 0;
}

public class Main {

    public static void Sortowanie_Przez_Wstawianie(int[] zbior, int n) {
        // Opcjonalną zmianą jest usunięcie argumentu n i sprawdzenie wewnątrz funkcji jaką liczbę elementów posiada tablica zbior
        for (int i = 1; i < n; i++) {
            int pom = zbior[i];
            int j = i - 1;
            // Przesunięcie elementów większych od pom, aby zrobić miejsce dla pom
            while (j >= 0 && zbior[j] > pom) {
                zbior[j + 1] = zbior[j];
                j--;
            }
            // Wstawienie zmiennej pom na odpowiednią pozycję
            zbior[j + 1] = pom;
        }
    }

    public static void main(String[] args) {
        // Deklaracja zbioru wartości
        int[] zbior = {5, 3, 8, 2, 1, 7};
        int n = zbior.length;  // Pobranie liczby elementów w tablicy, funkcja length zwraca liczbę elementów tablicy

        // Wywołanie funkcji sortowania przez wstawianie
        Sortowanie_Przez_Wstawianie(zbior, n);

        // Wyświetlanie tablicy po sortowaniu
        System.out.print("Posortowana tablica: ");
        for (int i = 0; i < n; i++) {
            System.out.print(zbior[i] + " ");
        }
        System.out.println();
    }
}

Sortowanie przez wstawianie – złożoność obliczeniowa

Złożoność algorytmu sortowanie przez wstawianie to O(n²).

Dzieje się tak z powodu zastosowania dwóch pętli iterujących przez tablicę. Warto jednak zauważyć, że algorytm ten jest stosowany częściej niż sortowanie bąbelkowe czy sortowanie przez wybieranie. Ale dlaczego, skoro wszystkie trzy algorytmy mają zbliżoną złożoność czasową?

Sytuacja wygląda inaczej, gdy nasza tablica jest już posortowana przed zastosowaniem algorytmu. W przypadku sortowania przez wybieranie oraz sortowania bąbelkowego obie pętle w ich implementacjach będą nadal do końca wykonywane, co skutkuje kwadratową złożonością przy układaniu już posortowanych danych. Aby temu zapobiec, warto dodać do kodu mechanizm, który uniemożliwi przeprowadzanie zbędnych operacji dla uporządkowanych danych.

Z kolei przy sortowaniu przez wstawianie, jeśli chcemy na przykład uporządkować trzeci element względem dwóch pierwszych, to w przypadku posortowanej tablicy pętla zakończy działanie po pierwszym porównaniu trzeciego elementu z drugim i nie będzie kontynuować dalszych porównań.

Porównując każdy element w tablicy tylko raz z jego poprzednikiem, osiągniemy złożoność rzędu O(n) (czyli liniową).

To znacząca różnica i przewaga sortowania przez wstawianie w porównaniu z sortowaniem bąbelkowym i przez wybieranie. Co ciekawe, ten algorytm jest również wykorzystywany do optymalizacji działania sortowania szybkiego. Kiedy liczba elementów w tablicy jest niewielka (zazwyczaj do 20), sortowanie przez wstawianie zastępuje szybkie sortowanie, ponieważ działa szybciej, zwłaszcza w optymistycznym scenariuszu, gdy tablica jest uporządkowana lub prawie uporządkowana.

Najczęściej zadawane pytania o sortowanie przez wstawianie