Odabir Razvrstavanje u Java Program s primjerom

Kako funkcionira sortiranje odabirom?

Selection Sort implementira jednostavan algoritam sortiranja na sljedeći način:

• Algoritam više puta traži najniži element.
• Zamijenite trenutni element s elementom koji ima najmanju vrijednost
• Sa svakim ponavljanjem/prolaskom sortiranja selekcije, elementi se mijenjaju.

Svaki prolaz stoga tretira poredak kao dvije regije: sortirani blok koji raste s lijeva i nesortirani blok koji se smanjuje s desne strane. Algoritam obilazi nesortirani blok, pamti indeks najmanje vrijednosti koju susreće i zamjenjuje tu vrijednost s prvom nesortiranom pozicijom.

Budući da se u jednom prolazu događa samo jedna zamjena, niz od n elemenata se uređuje nakon najviše n-1 zamjena. To svojstvo razlikuje ovu rutinu od ostalih rutina početne razine. Java algoritmi sortiranja, koji premještaju podatke daleko češće.

The tracSlijedeći niz slijedi primjer {860, 8, 200, 9} točno onako kako ga program u sljedećem odjeljku ispisuje za vrijeme izvođenja.

Dva detalja u tome tracVrijedi se na njima malo zastati. Prvo, prolaz 3 i dalje prijavljuje zamjenu iako se redoslijed ne mijenja, jer najmanja preostala vrijednost već leži na trenutnom indeksu i program zamjenjuje element sam sa sobom. Drugo, broj usporedbi pada za jednu u svakom prolazu (tri, zatim dvije, pa jedna), što je obrazac iza brojki složenosti dalje na stranici.

Java Program za implementaciju Selection Sort

Klasa u nastavku zove se SelectionSortAlgo i nalazi se u paketu com.guru99. Metoda main() deklarira uzorak polja, ispisuje ga, predaje ga selection() za sortiranje i ponovno ga ispisuje. Pomoćna metoda printArray() zapisuje sve elemente u jedan redak, što stvara čitljiv zapisnik prolaza-za-prolaza.

Unutar selection(), vanjska petlja označava granicu između sortiranih i nesortiranih područja, varijabla index drži poziciju najmanje vrijednosti viđene do sada, a tri dodjele na kraju svakog prolaza izvode zamjenu.

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();
	    
	}
 
}

Izlaz:

Kompajliranje i pokretanje klase proizvodi donji zapisnik konzole, s jednim blokom izlaza po prolazu.

------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

Dva problema susreću početnike kada prvi put pokrenu ovaj primjer. Budući da datoteka deklarira package com.guru99;, izvor mora živjeti u odgovarajućem com/guru99 direktorij, inače kompajler prijavljuje neusklađenost naziva paketa ili klase. Klasa se tada mora pokrenuti svojim punim imenom, java com.guru99.SelectionSortAlgo, jer običan java SelectionSortAlgo podiže NoClassDefFoundError.

Granice petlje su druga uobičajena zamka. Vanjska petlja se zaustavlja na array.length - 1 a unutarnja petlja počinje od i + 1; promjena bilo koje granice proizvodi dodatni prazan prolaz ili iznimku ArrayIndexOutOfBoundsException.

Vremenska i prostorna složenost sortiranja odabirom

Unutarnja petlja u programu uvijek se izvršava do kraja polja, pa algoritam izvodi isti broj usporedbi bez obzira na to kako podaci izgledaju. Za polje od n elemenata taj zbroj je n(n-1)/2, što je za uzorak od četiri elementa jednako šest, a gornji izlaz doista ispisuje točno šest redaka za usporedbu.

Iz tog ujednačenog niza slika slijede tri posljedice:

• Sortiranje odabirom nije adaptivno. Sortirani ulaz košta točno onoliko koliko i obrnuti ulaz, tako da ne postoji prečac s ranim izlazom te vrste. sortiranje mjehurićima nudi.
• Broj zamjena je jača strana algoritma. Odvija se najviše n-1 zamjena, što je daleko manje od kvadratnog broja poteza koje druge jednostavne sorte mogu napraviti.
• Korištenje memorije je konstantno. Potrebni su samo brojači petlji i dvije privremene varijable index i smallerNumber, tako da je pomoćni prostor O(1) i sortiranje se događa na mjestu.

Kvadratni rast je praktično ograničenje. Udvostručenje veličine polja otprilike učetverostručuje posao usporedbe, tako da sortiranje odabirom odgovara podučavanju, malim nizovima i ugrađenom kodu, a ne produkcijskim skupovima podataka, gdje su algoritmi O(n log n) ispravan izbor.

Prednosti i nedostaci sortiranja odabirom

Razumijevanje gdje algoritam pomaže, a gdje odmaže olakšava odlučivanje kada je razumno posegnuti za njim.

Prednosti

• Logika je kratka i čitljiva, zbog čega je to standardna prva vježba sortiranja uz umetanje sortirati.
• Sortira na mjestu, tako da se ne dodjeljuje drugi niz i korištenje memorije ne raste s ulazom.
• Izvršava najviše n-1 zapisa u niz, što je važno za pohranu gdje su zapisi spori ili troše medij.
• Vrijeme izvođenja je potpuno predvidljivo, jer broj usporedbi ovisi samo o duljini niza.

Nedostaci

• Svaki slučaj je O(n²), tako da se algoritam ne skalira na velike kolekcije.
• Ne može otkriti već sortirani niz i stoga nikada ne završava ranije.
• Klasični oblik prikazan gore je nestabilan, pa dvije jednake vrijednosti mogu završiti u suprotnom redoslijedu.
• Češće uspoređuje od sortiranja umetanjem na gotovo uređenim podacima, gdje se sortiranje umetanjem približava linearnom vremenu.

Ukratko, odaberite sortiranje odabirom kada je niz malen i svako pisanje je skupo, a izbjegavajte ga kad god je skup podataka velik ili već blizu sortiranja.

Sortiranje odabirom u odnosu na Bubble Sortiranje u odnosu na sortiranje umetanjem

Sva tri algoritma su kvadratna, s usporedbom na mjestu, no ponašaju se drugačije kada se promijeni oblik ulaza.

Tablica objašnjava uobičajeni odgovor na intervjuu. Sortiranje odabirom pobjeđuje u broju razmjena, mjehurićasto sortiranje pobjeđuje u prepoznavanju ulaza koji je već uređen, a sortiranje umetanjem obično je najbrže od te tri metode u praksi jer su stvarni podaci često djelomično sortirani. Nijedno od njih ne konkurira sortiranju spajanjem ili brzim sortiranjem nakon što niz naraste preko nekoliko desetaka elemenata.

Pitanja i odgovori