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?
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 njest liczbą elementów, gdy n = 10program 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ć”
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ć ai bjeśli ajest 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]. 5jest więcej niż 3— wszystko jest w porządku. Ale 2jest mniejszy niż 5. Wymaga jednak [3, 2, 5]kolejnej przepustki, ponieważ3 > 2i trzeba je wymienić. Ponieważ używamy pętli w pętli, zwiększa się złożoność naszego algorytmu. Biorąc pod uwagę nelementy, 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:
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 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));
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));
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 jako O(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:
Innym ciekawym algorytmem sortowania jest sortowanie zliczające. Złożoność algorytmiczna wynosi tutaj O(n+k), gdzie njest liczbą elementów i kjest 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:
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ż pivotna lewo od pivot, a większych — na prawo. Aby to zrobić, najpierw przesuwamy Lznacznik, aż znajdziemy wartość większą niż pivot. Jeśli nie zostanie znaleziona mniejsza wartość, to
L staje się równy
pivot. Następnie przesuwamy
Rznacznik, aż znajdziemy wartość mniejszą niż
pivot. Jeśli nie zostanie znaleziona większa wartość, wówczas
Rstaje się równy
pivot. Następnie, jeśli
Lznacznik znajduje się przed
Rznacznikiem lub pokrywa się z nim, wówczas próbujemy zamienić elementy, jeśli element
Ljest mniejszy niż
Relement. Następnie przesuwamy się
Lw prawo o 1 i przesuwamy
Rw lewo o 1. Kiedy
Lznacznik przesunie się poza
Rznacznik, 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
pivotna ś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
Ldo
pivotpozycji, ponieważ
Lnie możemy przejść obok
pivot, zgodnie z warunkiem. Napisz ponownie 4 2 6 7 3. Zakreśl 6 (
pivot) i umieść
Lpod nim. Teraz przesuń
Rznacznik. 3 jest mniejsze niż 6, więc umieść
Rznacznik 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
Ljest na 3.
RZnacznik jest na 6. Pamiętaj, że przesuwamy znaczniki, dopóki
Lnie przesunie się poza
R. Przejdź
Ldo 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ń
Lznacznik na 1, ponieważ możemy się poruszyć
Ltak długo jak
Lznacznik wskazuje na liczbę mniejszą niż
pivot. Ale nie możemy przesunąć
Rsię z 6, ponieważ R możemy przesunąć tylko wtedy, gdy
Rznacznik 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).
Lprzesuwa się
pivoti przestaje się poruszać.
Rnie rusza się. Nie wykonujemy zamiany. Shift
Li
Ro jedną pozycję. Wpisz
Rznacznik pod 1.
LZnacznik jest poza granicami. Ponieważ
Ljest 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
pivoti zacznij wszystko od nowa :)
Jeśli przedostatnia liczba to 7:Przesuń
Lznacznik 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
Ljest teraz przesunięty na 7, a
Rznacznik na 3. Nie ma sensu sortować części od
Lkońca, bo jest tylko 1 element. Jednak wysyłamy część od 4 do
Rmarkera do sortowania. Wybieramy
pivoti 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
pivotzamianą drugiego elementu na część przed
pivot.
Najważniejsze
Powyżej przyjrzeliśmy się „dżentelmeńskiemu” zestawowi algorytmów sortowania zaimplementowanych w Javie. Algorytmy są ogólnie przydatne, zarówno z perspektywy stosowanej, jak iw zakresie nauki myślenia. Niektóre są prostsze, inne bardziej skomplikowane. Mądrzy ludzie bronili swoich prac za niektórych. Dla innych pisali bardzo grube książki. Mam nadzieję, że dodatkowe materiały pomogą Ci dowiedzieć się jeszcze więcej, ponieważ ten artykuł to tylko przegląd, który już okazał się ważny. A jego celem jest zapewnienie małego wprowadzenia. Możesz również znaleźć wprowadzenie do algorytmów, jeśli czytasz
„Grokking Algorithms ”. Podoba mi się też playlista Jacka Browna:
AQA Decision 1 1.01 Tracing an Algorithm . Dla zabawy możesz zobaczyć wizualizacje algorytmów przy
sortowaniu.visualgo.net .
Volodymyr is one of those who learned Java development thanks to the CodeGym course, and after studying, got a job in our company. ...
[Przeczytaj pełną biografię]
GO TO FULL VERSION