Sortowanie przez wstawianie to jedna z często używanych operacji, które początkujący programista Java powinien znać. Chociaż tablice nie zawsze są najwygodniejszym sposobem porządkowania danych i dotyczą głównie małych liczb, koncepcja sortowania tablic ma mnóstwo zastosowań w złożonym oprogramowaniu i nauce o danych. W tym wpisie przyjrzymy się bliżej, czym jest sortowanie przez wstawianie. Dołączyliśmy kilka przykładów i problemów w praktyce, które pomogą ci w pełni zrozumieć tę koncepcję.

Czym jest sortowanie przez wstawianie?

Zasadniczo, sortowanie przez proste wstawianie jest algorytmem używanym przez programistów do organizowania ciągów małych liczb. Dzieli wszystkie wartości na dwa stosy - posortowany i nieposortowany. Liczby z "nieposortowanego" stosu są wybierane jedna za drugą i ustawiane we właściwej kolejności.Sortowanie przez wstawianie w Javie - Insertion Sort - 1Przyjrzyjmy się bliżej danym wejściowym i wyjściowym sortowania przez wstawianie:
  • Dane wejściowe: tablica A zawierająca nieposortowane elementy numeryczne: A[0,1, n, n-2...].
  • Dane wyjściowe: tablica zawierająca te same liczby, ale w pełni posortowane. Jest zwykle określana jako B: B[0]B[1]...B[n-1].
Istnieje kilka sposobów na wykorzystanie sortowania przez wstawianie - oto najpopularniejsze z nich:
  • Sortowanie numeryczne (w kolejności rosnącej): [1, 2, 3, 4, 5]
  • Sortowanie numeryczne (kolejność malejąca): [5, 4, 3, 2, 1]
  • Sortowanie alfabetyczne: [a, b, c, d]
Uwaga: jeśli masz pustą tablicę lub singleton, są one domyślnie uznane za posortowane.

Zrozumienie teorii sortowania przez wstawianie

Przed zapoznaniem się z kodem sortowania przez wstawianie przeanalizujmy algorytm, używając nietechnicznego języka. Ponieważ będziemy pokazywać kod sortowania w porządku rosnącym, sensowne będzie wyjaśnianie algorytmu krok po kroku w tym wpisie. Krok 1. Iteracja między arr[1] i arr[n], gdzie n jest wartością liczbową zwykle mniejszą niż 10. Krok 2. Porównaj wybrany przez siebie element (znany jako key) z poprzednią liczbą w sekwencji za pomocą metody sort(). Krok 3. Jeśli wszystkie elementy są mniejsze od elementów po nich następujących, powtarzaj porównanie, aż znajdziesz większą wartość. Krok 4. Zamień większą wartość o jedną pozycję poza mniejszą, aby utworzyć uporządkowaną sekwencję. Krok 5. Powtarzaj ten proces, aż otrzymasz posortowany ciąg znaków.

Sortowanie tablic typów pierwotnych

Ponieważ algorytm ten jest jedną z najprostszych operacji w Javie, nawet początkujący nie powinni mieć większych problemów z jego implementacją. Oto przewodnik krok po kroku sortowania tablicy:

1. Zadeklaruj tablicę do sortowania

Na początek stwórzmy ciąg wartości, które będziemy później wyświetlać za pomocą Javy. Aby skorzystać z sortowania przez wstawianie, musisz utworzyć tablicę. W tym celu należy użyć int[]
int[] arrayA = {10, 14, 20, 30};

2. Użyj sort_arr, aby zaimplementować algorytm

Metoda sort_arr jest jednym z najbardziej popularnych sposobów implementacji sortowania przez wstawianie. W praktyce wygląda to tak:
for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Utwórz pętlę i iterator

Używając pętli w algorytmie sortowania przez wstawianie, programiści nie muszą powtarzać logiki dla każdego elementu. Chociaż tworzenie pętli wydaje się skomplikowane, jest to dość proste - oto przykład:
for(int i=0; i< sort_arr.length; ++i){
Teraz, gdy masz już działającą pętlę, nadszedł czas, aby utworzyć iterator, który posortuje wszystkie elementy w żądanej kolejności. Od tej pory będziemy określać iterator jako "j".
int j = i;

4. Tworzenie "pętli while"

Jeśli chodzi o sortowanie przez wstawianie, pętla "while" jest niezbędna do uzyskania nowej, posortowanej tablicy. Aby skonfigurować ją dla sortowania rosnącego, programista musi spełnić dwa warunki:
  • Wartość przypisana do j musi być większa niż 0
  • Wartość przypisana do j-1 musi być większa niż indeks j
Gdy tylko oba warunki pętli while są spełnione, wartość klucza tablicy będzie równa indeksowi j.

5. Sortowanie tablicy

Po utworzeniu pętli while wartości j i j-1 będą zamieniane tak długo, aż jeden lub oba warunki w pętli while zakończą się niepowodzeniem. Podobnie sortowanie będzie powtarzane dla każdej wartości w pętli for, dopóki warunki pętli for również nie zakończą się niepowodzeniem. Oto jak działa sortowanie przez wstawianie w praktyce:
int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;
Sortowanie przez wstawianie w Javie - Insertion Sort - 2

Sortowanie ArrayList

Chociaż zrozumienie matematyki stojącej za sortowaniem przez wstawianie jest ważne, jeśli chodzi o tworzenie oprogramowania w prawdziwym życiu, sortowanie ArrayLists będzie znacznie częściej używane niż sekwencje w tablicach typów pierwotnych. Oto przewodnik krok po kroku sortowania ArrayList:
  1. Utwórz nową klasę Element dla elementów należących do kolekcji.

    public class Element {
        private int id;
    
        public Element(int id) {
            this.id = id;
        }

  2. Wewnątrz kolekcji znajduje się metoda compareTo() - użyjemy jej do porównania identyfikatorów dwóch elementów.

    public int compareTo(Element element) {
            int res = 0;
            if (this.id < element.getId()) {
                res = -1;
            }
            if (this.id > element.getId()) {
                res = 1;
            }
            return res;
        }
    }

  3. Zastosuj algorytm i utwórz pętle, aby posortować obiekty w ArrayList zamiast je porównywać.

    public static void insertionSortArrayList(List<element> list) {
        for (int j = 1; j < list.size(); j++) {
            Element current = list.get(j);
            int i = j-1;
            while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
                list.set(i+1, list.get(i));
                i--;
            }
            list.set(i+1, current);
        }
    }

  4. Możesz dodać również więcej elementów do ArrayList, jak pokazano poniżej:

    List<element> list = new ArrayList<>();
    
    // Create elements w/ IDs 0-24
    for (int i = 0; i < 25; i++) {
        list.add(new Element(i));
    }
    
    // To use insertion sort, shuffle the values
    Collections.shuffle(list);

  5. Teraz czas na sortowanie:

    // This helps print values before sorting
    list.forEach(e -> System.out.print(e.getId() + ", "));
    
    // Sort the list
    insertionSortArrayList(list);
    
    System.out.println();
    
    // Display a sorted array
    list.forEach(e -> System.out.print(e.getId() + ", "));

  6. Porównajmy teraz dane wejściowe i wyjściowe, aby upewnić się, że nie popełniliśmy błędów. Oto zestawienie ciągu, którego użyliśmy jako przykładu.

    4, 2, 6, 7, 0, 5, 9, 1, 8, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

Problemy praktyczne związane z sortowaniem przez wstawianie

Teraz, gdy znasz już ten algorytm sortowania, nadszedł czas, aby sprawdzić swoje umiejętności teoretyczne i praktyczne. Quiz z teorii #1 Otrzymujesz tablicę [1, 4, 6, 8] i dodajesz do niej nowy element n = 7. Jaka jest liczba porównań, które trzeba wykonać, aby otrzymać posortowany ciąg liczb? Wskaż końcową wartość indeksu n w tablicy. Quiz z teorii #2 Podczas rozmowy kwalifikacyjnej kierownik zespołu prosi cię o udowodnienie, że sortowanie przez wstawianie jest metodą nieefektywną. Biorąc pod uwagę ciąg liczbowy [0, 3, 6, 8, 9], jaka powinna być kolejność sekwencji wejściowej, aby zmaksymalizować czas potrzebny na sortowanie? Problem praktyczny Sortuj tablicę [0, 1, 4, 5, 2, 3, 7, 9, 8] rosnąco za pomocą sortowania przez wstawianie w Javie.

Wniosek

Największym wyzwaniem zrozumienia sortowania przez wstawianie jest pojęcie, jak działa ten proces. Kiedy już to zrozumiesz, przekształcenie szablonu w kod to bułka z masłem. Jeśli tylko będziesz ćwiczyć i z czasem powracać do odpowiednich zadań, szybko poprawisz swoją umiejętność sortowania przez wstawianie.
Ten artykuł przeczytasz także po angielsku.
Read the English version of this article to see what insertion sort looks like in Java.