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.

  • 🔘 Definiție: Sortarea prin selecție împarte matricea într-o regiune sortată și o regiune nesortată la fiecare trecere.
  • ☑️ Procesul: Fiecare trecere caută în regiunea nesortată elementul cel mai mic și îl schimbă înainte.
  • ✅ Program: Java Exemplul sortează {860, 8, 200, 9} și afișează fiecare comparație și permutare.
  • 🧪 Complexitate: Cazurile optime, medii și cele mai rele se execută toate în timp O(n²), deoarece numărul de comparații nu se micșorează niciodată.
  • 🛠️ Memorie: Schimburile au loc în interiorul tabloului original, deci spațiul auxiliar rămâne la O(1).
  • 📊 Comportament: Versiunea clasică este instabilă, totuși efectuează cele mai puține scrieri dintre toate tipurile de ordin pătratic.

Sortare selecție în Java Program cu Exemplu

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.

Întrebări frecvente

După n-1 treceri, regiunea nesortată conține un singur element, iar un element izolat se află deja în locul său corect. Rularea încă unei treceri nu ar compara nimic, astfel încât limita buclei evită o iterație irosită.

Asistenții inteligenți artificiali pot relata fiecare pas în cuvinte, pot construi tablouri de teste suplimentare și pot număra comparații pentru o anumită intrare. Folosește explicația ca ajutor pentru studiu și confirmă orice afirmație de complexitate față de un manual înainte de a-l cita.

Da. Copilotul GitHub completează metoda dintr-o semnătură sau un comentariu. Verificați singur începutul buclei interne și liniile de swap, deoarece versiunile generate se schimbă uneori cu i în loc de indexul minim stocat.

Versiunea prezentată aici este instabilă, deoarece un swap la distanță lungă poate face să sară o valoare egală peste alta. Shifting blocul de elemente în loc de swapping păstrează ordinea originală a cheilor egale, cu prețul unor scrieri suplimentare.

Reverse comparația din interiorul buclei interne. Testarea dacă array[j] este mai mare decât array[index] tracks cea mai mare valoare rămasă, astfel încât fiecare trecere mută maximul înainte, iar matricea finalizată rulează de la mare la mic.

Da. O metodă recursivă găsește minimul din subarray-ul curent, îl plasează în față, apoi se auto-se apelează la restul. Numărul de comparații rămâne neschimbat, dar stiva de apeluri adaugă spațiu O(n), deci este preferată forma buclei.

Erorile frecvente sunt uitarea resetării indexului la i la începutul fiecărei treceri, pornirea buclei interioare de la i în loc de i + 1 și schimbareaping array[j] în loc de array[index], care pierde track cu cea mai mică valoare.

Nu. Arrays.sort() aplică o sortare rapidă cu dual-pivot primitivelor și o sortare TimSort obiectelor, cu o sortare de tip inserare pe partiții minuscule. Sortarea prin selecție apare în materialele didactice și în codul scris de mână, mai degrabă decât în ​​biblioteca standard.

Rezumați această postare cu: