În acest tutorial, veți afla cum funcționează sortarea selecției. De asemenea, veți găsi exemple de lucru de sortare a selecției în C, C ++, Java și Python.
Sortarea selecției este un algoritm care selectează cel mai mic element dintr-o listă nesortată în fiecare iterație și plasează acel element la începutul listei nesortate.
Cum funcționează sortarea selecției?
- Setați primul element ca
minimum.
Selectați cel puțin primul element - Comparați
minimumcu al doilea element. În cazul în care al doilea element este mai mică decâtminimum, alocați al doilea element caminimum.
Comparațiminimumcu al treilea element. Din nou, dacă al treilea element este mai mic, atunci atribuițiminimumcelui de-al treilea element, altfel nu faceți nimic. Procesul continuă până la ultimul element.
Comparați minimul cu elementele rămase - După fiecare iterație,
minimumeste plasat în partea din față a listei nesortate.
Schimbați primul cu minim - Pentru fiecare iterație, indexarea începe de la primul element nesortat. Pasul 1 la 3 se repetă până când toate elementele sunt plasate în pozițiile lor corecte.
Prima iterație 
A doua iterație 
A treia iterație 
A patra iterație
Algoritm de sortare a selecției
selectionSort (matrice, dimensiune) repetați (dimensiune - 1) ori setați primul element nesortat ca minim pentru fiecare dintre elementele nesortate dacă elementul <curent Element minim setat ca nou minim swap minim cu prima selecție finală a poziției nesortate
Exemple Python, Java ș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); )
Complexitate
| Ciclu | Numărul de comparație |
|---|---|
| Primul | (n-1) |
| Al 2-lea | (n-2) |
| A treia | (n-3) |
| … | … |
| ultimul | 1 |
Numărul de comparații: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2aproape egal cu .n2
Complexitate =O(n2)
De asemenea, putem analiza complexitatea prin simpla observare a numărului de bucle. Există 2 bucle, deci complexitatea este .n*n = n2
Complexități de timp:
- Cel mai prost caz de complexitate: Dacă vrem să sortăm în ordine crescătoare și matricea este în ordine descrescătoare, atunci apare cel mai rău caz.
O(n2) - Complexitatea celui mai bun caz: apare atunci când matricea este deja sortată
O(n2) - Complexitatea medie a cazurilor: apare atunci când elementele matricei sunt în ordine amestecată (nici crescătoare, nici descendentă).
O(n2)
Complexitatea în timp a sortării selecției este aceeași în toate cazurile. La fiecare pas, trebuie să găsiți elementul minim și să îl puneți în locul potrivit. Elementul minim nu este cunoscut până la sfârșitul matricei nu este atins.
Complexitatea spațială:
Complexitatea spațiului se O(1)datorează faptului că tempse utilizează o variabilă suplimentară .
Selecție Sortare aplicații
Sortarea selecției este utilizată atunci când:
- va fi sortată o listă mică
- costul schimbului nu contează
- verificarea tuturor elementelor este obligatorie
- costul scrierii pe o memorie contează ca în memoria flash (numărul de scrieri / swap este
O(n)comparativ cu tipul cu bule)O(n2)
