Sortowanie przez wstawianie, Insertion Sort

Sortowanie przez wstawianie – Czy zdarzyło Ci się grać w karty🃏🃏 np. klasyczną wojnę karcianą⚔️? Ja taką grę, po rozdaniu kart zaczynam od układania ich, idąc po kolei, wrzucając najniższe na odpowiednie miejsce. Jeśli również i Ty tak robisz, to muszę Cię poinformować, że pierwsze kroki 👣 w sortowaniu przez wstawianie masz już za sobą :). Sortowanie przez wstawianie jest jednym z najprostszych algorytmów — dlatego warto go poznać na początku swojej przygody z algorytmami 🙂

Java – Sortowanie przez wstawianie – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest sortowanie?
• Czym jest algorytm sortowania?
• Czym jest sortowanie przez wstawianie?
• Jaka jest historia sortowania przez wstawianie?
• Jak zaimplementować sortowanie przez wstawianie?

Sortowanie

Sortowanie to po prostu uporządkowanie zbioru danych względem pewnych cech charakterystycznych elementów w zbiorze. Istnieją różne algorytmy sortowania, które w zależności od potrzeb, można zastosować chcąc posortować elementy w kolekcji.

Algorytm sortowania

Algorytm sortowania to algorytm, który umieszcza elementy listy lub tablicy w określonej kolejności, zwykle w porządku numerycznym lub leksykograficznym. Istnieje wiele dostępnych algorytmów sortowania, z których każdy ma swoje zalety i wady pod względem wydajności, prostoty i wykorzystania pamięci.

Sortowanie przez wstawianie (ang. insertion sort)

Sortowanie przez wstawianie jest prostym algorytmem sortowania, który sortuje tablicę poprzez wielokrotne wstawianie kolejnego elementu na właściwą pozycję posortowanych już elementów.

Sortowanie przez wstawianie – Historia

Sortowanie przez wstawianie jest jednym z najwcześniejszych algorytmów sortowania i jest używany od wieków. Algorytm ten był pierwotnie używany w grach karcianych, gdzie gracze sortowali swoją ręką karty, wkładając nowe karty do odpowiedniej pozycji w ręce.

Najwcześniejsze zarejestrowane odniesienie do Insertion Sort pochodzi z XIV wieku, z książki „The Art of Computer Programming” autorstwa Abu Ja’far Muhammad ibn Musa al-Khwarizmi, perskiego matematyka i astronoma.

Pomimo rozwoju bardziej wydajnych algorytmów sortowania na przestrzeni lat, Insertion Sort nadal jest używany w niektórych aplikacjach np. jako część bardziej złożonych algorytmów sortowania, takich jak Timsort i Shell Sort.

Sortowanie przez wstawianie – Algorytm

Algorytm sortowania przez wstawianie, podczas iteracji wstawia każdy element na jego właściwą pozycję. Przy każdej iteracji element jest porównywany ze wcześniejszymi elementami, aż do znalezienia prawidłowej pozycji, następnie elementy po lewej stronie są przesuwane, aby zrobić miejsce dla nowego elementu.

Sortowanie przez wstawianie – Java

Skoro już wiemy, na czym polega algorytm sortowania przez wstawianie, czas przyjrzeć się i zrozumieć implementację tego algorytmu.

public class InsertionSort {

    public static void sort(int[] arr) {
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

W powyższym kodzie wstawiamy każdy element na jego prawidłową pozycję, poprzez porównanie go ze wcześniejszymi posortowanymi elementami.

Zewnętrzna pętla rozpoczyna się od drugiego elementu (indeks 1) tablicy i kontynuuje do końca tablicy.

Bieżący element zewnętrznej pętli jest przechowywany w kluczu.

Pętla wewnętrzna (while) iteruje wstecz w kierunku początku tablicy, aż do jego osiągnięcia lub znalezienia elementu mniejszego, lub równego kluczowi.

Pętla zewnętrzna jest kontynuowana do momentu przetworzenia wszystkich elementów.

Kurs Java – Darmowy Kurs Programowania w Javie

W ramach tego materiału skupiliśmy się na algorytmie sortowania przez wstawianie. Jeżeli chcesz kontynuować swoją przygodę z Javą i poznać różne struktury, które oferuję ten język programowania – to zapraszam do zapoznania się z różnymi tematami z serii o Javie.
➡ ZOBACZ 👉: Kurs Java | Darmowy Kurs Programowania w Javie

Sortowanie przez wstawianie – Kiedy stosować

Zanim zdecydujesz się na zastosowanie algorytmu sortowania przez wstawianie, sprawdźmy kiedy tak naprawdę warto stosować ten algorytm:

• Przez swoją prostotę w implementacji i zrozumieniu, idealnie nadaje się na początku nauki zagadnienia algorytmów.
• Wydajny dla małych rozmiarów wejściowych lub dla prawie posortowanych tablic.
• Może być zaimplementowany jako algorytm sortowania in-place, co oznacza, że nie wymaga dodatkowej pamięci do sortowania tablicy wejściowej.
• Ze względu na jego złożoność czasową O(n^2), może być powolny i nieefektywny dla dużych list lub tablic i zazwyczaj nie jest używany w kodzie produkcyjnym.
• W przypadku dużych rozmiarów danych wejściowych lub aplikacji, w których wydajność sortowania jest krytyczna, zaleca się stosowanie bardziej zaawansowanych algorytmów, takich jak Quick Sort lub Merge Sort.

Sortowanie przez wstawianie – Podsumowanie

W ramach tego materiału dowiedzieliśmy się, czym jest sortowanie przez wstawianie. Przyjrzeliśmy się bliżej działaniu tego prostego algorytmu i jego implementacji.

Wiemy, że sortowanie przez wstawianie działa poprzez iteracyjne wstawianie każdego elementu na jego właściwą pozycję w posortowanych na lewo od niego elementach.

Algorytm ten jest często używany w bardziej złożonych algorytmach i jest dobrym algorytmem do poznania dla osób rozpoczynających swoją naukę o algorytmach sortowania.