Sortarea este una dintre operațiunile de bază pe care le efectuăm asupra obiectelor. Chiar și în copilărie, copiii sunt învățați să sorteze pe măsură ce își dezvoltă abilitățile de gândire. Calculatoarele și software-ul nu fac excepție. Există o mare varietate de algoritmi de sortare în Java . Vă sugerez să verificați care sunt și cum funcționează. Ce se întâmplă dacă ești întrebat despre unul dintre ei la un interviu într-o zi?
Introducere
Sortarea elementelor este una dintre categoriile de algoritmi pe care un dezvoltator trebuie să le cunoască. Dacă informatica nu era luată în serios când eram la școală, elevii de astăzi trebuie să fie capabili să implementeze și să înțeleagă algoritmi de sortare. Algoritmii de bază, cei mai simpli, sunt implementați folosind o buclă for . Desigur, pentru a sorta o colecție de elemente, cum ar fi o matrice, trebuie să parcurgeți cumva colecția. De exemplu:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Ce se poate spune despre acest segment de cod? Avem o buclă în care schimbăm indicele ( int i) de la 0 la ultimul element din matrice. De fapt, pur și simplu luăm fiecare element din matrice și îi imprimăm conținutul. Cu cât mai multe elemente în matrice, cu atât codul va dura mai mult pentru a se termina. Adică, dacă neste numărul de elemente, atunci când n = 10programul va dura de două ori mai mult decât atunci când n = 5. Dacă programul nostru are o singură buclă, timpul de execuție crește liniar: cu cât sunt mai multe elemente, cu atât timpul de execuție este mai lung. Se pare că algoritmul de mai sus funcționează în timp liniar (o funcție liniară a lui n). În astfel de cazuri, spunem că complexitatea algoritmului este „O(n)”. Această notație se mai numește „O mare” sau „comportament asimptotic”. Dar îți poți aminti doar"
Cel mai simplu algoritm de sortare (sortare cu bule)
Să presupunem că avem o matrice și putem itera prin ea. Grozav. Acum să încercăm să-l sortăm în ordine crescătoare. Ce înseamnă acest lucru? Înseamnă că având în vedere două elemente (de exemplu, a = 6, b = 5), trebuie să rearanjam ași bdacă aeste mai mare decât b(dacă a > b). Ce înseamnă asta când folosim un index pentru a lucra cu o colecție (cum este cazul unei matrice)? Înseamnă că dacă elementul cu indice a este mai mare decât elementul cu indice b( array[a] > array[b]), atunci elementele trebuie schimbate. Există diferite moduri de a schimba locurile. Dar vom folosi o tehnică simplă, de înțeles și ușor de reținut:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Acum putem scrie următoarele:
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));
După cum puteți vedea, elementele au fost într-adevăr schimbate. Am început cu indexul 1, deoarece dacă tabloul are un singur element, expresia array[i] < array[i-1]este invalidă pentru index 0. Făcând acest lucru, ne protejează și de cazurile în care matricea nu are elemente sau doar un element și face ca codul să arate mai bine. Dar matricea rezultată încă nu este sortată, deoarece o singură trecere nu este suficientă pentru a face sortarea. Va trebui să adăugăm o altă buclă în care vom efectua treceri din nou și din nou până când obținem o matrice sortată:
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));
Așa că am terminat primul nostru algoritm de sortare. Repetăm bucla exterioară ( while) până când decidem că nu mai sunt necesare iterații. În mod implicit, înainte de fiecare nouă iterație, presupunem că matricea noastră este sortată și nu mai trebuie să facem bucla. În consecință, ne deplasăm secvențial printre elemente și verificăm această ipoteză. Dar dacă elementele nu sunt în ordine, atunci schimbăm elemente și înțelegem că acum nu avem nicio garanție că elementele sunt în ordinea corectă. Aceasta înseamnă că trebuie să facem o altă iterație. De exemplu, să presupunem că avem [3, 5, 2]. 5este mai mult decât 3— totul este bine. Dar 2este mai puțin de 5. Cu toate acestea, [3, 2, 5]necesită o altă trecere, deoarece3 > 2și trebuie schimbate. Deoarece folosim o buclă în cadrul unei bucle, complexitatea algoritmului nostru crește. Datele nelemente, devine n * n, adică O(n^2). Aceasta se numește complexitate pătratică. În general, nu putem ști exact de câte iterații vor fi necesare. Expresia complexității unui algoritm arată cum complexitatea crește în cel mai rău caz. Adică indică cât de mult va crește timpul de execuție pe măsură ce nse schimbă numărul de elemente. Sortarea cu bule este unul dintre cei mai simpli și mai ineficienți algoritmi de sortare. De asemenea, uneori mai este numită „sort prost”. Material pe acest subiect:
Un alt algoritm de sortare este sortarea prin selecție. Are, de asemenea, complexitate pătratică, dar mai multe despre asta mai târziu. Deci ideea este simplă. La fiecare trecere, selectăm cel mai mic element și îl deplasăm la început. În plus, fiecare trecere începe cu un pas spre dreapta. Cu alte cuvinte, prima trecere începe de la elementul zero, a doua trecere de la primul etc. Va arăta astfel:
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));
Acest sortare este instabil, deoarece elementele identice (în ceea ce privește caracteristicile pe care le folosim pentru a sorta elementele) își pot schimba pozițiile relative. Există un exemplu bun în articolul Wikipedia despre sortarea selecției . Material pe acest subiect:
Sortarea prin inserție are și complexitate pătratică, deoarece avem din nou o buclă într-o buclă. Ce face sortarea prin inserare diferită? Acest algoritm de sortare este „stabil”. Aceasta înseamnă că elementele identice nu își vor schimba ordinea relativă. Din nou, ne referim la identic în ceea ce privește caracteristicile după care sortăm.
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));
Navetă sortare
Există un alt algoritm de sortare simplu: sortarea navetă. Acesta este, de asemenea, cunoscut sub numele de sortare cu bule bidirecționale sau sortare de cocktail shaker. Aceste nume alternative ne spun că tipul de navetă nu este despre naveta spațială. Este vorba despre ceva care se mișcă înainte și înapoi. Acum te poți gândi la asta când te gândești la acest algoritm. Care este esența algoritmului? Esența algoritmului este că repetăm de la stânga la dreapta, schimbând elemente și verificând dacă oricare dintre elementele rămase în cealaltă direcție trebuie schimbat.
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));
Un alt algoritm simplu de sortare este sortarea shell. Esenta este similară cu sortarea cu bule, dar în fiecare iterație avem un decalaj diferit între elementele comparate. Este tăiat în jumătate cu fiecare iterație. Iată o implementare:
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));
Pe lângă acești algoritmi simpli de sortare, există și algoritmi de sortare mai complicati. De exemplu, sortare îmbinare. Sunt două lucruri de remarcat. În primul rând, recursiunea vine în ajutorul nostru aici. În al doilea rând, complexitatea algoritmului nu mai este pătratică, așa cum suntem obișnuiți. Complexitatea acestui algoritm este logaritmică. Acesta este scris ca O(n log n). Deci haideți să o implementăm. Mai întâi, vom scrie un apel recursiv la metoda de sortare:
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);
}
}
Acum, să adăugăm acțiunea principală la implementarea noastră. Iată super metoda noastră:
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);
}
Ne putem rula exemplul sunândmergeSort(array, 0, array.length-1). După cum puteți vedea, procesul se rezumă la acceptarea unei matrice de intrare împreună cu indicațiile începutului și sfârșitului secțiunii care trebuie sortată. Când începe sortarea, acestea sunt începutul și sfârșitul matricei. Apoi calculăm delimitatorul, care este indexul în care vom împărți matricea. Dacă matricea poate fi împărțită în 2 părți, atunci numim metoda de sortare recursiv pentru cele două jumătăți ale matricei. Pregătim un buffer auxiliar în care vom introduce secțiunea sortată. Apoi, setați indexul la începutul secțiunii de sortat și începeți să parcurgeți fiecare element al bufferului gol, umplându-l cu cele mai mici elemente. Dacă elementul indicat de index este mai mic decât elementul indicat de delimitator, punem elementul în buffer și deplasăm indexul. In caz contrar, plasăm elementul indicat de delimitator în buffer și deplasăm delimitatorul. De îndată ce delimitatorul depășește limitele secțiunii care este sortată sau umplem întregul tablou, intervalul specificat este considerat sortat.Material pe acest subiect:
Un alt algoritm de sortare interesant este sortarea de numărare. Complexitatea algoritmică aici este O(n+k), unde neste numărul de elemente și keste valoarea maximă a unui element. Acest algoritm are un singur dezavantaj: trebuie să cunoaștem valorile minime și maxime din matrice. Iată un exemplu de sortare de numărare:
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;
}
Puteți înțelege că este foarte incomod când trebuie să cunoaștem dinainte valorile minime și maxime. Și avem un alt algoritm aici: radix sort. Voi prezenta algoritmul aici doar vizual. Vezi materialele suplimentare pentru implementare: Materiale:
Ei bine, este timpul pentru desert - sortare rapidă, unul dintre cei mai faimoși algoritmi de sortare. Are complexitate logaritmică: O(n log n). Acest algoritm de sortare a fost dezvoltat de Tony Hoare. Interesant este că a inventat-o în timp ce locuia în Uniunea Sovietică, unde a studiat traducerea automată la Universitatea din Moscova și a dezvoltat o carte de expresii rusă-engleză. Mai mult, Java folosește o versiune mai complexă a acestui algoritm în Arrays.sort. Ce zici Collections.sort? De ce să nu aruncați o privire la modul în care sunt sortate lucrurile „sub capotă”? Iată codul:
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);
}
}
Toate acestea sunt lucruri foarte înfricoșătoare, așa că haideți să cercetăm. Pentru matricea de intrare ( int[]sursă), creăm doi markeri: stânga ( L) și dreapta ( R). În timpul primului apel de metodă, acestea corespund începutului și sfârșitului matricei. Apoi identificăm elementul pivot, care este denumit în mod adecvat pivot. După aceasta, sarcina noastră este să mutăm valorile mai mici decât pivotla stânga lui pivotși pe cele mai mari - la dreapta. Pentru a face acest lucru, mai întâi mișcăm Lmarcatorul până când găsim o valoare mai mare decât pivot. Dacă nu se găsește o valoare mai mică, atunci
L devine egal cu
pivot. Apoi mutam marcatorul
Rpana cand gasim o valoare mai mica decat
pivot. Dacă nu se găsește o valoare mai mare, atunci
Rdevine egal cu
pivot. Apoi, dacă
Lmarkerul este înaintea
Rmarkerului sau coincide cu acesta, atunci încercăm să schimbăm elementele dacă elementul
Leste mai mic decât
Relementul. Apoi ne deplasăm
Lla dreapta cu 1 și ne deplasăm
Rla stânga cu 1. Când
Lmarcatorul se deplasează dincolo de
Rmarcator, înseamnă că schimbarea este completă: valorile mai mici sunt la stânga lui
pivot, valorile mai mari sunt la dreapta lui
pivot. După aceasta, apelăm recursiv aceeași metodă de sortare pe subbariere - de la începutul secțiunii care urmează să fie sortată la markerul din dreapta și de la markerul din stânga până la sfârșitul secțiunii care urmează să fie sortată. De ce de la început până la markerul potrivit? Pentru că la sfârșitul unei iterații, se dovedește că markerul din dreapta se mișcă suficient pentru a deveni limita părții din stânga. Acest algoritm este mai complex decât simpla sortare, așa că cel mai bine este să-l schițezi. Luați o foaie albă de hârtie și scrieți: 4 2 6 7 3. Apoi scrieți
pivotîn mijloc, adică sub numărul 6. Încercuiește-o. Sub 4, scrie
L, iar sub 3, scrie
R. 4 mai puțin decât 6, 2 mai puțin decât 6. Ajungem prin a trece
Lla
pivotpoziție, pentru
Lcă nu putem trece pe lângă
pivot, conform conditiei. Scrie din nou 4 2 6 7 3. Încercuiește 6 (
pivot) și pune
L-l dedesubt. Acum mutați
Rmarcatorul. 3 este mai mic decât 6, așa că puneți
Rmarcatorul pe 3. Deoarece 3 este mai mic decât 6 (
pivot), efectuăm o
swap. Scrie rezultatul: 4 2 3 7 6. Încercuiește 6, deoarece este încă
pivot. Markerul
Leste pe 3.
RMarkerul este pe 6. Amintiți-vă că mutăm marcajele până când
Ltrecem dincolo de
R. Treceți
Lla următorul număr. Aici aș dori să explorez două posibilități: 1) cazul în care penultimul număr este 7 și 2) cazul în care este 1, nu 7.
Dacă penultimul număr este 1: Mutați
Lmarcatorul la 1, pentru că putem muta
Latâta timp cât
Lmarkerul indică un număr mai mic decât
pivot. Dar nu ne putem deplasa
Rde la 6, deoarece putem muta R doar dacă
Rmarcatorul indică un număr care este mai mare decât
pivot. Nu efectuăm un
swap, deoarece 1 este mai mic decât 6. Scrieți situația actuală: 4 2 3 1 6. Încercuiți 6 (
pivot).
Ltrece
pivotși se oprește din mișcare.
Rnu se mișcă. Nu facem schimburi. Schimbați
Lși
Rcu o poziție. Scrieți
Rmarcatorul sub 1.
LMarkerul este în afara limitelor. Pentru că
Leste în afara limitelor, nu facem nimic. Dar, scriem din nou 4 2 3 1, pentru că aceasta este partea noastră stângă, care este mai mică decât
pivot(6). Selectați noul
pivotși începeți totul din nou :)
Dacă penultimul număr este 7:Mutați
Lmarkerul la 7. Nu putem muta markerul drept, deoarece este deja îndreptat spre pivot. 7 este mai mare decât
pivot, deci efectuăm un
swap. Scrie rezultatul: 4 2 3 6 7. Încercuiește 6, deoarece este
pivot. Markerul
Leste mutat acum la 7, iar
Rmarcatorul este mutat la 3. Nu are sens să sortați piesa de
Lla sfârșit, deoarece există doar 1 element. Cu toate acestea, trimitem piesa de la 4 la
Rmarker pentru sortare. Alegem a
pivotși o luăm de la capăt :) La prima vedere, poate părea că dacă adăugați o mulțime de valori egale cu
pivot, atunci vei rupe algoritmul. Dar nu este cazul. Puteți să vă gândiți la combinații dificile și pe hârtie să vă convingeți că totul este corect și să vă minunați că astfel de acțiuni simple implementează un mecanism de sortare atât de fiabil. Singurul dezavantaj este că acest algoritm de sortare nu este stabil. Deoarece o schimbare poate schimba ordinea relativă a elementelor identice dacă unul dintre ele este întâlnit înainte
pivotînainte ca celălalt element să fie schimbat în partea anterioară
pivot.
Linia de jos
Mai sus, ne-am uitat la un set „domn” de algoritmi de sortare implementați în Java. Algoritmii sunt în general utili, atât din perspectivă aplicată, cât și în ceea ce privește învățarea cum să gândim. Unele sunt mai simple, altele mai complicate. Oameni deștepți și-au susținut disertațiile pentru unii. Pentru alții, au scris cărți super groase. Sper că materialele suplimentare vă vor ajuta să învățați și mai multe, deoarece acest articol este doar o prezentare generală care sa dovedit deja a fi grea. Și scopul său este de a oferi o mică introducere. De asemenea, puteți găsi o introducere în algoritmi dacă citiți
„Algoritmi Grokking ”. Îmi place și lista de redare de la Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . Pentru distracție, puteți vedea vizualizările algoritmilor la
sortare.visualgo.net .
GO TO FULL VERSION