Sortare selecție în Java Program cu Exemplu
⚡ Rezumat inteligent
Sortare selecție în funcție de Java scanează în mod repetat partea nesortată a unui tablou, găsește cea mai mică valoare rămasă și o schimbă în poziția dorită, finalizând lucrarea cu cel mult n-1 schimburi, indiferent de ordinea de intrare.

Cum funcționează Selection Sort?
Selection Sort implementează un algoritm de sortare simplu, după cum urmează:
- Algoritmul caută în mod repetat elementul cel mai de jos.
- Schimbați elementul curent cu un element având cea mai mică valoare
- Cu fiecare iterație/trecere de sortare a selecției, elementele sunt schimbate.
Prin urmare, fiecare trecere tratează mulțime ca două regiuni: un bloc sortat care crește de la stânga și un bloc nesortat care se micșorează la dreapta. Algoritmul parcurge blocul nesortat, își amintește indicele celei mai mici valori pe care o întâlnește și schimbă acea valoare cu prima poziție nesortată.
Deoarece are loc un singur schimb per trecere, o matrice de n elemente este ordonată după cel mult n-1 schimburi. Această proprietate este ceea ce diferențiază această rutină de celelalte pentru începători. Java algoritmi de sortare, care mută datele mult mai des.
tracFigura de mai jos urmează matricea exemplu {860, 8, 200, 9} exact așa cum o afișează programul din secțiunea următoare la momentul execuției.
| Trece | Comparații tipărite | Cea mai mică valoare găsită | Matrice după schimb |
|---|---|---|---|
| acasă | - | - | +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 |
Două detalii în asta tracMerită să ne oprim asupra acestora. În primul rând, pasul 3 raportează în continuare o schimbare, chiar dacă ordinea nu se schimbă, deoarece cea mai mică valoare rămasă se află deja la indexul curent, iar programul schimbă elementul cu sine însuși. În al doilea rând, numărul de comparații scade cu unu la fiecare pasă (trei, apoi două, apoi una), acesta fiind modelul din spatele cifrelor de complexitate de mai jos pe pagină.
Java Program pentru implementarea Selection Sort
Clasa de mai jos se numește SelectionSortAlgo și se află în pachetul com.guru99. Metoda main() declară matricea eșantion, o afișează, o dă funcției selection() pentru sortare și o afișează din nou. Funcția helper printArray() scrie toate elementele pe o singură linie, ceea ce produce jurnalul de trecere-prin-trecere lizibil.
În interiorul funcției selection(), bucla exterioară marchează granița dintre regiunile sortate și cele nesortate, variabila index menține poziția celei mai mici valori văzute până în prezent, iar cele trei atribuări de la sfârșitul fiecărei treceri efectuează schimbarea.
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(); } }
ieșire:
Compilarea și rularea clasei produce jurnalul consolei de mai jos, cu un bloc de ieșire per trecere.
------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
Două probleme îi iau prin surprindere pe începători atunci când rulează acest exemplu pentru prima dată. Deoarece fișierul declară package com.guru99;, sursa trebuie să se afle într-o locație potrivită com/guru99 director, altfel compilatorul raportează o nepotrivire de nume de pachet sau de clasă. Clasa trebuie apoi lansată cu numele său complet calificat, java com.guru99.SelectionSortAlgo, pentru că simplu java SelectionSortAlgo generează eroarea NoClassDefFoundError.
Limitele buclei sunt cealaltă capcană comună. Bucla exterioară se oprește la array.length - 1 iar bucla interioară începe la i + 1; modificarea oricăreia dintre limite produce o trecere goală suplimentară sau o excepție ArrayIndexOutOfBounds.
Complexitatea timpului și spațiului sortării prin selecție
Bucla interioară din program rulează întotdeauna până la sfârșitul tabloului, deci algoritmul efectuează același număr de comparații indiferent de aspectul datelor. Pentru un tablou de n elemente, totalul este n(n-1)/2, ceea ce pentru eșantionul cu patru elemente este egal cu șase, iar rezultatul de mai sus afișează într-adevăr exact șase linii de comparare.
| Caz | Comparații | Swap-urile | Complexitatea timpului | Spațiu auxiliar |
|---|---|---|---|---|
| Cel mai bun (matricea deja sortată) | n (n-1) / 2 | n-1 | O(n²) | O (1) |
| Medie (ordine aleatorie) | n (n-1) / 2 | n-1 | O(n²) | O (1) |
| Cel mai rău (sortare inversă) | n (n-1) / 2 | n-1 | O(n²) | O (1) |
Trei consecințe decurg din acel rând uniform de cifre:
- Sortarea prin selecție nu este adaptivă. Intrarea sortată costă exact la fel de mult ca intrarea inversată, deci nu există o scurtătură de ieșire anticipată de acest fel. sortare cu bule ofera.
- Numărul de schimburi este punctul forte al algoritmului. Au loc cel mult n-1 schimburi, ceea ce este mult mai puțin decât numărul pătratic de mutări pe care le pot face alte sortări simple.
- Utilizarea memoriei este constantă. Sunt necesare doar contoarele de buclă și cele două variabile temporare index și smallerNumber, deci spațiul auxiliar este O(1) și sortarea are loc la locul ei.
Creșterea pătratică este limita practică. Dublarea dimensiunii matricei cvadruplează aproximativ munca de comparare, astfel încât sortarea prin selecție se potrivește mai degrabă predării, matricelor mici și codului încorporat decât seturilor de date de producție, unde algoritmii O(n log n) sunt alegerea corectă.
Avantajele și dezavantajele sortării prin selecție
Înțelegerea modului în care algoritmul ajută și unde dăunează face mai ușoară decizia privind momentul în care este rezonabil să îl utilizezi.
Avantaje
- Logica este scurtă și ușor de citit, motiv pentru care este un prim exercițiu standard de sortare alături de sortare inserție.
- Se sortează pe loc, astfel încât nu se alocă o a doua matrice și utilizarea memoriei nu crește odată cu intrarea.
- Efectuează cel mult n-1 scrieri pe matrice, ceea ce este important în spațiul de stocare unde scrierile sunt lente sau uzează mediul.
- Timpul său de execuție este complet previzibil, deoarece numărul de comparații depinde doar de lungimea matricei.
Dezavantaje
- Fiecare caz este O(n²), deci algoritmul nu se scalează la colecții mari.
- Nu poate detecta o matrice deja sortată și, prin urmare, nu se termină niciodată mai devreme.
- Forma clasică prezentată mai sus este instabilă, astfel încât două valori egale pot ajunge în ordine opusă.
- Compară mai des decât sortarea prin inserție pe date aproape ordonate, unde sortarea prin inserție se apropie de timpul liniar.
Pe scurt, alegeți sortarea prin selecție atunci când matricea este mică și fiecare scriere este costisitoare și evitați-o ori de câte ori setul de date este mare sau deja aproape de sortare.
Sortare prin selecție vs. BubblSortare prin e vs. sortare prin inserție
Toți cei trei algoritmi sunt sortări pătratice, prin comparație in-place, însă se comportă diferit odată ce forma intrării se schimbă.
| Criteriu | Sortare selecție | Bubblun fel | Sortare prin inserție |
|---|---|---|---|
| Cel mai bun moment posibil | O(n²) | O (n) | O (n) |
| Timpul mediu și cel mai defavorabil | O(n²) | O(n²) | O(n²) |
| Schimbări sau deplasări în cel mai rău caz | n-1 schimburi | n(n-1)/2 schimburi | Până la n(n-1)/2 deplasări |
| Stabil | Nu | Da | Da |
| Adaptiv la intrarea sortată | Nu | Da | Da |
| Spațiu auxiliar | O (1) | O (1) | O (1) |
| Utilizare tipică | Cele mai puține scrieri necesare | Predarea și identificarea datelor sortate | Tablouri mici sau aproape sortate |
Tabelul explică un răspuns comun la interviuri. Sortarea prin selecție câștigă în funcție de numărul de schimburi, sortarea prin bule câștigă în funcție de recunoașterea intrărilor deja ordonate, iar sortarea prin inserție este de obicei cea mai rapidă dintre cele trei în practică, deoarece datele reale sunt adesea parțial sortate. Niciuna dintre ele nu concurează cu sortarea prin îmbinare sau cu sortarea rapidă odată ce matricea crește peste câteva zeci de elemente.
