Sortowanie to jedna z podstawowych operacji, które wykonujemy na obiektach. Już w dzieciństwie dzieci są uczone sortowania, gdy rozwijają swoje umiejętności myślenia. Komputery i oprogramowanie nie są wyjątkiem. Istnieje ogromna różnorodność algorytmów sortowania w Javie . Proponuję sprawdzić, czym są i jak działają. Co jeśli pewnego dnia zostaniesz zapytany o jedną z nich na rozmowie kwalifikacyjnej?
L staje się równy
Wstęp
Sortowanie elementów to jedna z kategorii algorytmów, którą musi znać programista. Jeśli informatyka nie była kiedyś traktowana poważnie, kiedy byłem w szkole, dzisiejsi uczniowie muszą być w stanie wdrożyć i zrozumieć algorytmy sortowania. Podstawowe algorytmy, najprostsze, są realizowane za pomocą pętli for . Naturalnie, aby posortować kolekcję elementów, taką jak tablica, musisz w jakiś sposób przejść przez tę kolekcję. Na przykład:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Co można powiedzieć o tym fragmencie kodu? Mamy pętlę, w której zmieniamy indeks ( int i
) od 0 do ostatniego elementu w tablicy. W rzeczywistości po prostu bierzemy każdy element z tablicy i drukujemy jego zawartość. Im więcej elementów w tablicy, tym dłużej trwa kodowanie. To znaczy, jeśli n
jest liczbą elementów, gdy n = 10
program będzie działał dwa razy dłużej niż wtedy, gdy n = 5
. Jeśli nasz program ma jedną pętlę, czas wykonania rośnie liniowo: im więcej elementów, tym dłuższy czas wykonania. Okazuje się, że powyższy algorytm działa w czasie liniowym (funkcja liniowa n). W takich przypadkach mówimy, że złożoność algorytmu wynosi „O(n)”. Ten zapis jest również nazywany „dużym O” lub „zachowaniem asymptotycznym”. Ale możesz po prostu pamiętać”
Najprostszy algorytm sortowania (sortowanie bąbelkowe)
Załóżmy, że mamy tablicę i możemy ją iterować. Świetnie. Spróbujmy teraz posortować je w porządku rosnącym. Co to znaczy? Oznacza to, że biorąc pod uwagę dwa elementy (na przykład ,a = 6
) b = 5
, musimy przestawić a
i b
jeśli a
jest większe niż b
(jeśli a > b
). Co to oznacza, gdy używamy indeksu do pracy z kolekcją (jak w przypadku tablicy)? Oznacza to, że jeśli element o indeksie a jest większy niż element o indeksie b
( array[a] > array[b]
), to elementy muszą zostać zamienione miejscami. Istnieją różne sposoby zmiany miejsca. Ale użyjemy techniki, która jest prosta, zrozumiała i łatwa do zapamiętania:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Teraz możemy napisać, co następuje:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Jak widać, elementy rzeczywiście zostały zamienione miejscami. Zaczęliśmy od indeksu 1, ponieważ jeśli tablica ma tylko jeden element, wyrażenie array[i] < array[i-1]
jest nieprawidłowe dla indeksu 0
. Takie postępowanie chroni nas również przed przypadkami, w których tablica nie ma żadnych elementów lub zawiera tylko jeden element, a dzięki temu kod wygląda lepiej. Ale wynikowa tablica nadal nie jest posortowana, ponieważ jedno przejście nie wystarcza do przeprowadzenia sortowania. Będziemy musieli dodać kolejną pętlę, w której będziemy powtarzać przebiegi, aż otrzymamy posortowaną tablicę:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Więc zakończyliśmy nasz pierwszy algorytm sortowania. Powtarzamy zewnętrzną pętlę ( while
), dopóki nie zdecydujemy, że więcej iteracji nie jest potrzebnych. Domyślnie przed każdą nową iteracją zakładamy, że nasza tablica jest posortowana i nie musimy już wykonywać pętli. W związku z tym przechodzimy kolejno przez elementy i sprawdzamy to założenie. Ale jeśli elementy nie są w porządku, to zamieniamy elementy i rozumiemy, że teraz nie mamy gwarancji, że elementy są we właściwej kolejności. Oznacza to, że musimy wykonać kolejną iterację. Załóżmy na przykład, że mamy [3, 5, 2]
. 5
jest więcej niż 3
— wszystko jest w porządku. Ale 2
jest mniejszy niż 5
. Wymaga jednak [3, 2, 5]
kolejnej przepustki, ponieważ3 > 2
i trzeba je wymienić. Ponieważ używamy pętli w pętli, zwiększa się złożoność naszego algorytmu. Biorąc pod uwagę n
elementy, staje się n * n
, czyli O(n^2)
. Nazywa się to złożonością kwadratową. Ogólnie rzecz biorąc, nie możemy dokładnie wiedzieć, ile iteracji będzie potrzebnych. Wyrażenie złożoności algorytmu pokazuje, jak wzrasta złożoność w najgorszym przypadku. Oznacza to, że wskazuje, o ile wydłuży się czas wykonania wraz ze zmianą liczby elementów n
. Sortowanie bąbelkowe jest jednym z najprostszych i najbardziej nieefektywnych algorytmów sortowania. Jest to również czasami nazywane „głupim sortem”. Materiał na ten temat:
Sortowanie przez wybór
Innym algorytmem sortowania jest sortowanie przez wybór. Ma również złożoność kwadratową, ale o tym później. Więc pomysł jest prosty. Na każdym przejściu wybieramy najmniejszy element i przesuwamy go na początek. Dodatkowo każde przejście rozpoczyna się o krok w prawo. Innymi słowy, pierwszy przebieg zaczyna się od elementu zerowego, drugi przebieg od pierwszego itd. Będzie to wyglądało tak:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
To sortowanie jest niestabilne, ponieważ identyczne elementy (pod względem dowolnej cechy, której używamy do sortowania elementów) mogą zmieniać swoje względne pozycje. Dobry przykład znajduje się w artykule w Wikipedii na temat sortowania przez wybór . Materiał na ten temat:
Sortowanie przez wstawianie
Sortowanie przez wstawianie ma również złożoność kwadratową, ponieważ ponownie mamy pętlę w pętli. Co wyróżnia sortowanie przez wstawianie? Ten algorytm sortowania jest „stabilny”. Oznacza to, że identyczne elementy nie zmienią swojej względnej kolejności. Ponownie mamy na myśli identyczne pod względem cech, według których sortujemy.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Sortowanie wahadłowe
Istnieje inny prosty algorytm sortowania: sortowanie wahadłowe. Jest to również znane jako dwukierunkowe sortowanie bąbelkowe lub sortowanie w shakerze. Te alternatywne nazwy mówią nam, że rodzaj wahadłowca nie dotyczy promu kosmicznego. Chodzi o coś, co porusza się tam iz powrotem. Teraz możesz o tym myśleć, kiedy myślisz o tym algorytmie. Jaka jest istota algorytmu? Istotą algorytmu jest to, że iterujemy od lewej do prawej, zamieniając elementy i sprawdzając, czy któryś z elementów pozostających w przeciwnym kierunku wymaga zamiany.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Materiał na ten temat:
Sortowanie skorupowe
Innym prostym algorytmem sortowania jest sortowanie skorupowe. Jego istota jest podobna do sortowania bąbelkowego, ale w każdej iteracji mamy inny odstęp między porównywanymi elementami. Przy każdej iteracji jest przecinany na pół. Oto implementacja:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
Materiał na ten temat:
Sortuj przez scalanie
Oprócz tych prostych algorytmów sortowania istnieją również bardziej skomplikowane algorytmy sortowania. Na przykład sortowanie przez scalanie. Należy zwrócić uwagę na dwie rzeczy. Po pierwsze, rekurencja przychodzi nam tutaj na ratunek. Po drugie, złożoność algorytmu nie jest już kwadratowa, do czego jesteśmy przyzwyczajeni. Złożoność tego algorytmu jest logarytmiczna. To jest napisane jakoO(n log n)
. Wprowadźmy go więc w życie. Najpierw napiszemy rekurencyjne wywołanie metody sortowania:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Teraz dodajmy główną akcję do naszej implementacji. Oto nasza super metoda:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Możemy uruchomić nasz przykład, dzwoniącmergeSort(array, 0, array.length-1)
. Jak widać, proces sprowadza się do zaakceptowania tablicy wejściowej wraz ze wskazaniem początku i końca sekcji, która ma zostać posortowana. Kiedy zaczyna się sortowanie, są to początek i koniec tablicy. Następnie obliczamy ogranicznik, czyli indeks, w którym podzielimy tablicę. Jeśli tablicę można podzielić na 2 części, to metodę sortowania wywołujemy rekurencyjnie dla dwóch połówek tablicy. Przygotowujemy bufor pomocniczy, w którym wstawimy posortowaną sekcję. Następnie ustaw indeks na początku sortowanej sekcji i zacznij przeglądać każdy element pustego bufora, wypełniając go najmniejszymi elementami. Jeśli element wskazywany przez indeks jest mniejszy niż element wskazywany przez ogranicznik, umieszczamy ten element w buforze i przesuwamy indeks. W przeciwnym razie, umieszczamy element wskazany przez ogranicznik w buforze i przesuwamy ogranicznik. Gdy tylko ogranicznik wyjdzie poza granice sortowanej sekcji lub wypełnimy całą tablicę, określony zakres jest uważany za posortowany.Materiał na ten temat:
Sortowanie liczące i sortowanie według podstawy
Innym ciekawym algorytmem sortowania jest sortowanie zliczające. Złożoność algorytmiczna wynosi tutajO(n+k)
, gdzie n
jest liczbą elementów i k
jest maksymalną wartością elementu. Ten algorytm ma jedną wadę: musimy znać minimalną i maksymalną wartość w tablicy. Oto przykład sortowania zliczającego:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Możesz zrozumieć, że jest to bardzo niewygodne, gdy musimy znać z góry wartości minimalne i maksymalne. I mamy tutaj inny algorytm: sortowanie radix. Algorytm przedstawię tutaj tylko wizualnie. Zobacz materiały uzupełniające do realizacji: Materiały:
Szybkie sortowanie
Cóż, czas na deser — szybkie sortowanie, jeden z najbardziej znanych algorytmów sortowania. Ma złożoność logarytmiczną:O(n log n)
. Ten algorytm sortowania został opracowany przez Tony'ego Hoare'a. Co ciekawe, wymyślił je mieszkając w Związku Radzieckim, gdzie studiował tłumaczenie maszynowe na Uniwersytecie Moskiewskim i opracował rosyjsko-angielskie rozmówki. Co więcej, Java używa bardziej złożonej wersji tego algorytmu w Arrays.sort
. co z Collections.sort
? Dlaczego nie przyjrzeć się, jak sprawy są sortowane „pod maską”? Oto kod:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
To wszystko jest bardzo przerażające, więc zagłębimy się w to. Dla tablicy wejściowej ( int[]
źródło) tworzymy dwa znaczniki: lewy ( L
) i prawy ( R
). Podczas pierwszego wywołania metody odpowiadają one początkowi i końcowi tablicy. Następnie identyfikujemy element przestawny, który jest trafnie nazwany pivot
. Następnie naszym zadaniem jest przesuwanie wartości mniejszych niż pivot
na lewo od pivot
, a większych — na prawo. Aby to zrobić, najpierw przesuwamy L
znacznik, aż znajdziemy wartość większą niż pivot
. Jeśli nie zostanie znaleziona mniejsza wartość, topivot
. Następnie przesuwamy
R
znacznik, aż znajdziemy wartość mniejszą niż
pivot
. Jeśli nie zostanie znaleziona większa wartość, wówczas
R
staje się równy
pivot
. Następnie, jeśli
L
znacznik znajduje się przed
R
znacznikiem lub pokrywa się z nim, wówczas próbujemy zamienić elementy, jeśli element
L
jest mniejszy niż
R
element. Następnie przesuwamy się
L
w prawo o 1 i przesuwamy
R
w lewo o 1. Kiedy
L
znacznik przesunie się poza
R
znacznik, oznacza to, że zamiana jest zakończona: mniejsze wartości są na lewo od
pivot
, większe wartości na prawo od
pivot
. Następnie wywołujemy tę samą metodę sortowania rekurencyjnie na podtablicach — od początku sortowanej sekcji do prawego znacznika i od lewego znacznika do końca sortowanej sekcji. Dlaczego od początku do prawego znacznika? Ponieważ na końcu iteracji okazuje się, że prawy znacznik przesuwa się na tyle, że staje się granicą lewej części. Ten algorytm jest bardziej złożony niż proste sortowanie, więc najlepiej go naszkicować. Weź białą kartkę i napisz: 4 2 6 7 3. Następnie napisz
pivot
na środku, czyli pod cyfrą 6. Zakreśl ją. Pod 4 wpisz
L
, a pod 3 wpisz
R
. 4 mniej niż 6, 2 mniej niż 6. W końcu przechodzimy
L
do
pivot
pozycji, ponieważ
L
nie możemy przejść obok
pivot
, zgodnie z warunkiem. Napisz ponownie 4 2 6 7 3. Zakreśl 6 (
pivot
) i umieść
L
pod nim. Teraz przesuń
R
znacznik. 3 jest mniejsze niż 6, więc umieść
R
znacznik na 3. Ponieważ 3 jest mniejsze niż 6 (
pivot
), wykonujemy
swap
. Zapisz wynik: 4 2 3 7 6. Zakreśl 6, ponieważ nadal jest to
pivot
. Znacznik
L
jest na 3.
R
Znacznik jest na 6. Pamiętaj, że przesuwamy znaczniki, dopóki
L
nie przesunie się poza
R
. Przejdź
L
do następnego numeru. Tutaj chciałbym zbadać dwie możliwości: 1) przypadek, w którym przedostatnia liczba to 7 i 2) przypadek, w którym jest to 1, a nie 7.
Jeśli przedostatnia liczba to 1: Przesuń
L
znacznik na 1, ponieważ możemy się poruszyć
L
tak długo jak
L
znacznik wskazuje na liczbę mniejszą niż
pivot
. Ale nie możemy przesunąć
R
się z 6, ponieważ R możemy przesunąć tylko wtedy, gdy
R
znacznik wskazuje na liczbę większą niż
pivot
. Nie wykonujemy a
swap
, ponieważ 1 jest mniejsze od 6. Zapisz obecną sytuację: 4 2 3 1 6. Zakreśl 6 (
pivot
).
L
przesuwa się
pivot
i przestaje się poruszać.
R
nie rusza się. Nie wykonujemy zamiany. Shift
L
i
R
o jedną pozycję. Wpisz
R
znacznik pod 1.
L
Znacznik jest poza granicami. Ponieważ
L
jest poza granicami, nic nie robimy. Ale znowu piszemy 4 2 3 1, ponieważ to jest nasza lewa strona, która jest mniejsza niż
pivot
(6). Wybierz nowy
pivot
i zacznij wszystko od nowa :)
Jeśli przedostatnia liczba to 7:Przesuń
L
znacznik na 7. Nie możemy przesunąć prawego znacznika, ponieważ wskazuje on już na oś. 7 jest większe niż
pivot
, więc wykonujemy
swap
. Zapisz wynik: 4 2 3 6 7. Zakreśl 6, ponieważ jest to
pivot
. Znacznik
L
jest teraz przesunięty na 7, a
R
znacznik na 3. Nie ma sensu sortować części od
L
końca, bo jest tylko 1 element. Jednak wysyłamy część od 4 do
R
markera do sortowania. Wybieramy
pivot
i zaczynamy wszystko od nowa :) Na pierwszy rzut oka może się wydawać, że jeśli dodamy dużo wartości równych
pivot
, to złamiesz algorytm. Ale tak nie jest. Możesz wymyślać podchwytliwe kombinacje i na papierze przekonywać się, że wszystko jest w porządku i dziwić się, że tak proste działania realizują tak niezawodny mechanizm sortowania. Jedynym minusem jest to, że ten algorytm sortowania nie jest stabilny. Ponieważ zamiana może zmienić względną kolejność identycznych elementów, jeśli jeden z nich zostanie napotkany przed
pivot
zamianą drugiego elementu na część przed
pivot
.
GO TO FULL VERSION