Sortowanie wyboru Java Program z przykładem
⚡ Inteligentne podsumowanie
Sortowanie przez wybór w Java wielokrotnie skanuje nieposortowaną część tablicy, znajduje najmniejszą pozostałą wartość i umieszcza ją w odpowiedniej pozycji, kończąc pracę przy maksymalnie n-1 zamianach, niezależnie od kolejności wprowadzania danych.
Jak działa sortowanie przez wybór?
Sortowanie przez wybór implementuje prosty algorytm sortowania w następujący sposób:
- Algorytm wielokrotnie wyszukuje najniższy element.
- Zamień bieżący element na element o najniższej wartości
- Przy każdej iteracji/przejściu sortowania przez wybór elementy są zamieniane.
Każde przejście traktuje zatem szyk jako dwa obszary: posortowany blok rosnący od lewej i niesortowany blok kurczący się po prawej. Algorytm przechodzi przez niesortowany blok, zapamiętuje indeks najmniejszej napotkanej wartości i zamienia tę wartość z pierwszą niesortowaną pozycją.
Ponieważ w jednym przejściu następuje tylko jedna wymiana, tablica n elementów jest porządkowana po maksymalnie n-1 zamianach. Ta właściwość odróżnia tę procedurę od innych procedur dla początkujących. Java algorytmy sortowania, które znacznie częściej przenoszą dane.
tracPoniższy przykład jest następcą tablicy {860, 8, 200, 9} dokładnie tak, jak program w następnej sekcji drukuje ją w czasie wykonywania.
| Przechodzić | Porównania wydrukowane | Najmniejsza znaleziona wartość | Tablica po zamianie |
|---|---|---|---|
| Rozpocznij | Do | Do | 860 8 200 9 |
| 1 | 860 i 8, 8 i 200, 8 i 9 | 8 | 8 860 200 9 |
| 2 | 860 i 200, 200 i 9 | 9 | 8 9 200 860 |
| 3 | 200 i 860 | 200 | 8 9 200 860 |
Dwa szczegóły w tym tracWarto się nad nimi zatrzymać. Po pierwsze, przebieg 3 nadal zgłasza zamianę, mimo że kolejność się nie zmienia, ponieważ najmniejsza pozostała wartość znajduje się już pod bieżącym indeksem, a program wymienia element ze sobą. Po drugie, liczba porównań spada o jeden w każdym przebiegu (trzy, potem dwa, a potem jedno), co jest wzorcem leżącym u podstaw liczb złożoności przedstawionych dalej na stronie.
Java Program do implementacji sortowania przez wybór
Poniższa klasa nosi nazwę SelectionSortAlgo i znajduje się w pakiecie com.guru99. Metoda main() deklaruje tablicę przykładową, drukuje ją, przekazuje do selection() w celu sortowania i ponownie drukuje. Funkcja pomocnicza printArray() zapisuje wszystkie elementy w jednym wierszu, co generuje czytelny dziennik przejść pominiętych.
Wewnątrz funkcji selection() pętla zewnętrzna zaznacza granicę między obszarami sortowanymi i nieposortowanymi, zmienna index przechowuje pozycję najmniejszej wartości widzianej do tej pory, a trzy przypisania na końcu każdego przebiegu wykonują zamianę.
package com.guru99; public class SelectionSortAlgo { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("------Before Selection Sort-----"); printArray(myArray); selection(myArray);//sorting array using selection sort System.out.println("-----After Selection Sort-----"); printArray(myArray); } public static void selection(int[] array) { for (int i = 0; i < array.length - 1; i++) { System.out.println("Sort Pass Number "+(i+1)); int index = i; for (int j = i + 1; j < array.length; j++) { System.out.println("Comparing "+ array[index] + " and " + array[j]); if (array[j] < array[index]){ System.out.println(array[index] + " is greater than " + array[j] ); index = j; } } int smallerNumber = array[index]; array[index] = array[i]; array[i] = smallerNumber; System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Wyjście:
Skompilowanie i uruchomienie klasy generuje poniższy dziennik konsoli, zawierający jeden blok danych wyjściowych na przejście.
------Before Selection Sort----- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Comparing 8 and 200 Comparing 8 and 9 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 860 and 200 860 is greater than 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 9 200 860 -----After Selection Sort----- 8 9 200 860
Początkujący napotykają dwa problemy, gdy uruchamiają ten przykład po raz pierwszy. Ponieważ plik deklaruje package com.guru99;źródło musi znajdować się w pasującym com/guru99 katalogu, w przeciwnym razie kompilator zgłosi niezgodność nazwy pakietu lub klasy. Klasę należy wówczas uruchomić za pomocą jej pełnej nazwy kwalifikowanej, java com.guru99.SelectionSortAlgo, ponieważ zwykły java SelectionSortAlgo podnosi wyjątek NoClassDefFoundError.
Granice pętli to kolejna częsta pułapka. Pętla zewnętrzna zatrzymuje się na array.length - 1 a wewnętrzna pętla zaczyna się od i + 1; zmiana którejkolwiek z granic powoduje dodatkowe puste przejście lub wyjątek ArrayIndexOutOfBoundsException.
Złożoność czasowa i przestrzenna sortowania przez wybieranie
Pętla wewnętrzna w programie zawsze przebiega do końca tablicy, więc algorytm wykonuje tę samą liczbę porównań, niezależnie od wyglądu danych. Dla tablicy n-elementowej suma wynosi n(n-1)/2, co dla próbki czteroelementowej daje sześć, a powyższy wynik rzeczywiście wyświetla dokładnie sześć wierszy porównania.
| Walizka | Porównania | Swapy | Złożoność czasowa | Przestrzeń pomocnicza |
|---|---|---|---|---|
| Najlepszy (tablica już posortowana) | n(n-1)/2 | n-1 | O(n²) | O (1) |
| Średnia (kolejność losowa) | n(n-1)/2 | n-1 | O(n²) | O (1) |
| Najgorsze (sortowanie odwrotne) | n(n-1)/2 | n-1 | O(n²) | O (1) |
Z tego jednolitego szeregu cyfr wynikają trzy konsekwencje:
- Sortowanie przez wybór nie jest adaptacyjne. Posortowane dane wejściowe kosztują dokładnie tyle samo, co dane wejściowe odwrócone, więc nie ma skrótu do wcześniejszego wyjścia. sortowanie bąbelkowe oferuje.
- Liczba wymian to mocna strona algorytmu. Maksymalnie odbywa się n-1 wymian, czyli znacznie mniej niż kwadratowa liczba ruchów, jaką mogą wykonać inne proste algorytmy.
- Użycie pamięci jest stałe. Potrzebne są tylko liczniki pętli oraz dwie zmienne tymczasowe: index i lessNumber, więc przestrzeń pomocnicza zajmuje O(1), a sortowanie odbywa się w miejscu.
Wzrost kwadratowy to praktyczna granica. Podwojenie rozmiaru tablicy mniej więcej czterokrotnie zwiększa nakład pracy porównawczej, dlatego sortowanie przez wybieranie sprawdza się w nauczaniu, małych tablicach i kodzie wbudowanym, a nie w zbiorach danych produkcyjnych, gdzie właściwym wyborem są algorytmy O(n log n).
Zalety i wady sortowania przez selekcję
Zrozumienie, kiedy algorytm pomaga, a kiedy przeszkadza, ułatwia podjęcie decyzji, kiedy warto po niego sięgnąć.
Zalety
- Logika jest krótka i czytelna, dlatego stanowi standardowe pierwsze ćwiczenie sortujące sortowanie przez wstawianie.
- Sortuje w miejscu, dzięki czemu nie jest przydzielana druga tablica, a użycie pamięci nie rośnie wraz z danymi wejściowymi.
- Wykonuje maksymalnie n-1 operacji zapisu do tablicy, co ma znaczenie w przypadku pamięci masowej, w których operacje zapisu są powolne lub powodują zużycie nośnika.
- Czas wykonania jest całkowicie przewidywalny, ponieważ liczba porównań zależy wyłącznie od długości tablicy.
Wady
- Każdy przypadek jest O(n²), więc algorytm nie skaluje się do dużych zbiorów.
- Nie jest w stanie wykryć, że tablica jest już posortowana, dlatego nigdy nie kończy pracy przed czasem.
- Klasyczna forma pokazana powyżej jest niestabilna, więc dwie równe wartości mogą pojawić się w odwrotnej kolejności.
- Porównuje dane niemal uporządkowane częściej niż sortowanie przez wstawianie, podczas gdy sortowanie przez wstawianie zbliża się do czasu liniowego.
Krótko mówiąc, wybieraj sortowanie przez wybór, gdy tablica jest mała i każdy zapis jest kosztowny, a unikaj tej opcji, gdy zbiór danych jest duży lub prawie gotowy do posortowania.
Sortowanie przez wybór vs. BubblSortowanie e vs. sortowanie przez wstawianie
Wszystkie trzy algorytmy są kwadratowymi algorytmami sortującymi przez porównanie w miejscu, jednak zachowują się inaczej, gdy zmienia się kształt danych wejściowych.
| Kryterium | Sortowanie wyboru | Bubblsortowanie | Sortowanie przez wstawianie |
|---|---|---|---|
| Najlepszy czas | O(n²) | Na) | Na) |
| Średni i najgorszy czas | O(n²) | O(n²) | O(n²) |
| W najgorszym przypadku zamiany lub przesunięcia | n-1 swapów | n(n-1)/2 zamian | Do n(n-1)/2 zmian |
| Stabilny | Nie | Tak | Tak |
| Adaptacja do posortowanego wejścia | Nie | Tak | Tak |
| Przestrzeń pomocnicza | O (1) | O (1) | O (1) |
| Typowe zastosowanie | Najmniej wymaganych zapisów | Nauczanie i wyszukiwanie posortowanych danych | Małe lub prawie posortowane tablice |
Tabela wyjaśnia typową odpowiedź udzielaną podczas rozmowy kwalifikacyjnej. Sortowanie przez wybór wygrywa pod względem liczby wymian, sortowanie bąbelkowe wygrywa pod względem rozpoznawania danych wejściowych, które są już uporządkowane, a sortowanie przez wstawianie jest zazwyczaj najszybsze z tych trzech w praktyce, ponieważ rzeczywiste dane są często częściowo posortowane. Żadne z nich nie konkuruje z sortowaniem przez scalanie ani sortowaniem szybkim, gdy tablica przekroczy kilkadziesiąt elementów.
