W tym samouczku dowiesz się, jak działa sortowanie przez wybór. Znajdziesz również działające przykłady sortowania przez wybór w językach C, C ++, Java i Python.
Sortowanie przez wybór to algorytm, który wybiera najmniejszy element z niesortowanej listy w każdej iteracji i umieszcza ten element na początku nieposortowanej listy.
Jak działa sortowanie przez wybór?
- Ustaw pierwszy element jako
minimum.
Wybierz pierwszy element jako minimum - Porównaj
minimumz drugim elementem. Jeśli drugi element jest mniejszy niżminimum, przypisz drugiemu element jakominimum.
Porównajminimumz trzecim elementem. Ponownie, jeśli trzeci element jest mniejszy, przypiszminimumdo trzeciego elementu, w przeciwnym razie nic nie rób. Proces trwa do ostatniego elementu.
Porównaj minimum z pozostałymi elementami - Po każdej iteracji
minimumjest umieszczany na początku niesortowanej listy.
Zamień pierwszy na minimum - Dla każdej iteracji indeksowanie rozpoczyna się od pierwszego nieposortowanego elementu. Kroki od 1 do 3 są powtarzane, aż wszystkie elementy zostaną umieszczone we właściwych miejscach.
Pierwsza iteracja 
Druga iteracja 
Trzecia iteracja 
Czwarta iteracja
Algorytm sortowania przez wybór
selectionSort (array, size) repeat (size - 1) times ustaw pierwszy nieposortowany element jako minimum dla każdego nieposortowanego elementu if element <currentMinimum set element jako nowe minimum wymiany z pierwszą nieposortowaną pozycją end selectionSort
Przykłady w Pythonie, Javie i C / C ++
Python Java C C ++ # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
// Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )
Złożoność
| Cykl | Liczba porównań |
|---|---|
| 1 | (n-1) |
| 2nd | (n-2) |
| 3rd | (n-3) |
| … | … |
| ostatni, ubiegły, zeszły | 1 |
Liczba porównań: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2prawie równa .n2
Złożoność =O(n2)
Możemy również przeanalizować złożoność, po prostu obserwując liczbę pętli. Istnieją 2 pętle, więc złożoność jest .n*n = n2
Złożoność czasowa:
- Najgorsza złożoność przypadku : jeśli chcemy posortować w porządku rosnącym, a tablica jest w porządku malejącym, wtedy pojawia się najgorszy przypadek.
O(n2) - Najlepsza złożoność przypadku: występuje, gdy tablica jest już posortowana
O(n2) - Średnia złożoność przypadku: występuje, gdy elementy tablicy są pomieszane (ani rosnąco, ani malejąco).
O(n2)
Złożoność czasowa sortowania przez wybieranie jest taka sama we wszystkich przypadkach. Na każdym kroku musisz znaleźć minimalny element i umieścić go we właściwym miejscu. Minimalny element nie jest znany, dopóki nie zostanie osiągnięty koniec tablicy.
Złożoność przestrzeni:
Złożoność przestrzeni O(1)wynika z tempużycia dodatkowej zmiennej .
Aplikacje sortowania przez wybór
Sortowanie przez wybór jest używane, gdy:
- należy posortować małą listę
- koszt zamiany nie ma znaczenia
- sprawdzenie wszystkich elementów jest obowiązkowe
- koszt zapisu do pamięci ma znaczenie jak w pamięci flash (liczba zapisów / zamian jest
O(n)porównywana z sortowaniem bąbelkowym)O(n2)
