Wprowadzenie do sortowania wstawianego w Javie
Jeśli jesteś programistą, musiałeś już dużo słyszeć o sortowaniu. Sortowanie polega zasadniczo na ułożeniu elementów w porządku rosnącym lub malejącym. Dostępnych jest tak wiele algorytmów sortowania do sortowania elementów, a każdy algorytm ma inne sposoby sortowania, różną złożoność. Zależy więc od konkretnego scenariusza i liczby elementów, który algorytm powinien zostać użyty. Wstawianie jest również jednym z najczęściej używanych algorytmów sortowania o złożoności O (n 2) w ogólności i jest wykonywane tak, jakbyśmy sortowali karty do gry w naszych rękach. W tym temacie dowiemy się o sortowaniu wstawianym w Javie.
Jak działa sortowanie wstawiane w Javie?
Przyjrzyjmy się działaniu sortowania wstawiania na przykładzie. Załóżmy, że istnieje tablica o nazwie arr zawierająca niżej wymienione elementy:
10 5 8 20 30 2 9 7
Krok # 1 - Sortowanie wstawiania rozpoczyna się od drugiego elementu tablicy, tj. 5, biorąc pod uwagę pierwszy element tablicy zestawiony sam w sobie. Teraz element 5 jest porównywany z 10, ponieważ 5 jest mniejszy niż 10, więc 10 jest przesuwane o 1 pozycję do przodu, a 5 jest wstawiane przed nim.
Teraz wynikowa tablica to:
5 10 8 20 30 2 9 7
Krok # 2 - Teraz element arr (2), tj. 8, jest porównywany z elementem arr (1), tj. 10. Ponieważ 8 jest mniejszy niż jego poprzedni element 10, przesuwa się o krok do przodu od swojej pozycji, a następnie jest w porównaniu z 5. Ponieważ 8 jest większe niż 5, więc jest wstawiane po nim.
Wynikowa tablica to:
5 8 10 20 30 2 9 7
Krok # 3 - Teraz element 20 jest porównywany z 10, ponieważ jest większy niż 10, pozostaje na swoim miejscu.
5 8 10 20 30 2 9 7
Krok # 4 - Element 30 jest porównywany z 20, a ponieważ jest większy niż 20, nie zostaną wprowadzone żadne zmiany, a tablica pozostanie bez zmian. Teraz tablica byłaby
5 8 10 20 30 2 9 7
Krok # 5 - Element 2 jest porównywany z 30, ponieważ jest mniejszy niż 30, jest przesuwany o jedną pozycję do przodu, a następnie porównywany z 20, 10, 8, 5, jeden po drugim, a wszystkie elementy są przesuwane do 1 pozycji do przodu i 2 dodaje się przed 5.
Wynikowa tablica to:
2 5 8 10 20 30 9 7
Krok # 6 - Element 9 jest porównywany z 30, ponieważ jest mniejszy niż 30, jest porównywany z 20, 10 jeden po drugim, a element zostaje przesunięty o 1 pozycję do przodu, a 9 jest wstawiany przed 10 i po 8. Wynikowa tablica to:
2 5 8 9 10 20 30 7
Krok 7 - Element 7 jest porównywany z 30, a ponieważ jest mniejszy niż 30, jest porównywany z 30, 20, 10, 9, 8, a wszystkie elementy są przesuwane o 1 pozycję do przodu jeden po drugim, a 7 jest wstawiane przed 8 Wynikowa tablica wyglądałaby następująco:
2 5 7 8 9 10 20 30
W ten sposób wszystkie elementy tablicy są sortowane za pomocą sortowania wstawianego, rozpoczynając porównanie z poprzednim elementem.
Przykłady implementacji sortowania wstawiania w Javie
Wstawianie Sortuj w Javie to prosty algorytm sortowania odpowiedni dla wszystkich małych zestawów danych.
public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)
Wynik:
12 15 18 21 23 52 61
Wyjaśnienie:
W powyższym programie Insertion Sort funkcja insertionSort () służy do sortowania elementów oryginalnej tablicy. Sortowanie rozpoczyna się od drugiego elementu, ponieważ pierwszy element uważa się za posortowany sam w sobie. Pętla „j” zaczyna się od indeksu 1 tablicy. „i” to zmienna śledząca indeks tuż przed „j” w celu porównania wartości. ” klucz ”to zmienna przechowująca wartość bieżącego elementu, który ma być ustawiony w pozycji posortowanej. pętla while () jest wykonywana, jeśli bieżąca wartość jest mniejsza niż wartość skrajnie lewa, aby można było przetwarzać przesunięcie elementów, a na końcu można wstawić bieżący element we właściwej pozycji. Funkcja printArray () służy do ostatecznego wydrukowania posortowanej tablicy.
1. Najlepszy przypadek
W sortowaniu wstawiania najlepszym przypadkiem byłoby, gdy wszystkie elementy tablicy są już posortowane. Tak więc, gdy dowolny element jest porównywany z jego najbardziej wysuniętym na lewo elementem, jest on zawsze większy i dlatego nie będzie przetwarzane przesunięcie i wstawianie elementów. W takim przypadku złożoność najlepszego przypadku byłaby liniowa, tj. O (n).
2. Najgorszy przypadek
W powyższym kodzie sortowania wstawiania najgorszym przypadkiem jest sytuacja, gdy tablica jest w odwrotnej kolejności, więc za każdym razem, gdy element jest porównywany z jego najbardziej wysuniętym na lewo elementem, jest on zawsze mniejszy, a następnie porównywany ze wszystkimi zachodzącymi i przesuwającymi się elementami i wstawianie jest zakończone. W tym przypadku złożoność sortowania przez wstawianie wynosi O (n 2).
3. Średnia sprawa
Nawet w przeciętnym przypadku sortowanie wstawiania ma złożoność O (n 2), w której niektóre elementy nie wymagają przesunięcia, podczas gdy niektóre elementy są przesuwane z ich pozycji i wstawianie w odpowiedniej pozycji jest wykonywane.
4. Najlepsze wykorzystanie
Sortowania wstawiania najlepiej używać, gdy rozmiar tablicy nie jest zbyt duży lub tylko niewielka liczba elementów musi być posortowana, w której prawie wszystkie elementy są sortowane i tylko niektóre zmiany muszą zostać wprowadzone. Sortowanie wstawiania jest jednym z najszybszych algorytmów dla tablic o małych rozmiarach, nawet szybszym niż szybkie sortowanie. W rzeczywistości quicksort używa sortowania wstawianego podczas sortowania małych części tablicy.
Wniosek
Powyższe wyjaśnienie wyraźnie pokazuje działanie i implementację sortowania wstawianego w Javie. Również w innych językach programowania logika wykonywania sortowania wstawianego pozostaje taka sama, tylko zmiany składniowe. Przed wdrożeniem jakiegokolwiek algorytmu sortowania bardzo ważne jest przeprowadzenie analizy scenariusza, w którym należy wykonać sortowanie, ponieważ nie każdy algorytm sortowania pasuje do wszystkich scenariuszy.
Polecane artykuły
Jest to przewodnik po sortowaniu wstawianym w Javie. Tutaj omawiamy, jak działa sortowanie wstawiane w Javie z Przykładami implementacji sortowania wstawianego w Javie. Możesz także zapoznać się z następującymi artykułami, aby dowiedzieć się więcej -
- Pierwiastek kwadratowy w Javie
- BorderLayout w Javie
- Odwrotna liczba w Javie
- StringBuffer w Javie
- Pierwiastek kwadratowy w PHP
- Pierwiastek kwadratowy w JavaScript
- Przewodnik po najlepszych 6 algorytmach sortowania w Pythonie