Sortare selecție este un algoritm de sortare simplu și eficient care funcționează prin selectarea în mod repetat a celui mai mic (sau cel mai mare) element din porțiunea nesortată a listei și mutarea acestuia în porțiunea sortată a listei.
Algoritmul selectează în mod repetat cel mai mic (sau cel mai mare) element din porțiunea nesortată a listei și îl schimbă cu primul element al părții nesortate. Acest proces se repetă pentru porțiunea rămasă nesortată până când întreaga listă este sortată.
Cum funcționează algoritmul de sortare a selecției?
Selecție de practică recomandată Sortare Încercați!Să considerăm următoarea matrice ca exemplu: arr[] = {64, 25, 12, 22, 11}
Prima trecere:
- Pentru prima poziție din tabloul sortat, întregul tablou este parcurs de la indexul 0 la 4 secvenţial. Prima pozitie unde 64 este stocat în prezent, după parcurgerea întregii matrice este clar că unsprezece este cea mai mică valoare.
- Astfel, înlocuiți 64 cu 11. După o iterație unsprezece , care se întâmplă să fie cea mai mică valoare din matrice, tinde să apară în prima poziție a listei sortate.
Algoritm de sortare a selecției | Schimbarea primului element cu minimul din matrice
A doua trecere:
- Pentru a doua poziție, unde este prezent 25, traversați din nou restul matricei într-o manieră secvențială.
- După ce am străbătut, am aflat că 12 este a doua cea mai mică valoare din matrice și ar trebui să apară pe locul doi în matrice, astfel schimbă aceste valori.
Algoritm de sortare a selecției | schimbând i=1 cu următorul element minim
A treia trecere:
- Acum, pe locul trei, unde 25 este prezent traversează din nou restul matricei și găsește a treia cea mai mică valoare prezentă în matrice.
- În timpul traversării, 22 a ieșit a fi a treia cea mai mică valoare și ar trebui să apară pe locul trei în matrice, astfel încât să se schimbe 22 cu element prezent pe poziţia a treia.
Algoritm de sortare a selecției | schimbând i=2 cu următorul element minim
A patra trecere:
- În mod similar, pentru a patra poziție, traversați restul matricei și găsiți al patrulea cel mai mic element din matrice
- La fel de 25 este a patra cea mai mică valoare, prin urmare, se va plasa pe a patra poziție.
Algoritm de sortare a selecției | schimbând i=3 cu următorul element minim
A cincea trecere:
- În cele din urmă, cea mai mare valoare prezentă în matrice este plasată automat în ultima poziție din matrice
- Matricea rezultată este matricea sortată.
Algoritm de sortare a selecției | Matrice sortată obligatorie
Mai jos este implementarea abordării de mai sus:
C++ // C++ program for implementation of // selection sort #include using namespace std; // Function for Selection sort void selectionSort(int arr[], int n) { int i, j, min_idx; // One by one move boundary of // unsorted subarray for (i = 0; i < n - 1; i++) { // Find the minimum element in // unsorted array min_idx = i; for (j = i + 1; j < n; j++) { if (arr[j] < arr[min_idx]) min_idx = j; } // Swap the found minimum element // with the first element if (min_idx != i) swap(arr[min_idx], arr[i]); } } // Function to print an array void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) { cout << arr[i] << ' '; cout << endl; } } // Driver program int main() { int arr[] = { 64, 25, 12, 22, 11 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call selectionSort(arr, n); cout << 'Sorted array:
'; printArray(arr, n); return 0; } // This is code is contributed by rathbhupendra> C // C program for implementation of selection sort #include void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; } void selectionSort(int arr[], int n) { int i, j, min_idx; // One by one move boundary of unsorted subarray for (i = 0; i < n-1; i++) { // Find the minimum element in unsorted array min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swap the found minimum element with the first element if(min_idx != i) swap(&arr[min_idx], &arr[i]); } } /* Function to print an array */ void printArray(int arr[], int size) { int i; for (i=0; i < size; i++) printf('%d ', arr[i]); printf('
'); } // Driver program to test above functions int main() { int arr[] = {64, 25, 12, 22, 11}; int n = sizeof(arr)/sizeof(arr[0]); selectionSort(arr, n); printf('Sorted array:
'); printArray(arr, n); return 0; }> Java // Java program for implementation of Selection Sort import java.io.*; public class SelectionSort { void sort(int arr[]) { int n = arr.length; // One by one move boundary of unsorted subarray for (int i = 0; i < n-1; i++) { // Find the minimum element in unsorted array int min_idx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swap the found minimum element with the first // element int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } } // Prints the array void printArray(int arr[]) { int n = arr.length; for (int i=0; i Python3 # Python program for implementation of Selection # Sort A = [64, 25, 12, 22, 11] # Traverse through all array elements for i in range(len(A)-1): # Find the minimum element in remaining # unsorted array min_idx = i for j in range(i+1, len(A)): if A[min_idx]>A[j]: min_idx = j # Schimbați elementul minim găsit cu # primul element A[i], A[min_idx] = A[min_idx], A[i] # Cod driver de testat deasupra tipăririi ('Matrice sortată ') pentru i în interval(len(A)): print(A[i],end=' ')> C# // C# program for implementation // of Selection Sort using System; class GFG { static void sort(int []arr) { int n = arr.Length; // One by one move boundary of unsorted subarray for (int i = 0; i < n - 1; i++) { // Find the minimum element in unsorted array int min_idx = i; for (int j = i + 1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swap the found minimum element with the first // element int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } } // Prints the array static void printArray(int []arr) { int n = arr.Length; for (int i=0; i Javascript >>>PHP>>>
Ieșire Complexitatea timpului: Complexitatea de timp a sortării selecției este PE 2 ) deoarece există două bucle imbricate: - O buclă pentru a selecta un element al matricei unul câte unul = O(N)
- O altă buclă pentru a compara acel element cu orice alt element Array = O(N)
- Prin urmare, complexitatea globală = O(N) * O(N) = O(N*N) = O(N2)
Spațiu auxiliar: O(1), deoarece singura memorie suplimentară folosită este pentru variabilele temporare în timp ce schimbăm două valori în Array. Sortarea de selecție nu face niciodată mai mult de schimburi O(N) și poate fi utilă atunci când scrierea în memorie este costisitoare.
vârsta rihanna
Avantajele algoritmului de sortare de selecție
- Simplu și ușor de înțeles.
- Funcționează bine cu seturi de date mici.
Dezavantajele algoritmului de sortare a selecției
- Sortarea selecției are o complexitate de timp de O(n^2) în cel mai rău și mediu caz.
- Nu funcționează bine pe seturi mari de date.
- Nu păstrează ordinea relativă a elementelor cu chei egale, ceea ce înseamnă că nu este stabil.
Întrebări frecvente privind sortarea selecției
Î1. Algoritmul de sortare al selecției este stabil?
Implementarea implicită a algoritmului de sortare a selecției este instabil . Cu toate acestea, poate fi stabilizat. Vă rugăm să vedeți Stabil Selection Sort pentru detalii.
Q2. Algoritmul de sortare al selecției este în vigoare?
Da, algoritmul de sortare a selecției este un algoritm pe loc, deoarece nu necesită spațiu suplimentar.