Izbirno razvrščanje je preprost in učinkovit algoritem za razvrščanje, ki deluje tako, da večkrat izbere najmanjši (ali največji) element iz nerazvrščenega dela seznama in ga premakne na razvrščeni del seznama.
Algoritem vedno znova izbere najmanjši (ali največji) element iz nerazvrščenega dela seznama in ga zamenja s prvim elementom nerazvrščenega dela. Ta postopek se ponavlja za preostali nerazvrščeni del, dokler ni razvrščen celoten seznam.
Kako deluje algoritem za razvrščanje izbire?
Priporočena praksa Izbira Razvrsti Poskusi!Vzemimo za primer naslednjo matriko: arr[] = {64, 25, 12, 22, 11}
Prvi prehod:
- Za prvo pozicijo v razvrščeni matriki je celotna matrika zaporedno prečkana od indeksa 0 do 4. Prvi položaj, kjer 64 je trenutno shranjeno, po prehodu celotne matrike je jasno, da enajst je najnižja vrednost.
- Tako zamenjajte 64 z 11. Po eni ponovitvi enajst , ki je najmanjša vrednost v matriki, se običajno pojavi na prvem mestu razvrščenega seznama.
Algoritem za razvrščanje izbire | Zamenjava 1. elementa z najmanjšim v matriki
Drugi prehod:
- Za drugo pozicijo, kjer je prisotno 25, ponovno prečkajte preostanek niza zaporedno.
- Po prehodu smo to ugotovili 12 je druga najnižja vrednost v matriki in bi morala biti prikazana na drugem mestu v matriki, zato te vrednosti zamenjajte.
Algoritem za razvrščanje izbire | zamenjava i=1 z naslednjim minimalnim elementom
Tretji prehod:
- Zdaj pa za tretje mesto, kje 25 je ponovno prisoten, prečkati preostali del matrike in najti tretjo najmanjšo vrednost, ki je prisotna v matriki.
- Med prečkanjem, 22 izkazalo se je, da je tretja najmanjša vrednost in bi se morala pojaviti na tretjem mestu v matriki, torej zamenjati 22 z elementom na tretjem mestu.
Algoritem za razvrščanje izbire | zamenjava i=2 z naslednjim minimalnim elementom
Četrti prehod:
- Podobno za četrti položaj prečkajte preostali del matrike in poiščite četrti najmanjši element v matriki
- Kot 25 je 4. najnižja vrednost, zato se bo uvrstil na četrto mesto.
Algoritem za razvrščanje izbire | zamenjava i=3 z naslednjim minimalnim elementom
Peti prehod:
- Končno se največja vrednost v matriki samodejno postavi na zadnji položaj v matriki
- Dobljena matrika je razvrščena matrika.
Algoritem za razvrščanje izbire | Zahtevano razvrščeno polje
Spodaj je izvedba zgornjega pristopa:
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 # Zamenjaj najdeni najmanjši element s # prvim elementom A[i], A[min_idx] = A[min_idx], A[i] # Koda gonilnika za preizkus nad tiskanjem ('Razvrščena matrika ') za i v območju (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 // PHP program for implementation // of selection sort function selection_sort(&$arr, $n) { for($i = 0; $i < $n ; $i++) { $low = $i; for($j = $i + 1; $j < $n ; $j++) { if ($arr[$j] < $arr[$low]) { $low = $j; } } // swap the minimum value to $ith node if ($arr[$i]>$arr[$low]) { $tmp = $arr[$i]; $arr[$i] = $arr[$low]; $arr[$low] = $tmp; } } } // Koda gonilnika $arr = array(64, 25, 12, 22, 11); $len = štetje($arr); izbor_razvrsti($arr, $len); echo 'Razvrščena matrika:
'; za ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed // by Deepika Gupta. ?>> Izhod
Sorted array: 11 12 22 25 64>
Analiza kompleksnosti izbirnega razvrščanja
Časovna zapletenost: Časovna zapletenost Selection Sort je O(N 2 ) ker obstajata dve ugnezdeni zanki:
- Ena zanka za izbiro elementov matrike enega za drugim = O(N)
- Druga zanka za primerjavo tega elementa z vsemi drugimi elementi matrike = O(N)
- Zato je skupna kompleksnost = O(N) * O(N) = O(N*N) = O(N2)
Pomožni prostor: O(1), saj je edini uporabljen dodatni pomnilnik za začasne spremenljivke med zamenjavo dveh vrednosti v Array. Izbirno razvrščanje nikoli ne naredi več kot O(N) zamenjav in je lahko koristno, ko je pisanje v pomnilnik drago.
meni z nastavitvami telefona Android
Prednosti algoritma za razvrščanje izbire
- Enostavno in lahko razumljivo.
- Dobro deluje z majhnimi nabori podatkov.
Slabosti algoritma za razvrščanje izbire
- Izbirno razvrščanje ima časovno kompleksnost O(n^2) v najslabšem in povprečnem primeru.
- Ne deluje dobro na velikih zbirkah podatkov.
- Ne ohranja relativnega vrstnega reda elementov z enakimi ključi, kar pomeni, da ni stabilen.
Pogosto zastavljena vprašanja o razvrščanju izbire
Q1. Ali je algoritem za razvrščanje izbire stabilen?
Privzeta izvedba algoritma za razvrščanje izbire je ni stabilen . Vendar ga je mogoče narediti stabilno. Oglejte si stabilen izbor Razvrsti za podrobnosti.
Q2. Ali je algoritem za razvrščanje izbire na mestu?
Da, algoritem za razvrščanje izbire je algoritem na mestu, saj ne potrebuje dodatnega prostora.