Sortowanie wyboru Java Program z przykładem

⚡ Inteligentne podsumowanie

Sortowanie przez wybór w Java wielokrotnie skanuje nieposortowaną część tablicy, znajduje najmniejszą pozostałą wartość i umieszcza ją w odpowiedniej pozycji, kończąc pracę przy maksymalnie n-1 zamianach, niezależnie od kolejności wprowadzania danych.

  • 🔘 Definicja: Sortowanie przez wybieranie dzieli tablicę na obszar sortowany i obszar niesortowany przy każdym przejściu.
  • ️ Proces: W każdym przebiegu przeszukiwany jest nieposortowany region w celu znalezienia najniższego elementu i zamiany go na inny.
  • ✅ Program: Java przykład sortuje {860, 8, 200, 9} i drukuje każde porównanie i zamianę.
  • 🧪 Złożoność: Najlepszy, średni i najgorszy przypadek są obliczane w czasie O(n²), ponieważ liczba porównań nigdy się nie zmniejsza.
  • 🛠️. Pamięć: Wymiany odbywają się wewnątrz oryginalnej tablicy, więc przestrzeń pomocnicza pozostaje na poziomie O(1).
  • 📊 Zachowanie: Klasyczna wersja jest niestabilna, ale wykonuje najmniej operacji zapisu dowolnego typu kwadratowego.

Sortowanie wyboru Java Program z przykładem

Jak działa sortowanie przez wybór?

Sortowanie przez wybór implementuje prosty algorytm sortowania w następujący sposób:

  • Algorytm wielokrotnie wyszukuje najniższy element.
  • Zamień bieżący element na element o najniższej wartości
  • Przy każdej iteracji/przejściu sortowania przez wybór elementy są zamieniane.

Każde przejście traktuje zatem szyk jako dwa obszary: posortowany blok rosnący od lewej i niesortowany blok kurczący się po prawej. Algorytm przechodzi przez niesortowany blok, zapamiętuje indeks najmniejszej napotkanej wartości i zamienia tę wartość z pierwszą niesortowaną pozycją.

Ponieważ w jednym przejściu następuje tylko jedna wymiana, tablica n elementów jest porządkowana po maksymalnie n-1 zamianach. Ta właściwość odróżnia tę procedurę od innych procedur dla początkujących. Java algorytmy sortowania, które znacznie częściej przenoszą dane.

tracPoniższy przykład jest następcą tablicy {860, 8, 200, 9} dokładnie tak, jak program w następnej sekcji drukuje ją w czasie wykonywania.

Przechodzić Porównania wydrukowane Najmniejsza znaleziona wartość Tablica po zamianie
Rozpocznij Do Do 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

Dwa szczegóły w tym tracWarto się nad nimi zatrzymać. Po pierwsze, przebieg 3 nadal zgłasza zamianę, mimo że kolejność się nie zmienia, ponieważ najmniejsza pozostała wartość znajduje się już pod bieżącym indeksem, a program wymienia element ze sobą. Po drugie, liczba porównań spada o jeden w każdym przebiegu (trzy, potem dwa, a potem jedno), co jest wzorcem leżącym u podstaw liczb złożoności przedstawionych dalej na stronie.

Java Program do implementacji sortowania przez wybór

Poniższa klasa nosi nazwę SelectionSortAlgo i znajduje się w pakiecie com.guru99. Metoda main() deklaruje tablicę przykładową, drukuje ją, przekazuje do selection() w celu sortowania i ponownie drukuje. Funkcja pomocnicza printArray() zapisuje wszystkie elementy w jednym wierszu, co generuje czytelny dziennik przejść pominiętych.

Wewnątrz funkcji selection() pętla zewnętrzna zaznacza granicę między obszarami sortowanymi i nieposortowanymi, zmienna index przechowuje pozycję najmniejszej wartości widzianej do tej pory, a trzy przypisania na końcu każdego przebiegu wykonują zamianę.

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

Wyjście:

Skompilowanie i uruchomienie klasy generuje poniższy dziennik konsoli, zawierający jeden blok danych wyjściowych na przejście.

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

Początkujący napotykają dwa problemy, gdy uruchamiają ten przykład po raz pierwszy. Ponieważ plik deklaruje package com.guru99;źródło musi znajdować się w pasującym com/guru99 katalogu, w przeciwnym razie kompilator zgłosi niezgodność nazwy pakietu lub klasy. Klasę należy wówczas uruchomić za pomocą jej pełnej nazwy kwalifikowanej, java com.guru99.SelectionSortAlgo, ponieważ zwykły java SelectionSortAlgo podnosi wyjątek NoClassDefFoundError.

Granice pętli to kolejna częsta pułapka. Pętla zewnętrzna zatrzymuje się na array.length - 1 a wewnętrzna pętla zaczyna się od i + 1; zmiana którejkolwiek z granic powoduje dodatkowe puste przejście lub wyjątek ArrayIndexOutOfBoundsException.

Złożoność czasowa i przestrzenna sortowania przez wybieranie

Pętla wewnętrzna w programie zawsze przebiega do końca tablicy, więc algorytm wykonuje tę samą liczbę porównań, niezależnie od wyglądu danych. Dla tablicy n-elementowej suma wynosi n(n-1)/2, co dla próbki czteroelementowej daje sześć, a powyższy wynik rzeczywiście wyświetla dokładnie sześć wierszy porównania.

Walizka Porównania Swapy Złożoność czasowa Przestrzeń pomocnicza
Najlepszy (tablica już posortowana) n(n-1)/2 n-1 O(n²) O (1)
Średnia (kolejność losowa) n(n-1)/2 n-1 O(n²) O (1)
Najgorsze (sortowanie odwrotne) n(n-1)/2 n-1 O(n²) O (1)

Z tego jednolitego szeregu cyfr wynikają trzy konsekwencje:

  • Sortowanie przez wybór nie jest adaptacyjne. Posortowane dane wejściowe kosztują dokładnie tyle samo, co dane wejściowe odwrócone, więc nie ma skrótu do wcześniejszego wyjścia. sortowanie bąbelkowe oferuje.
  • Liczba wymian to mocna strona algorytmu. Maksymalnie odbywa się n-1 wymian, czyli znacznie mniej niż kwadratowa liczba ruchów, jaką mogą wykonać inne proste algorytmy.
  • Użycie pamięci jest stałe. Potrzebne są tylko liczniki pętli oraz dwie zmienne tymczasowe: index i lessNumber, więc przestrzeń pomocnicza zajmuje O(1), a sortowanie odbywa się w miejscu.

Wzrost kwadratowy to praktyczna granica. Podwojenie rozmiaru tablicy mniej więcej czterokrotnie zwiększa nakład pracy porównawczej, dlatego sortowanie przez wybieranie sprawdza się w nauczaniu, małych tablicach i kodzie wbudowanym, a nie w zbiorach danych produkcyjnych, gdzie właściwym wyborem są algorytmy O(n log n).

Zalety i wady sortowania przez selekcję

Zrozumienie, kiedy algorytm pomaga, a kiedy przeszkadza, ułatwia podjęcie decyzji, kiedy warto po niego sięgnąć.

Zalety

  • Logika jest krótka i czytelna, dlatego stanowi standardowe pierwsze ćwiczenie sortujące sortowanie przez wstawianie.
  • Sortuje w miejscu, dzięki czemu nie jest przydzielana druga tablica, a użycie pamięci nie rośnie wraz z danymi wejściowymi.
  • Wykonuje maksymalnie n-1 operacji zapisu do tablicy, co ma znaczenie w przypadku pamięci masowej, w których operacje zapisu są powolne lub powodują zużycie nośnika.
  • Czas wykonania jest całkowicie przewidywalny, ponieważ liczba porównań zależy wyłącznie od długości tablicy.

Wady

  • Każdy przypadek jest O(n²), więc algorytm nie skaluje się do dużych zbiorów.
  • Nie jest w stanie wykryć, że tablica jest już posortowana, dlatego nigdy nie kończy pracy przed czasem.
  • Klasyczna forma pokazana powyżej jest niestabilna, więc dwie równe wartości mogą pojawić się w odwrotnej kolejności.
  • Porównuje dane niemal uporządkowane częściej niż sortowanie przez wstawianie, podczas gdy sortowanie przez wstawianie zbliża się do czasu liniowego.

Krótko mówiąc, wybieraj sortowanie przez wybór, gdy tablica jest mała i każdy zapis jest kosztowny, a unikaj tej opcji, gdy zbiór danych jest duży lub prawie gotowy do posortowania.

Sortowanie przez wybór vs. BubblSortowanie e vs. sortowanie przez wstawianie

Wszystkie trzy algorytmy są kwadratowymi algorytmami sortującymi przez porównanie w miejscu, jednak zachowują się inaczej, gdy zmienia się kształt danych wejściowych.

Kryterium Sortowanie wyboru Bubblsortowanie Sortowanie przez wstawianie
Najlepszy czas O(n²) Na) Na)
Średni i najgorszy czas O(n²) O(n²) O(n²)
W najgorszym przypadku zamiany lub przesunięcia n-1 swapów n(n-1)/2 zamian Do n(n-1)/2 zmian
Stabilny Nie Tak Tak
Adaptacja do posortowanego wejścia Nie Tak Tak
Przestrzeń pomocnicza O (1) O (1) O (1)
Typowe zastosowanie Najmniej wymaganych zapisów Nauczanie i wyszukiwanie posortowanych danych Małe lub prawie posortowane tablice

Tabela wyjaśnia typową odpowiedź udzielaną podczas rozmowy kwalifikacyjnej. Sortowanie przez wybór wygrywa pod względem liczby wymian, sortowanie bąbelkowe wygrywa pod względem rozpoznawania danych wejściowych, które są już uporządkowane, a sortowanie przez wstawianie jest zazwyczaj najszybsze z tych trzech w praktyce, ponieważ rzeczywiste dane są często częściowo posortowane. Żadne z nich nie konkuruje z sortowaniem przez scalanie ani sortowaniem szybkim, gdy tablica przekroczy kilkadziesiąt elementów.

FAQ

Po n-1 przejściach nieposortowany region zawiera pojedynczy element, a samotny element jest już na swoim właściwym miejscu. Wykonanie kolejnego przejścia nie dałoby żadnych wyników, więc ograniczenie pętli pozwala uniknąć zmarnowanej iteracji.

Asystenci AI mogą opowiadać słownie o każdym przejściu, tworzyć dodatkowe tablice testowe i liczyć porównania dla danego wejścia. Wykorzystaj wyjaśnienie jako pomoc naukową i potwierdź wszelkie twierdzenia dotyczące złożoności w odniesieniu do podręcznika, zanim je zacytujesz.

Tak. Drugi pilot GitHub Uzupełnia metodę z sygnatury lub komentarza. Sprawdź sam początek pętli wewnętrznej i linie zamiany, ponieważ wygenerowane wersje czasami zamieniają się z i, a nie z zapisanym minimalnym indeksem.

Pokazana tutaj wersja jest niestabilna, ponieważ wymiana na dużą odległość może powodować przeskakiwanie jednej równej wartości ponad drugą. Shiftblokowanie elementów zamiast zamianyping zachowuje oryginalną kolejność jednakowych kluczy, kosztem dodatkowych zapisów.

Reverse Porównanie wewnątrz pętli wewnętrznej. Sprawdzanie, czy array[j] jest większe niż array[index] tracks to największa pozostała wartość, więc każde przejście przesuwa maksimum do przodu, a gotowa tablica przebiega od najwyższej do najniższej wartości.

Tak. Metoda rekurencyjna znajduje minimum bieżącej podtablicy, umieszcza ją na początku, a następnie wywołuje samą siebie dla reszty. Liczba porównań pozostaje niezmieniona, ale stos wywołań dodaje przestrzeń O(n), dlatego preferowana jest forma pętli.

Częstymi błędami są zapominanie o zresetowaniu indeksu do i na początku każdego przebiegu, rozpoczynanie pętli wewnętrznej od i zamiast od i + 1 oraz zamianaping array[j] zamiast array[index], który traci track o najmniejszej wartości.

Nie. Arrays.sort() stosuje sortowanie szybkie z podwójnym przesunięciem do prymitywów, a TimSort do obiektów, z sortowaniem przez wstawianie na małych partycjach. Sortowanie przez wybieranie pojawia się w materiałach dydaktycznych i ręcznie pisanym kodzie, a nie w bibliotece standardowej.

Podsumuj ten post następująco: