Výběr řazení je jednoduchý a účinný třídicí algoritmus, který funguje tak, že opakovaně vybírá nejmenší (nebo největší) prvek z neseřazené části seznamu a přesouvá jej do seřazené části seznamu.
Algoritmus opakovaně vybírá nejmenší (nebo největší) prvek z neseřazené části seznamu a zaměňuje jej s prvním prvkem neseřazené části. Tento proces se opakuje pro zbývající neseřazenou část, dokud není setříděn celý seznam.
Jak funguje algoritmus třídění výběru?
Výběr doporučené praxe Seřadit Vyzkoušejte!Uvažujme jako příklad následující pole: arr[] = {64, 25, 12, 22, 11}
První průchod:
- Pro první pozici v seřazeném poli se postupně prochází celé pole od indexu 0 do 4. První pozice kde 64 je uložen v současnosti, po projetí celého pole je jasné, že jedenáct je nejnižší hodnota.
- Nahraďte tedy 64 za 11. Po jedné iteraci jedenáct , což je shodou okolností nejmenší hodnota v poli, má tendenci se objevovat na první pozici seřazeného seznamu.
Výběr Algoritmus řazení | Prohození 1. prvku s minimem v poli
Druhý průchod:
- Pro druhou polohu, kde je přítomna 25, znovu projděte zbytek pole postupně.
- Po procházení jsme to zjistili 12 je druhá nejnižší hodnota v poli a měla by se objevit na druhém místě v poli, proto tyto hodnoty prohoďte.
Výběr Algoritmus řazení | prohození i=1 s dalším minimálním prvkem
Třetí průchod:
- Teď na třetí místo, kde 25 je přítomen znovu projděte zbytek pole a najděte třetí nejmenší hodnotu přítomnou v poli.
- Při procházení, 22 vyšla jako třetí nejmenší hodnota a měla by se objevit na třetím místě v poli, tedy swap 22 s prvkem přítomným na třetí pozici.
Výběr Algoritmus řazení | prohození i=2 s dalším minimálním prvkem
Čtvrtý průchod:
- Podobně pro čtvrtou pozici projděte zbytek pole a najděte čtvrtý nejmenší prvek v poli
- Tak jako 25 je 4. nejnižší hodnota, proto se umístí na čtvrté pozici.
Výběr Algoritmus řazení | prohození i=3 s dalším minimálním prvkem
Pátý průchod:
- Konečně se největší hodnota přítomná v poli automaticky umístí na poslední pozici v poli
- Výsledné pole je seřazené pole.
Výběr Algoritmus řazení | Povinné seřazené pole
Níže je uvedena implementace výše uvedeného přístupu:
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; }> Jáva // 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 # Prohoďte nalezený minimální prvek s # prvním prvkem A[i], A[min_idx] = A[min_idx], A[i] # Kód ovladače k otestování nad tiskem ('Sorted array ') pro i v rozsahu(délka(A)): print(A[i],konec=' ')> 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; } } } // Kód ovladače $arr = array(64, 25, 12, 22, 11); $len = pocet($arr); select_sort($arr, $len); echo 'Seřazené pole:
'; pro ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed // by Deepika Gupta. ?>> Výstup
Sorted array: 11 12 22 25 64>
Analýza složitosti výběru druhu
Časová náročnost: Časová složitost třídění výběru je NA 2 ) protože existují dvě vnořené smyčky:
- Jedna smyčka pro výběr prvku pole jeden po druhém = O(N)
- Další smyčka pro porovnání tohoto prvku s každým dalším prvkem pole = O(N)
- Proto celková složitost = O(N) * O(N) = O(N*N) = O(N2)
Pomocný prostor: O(1) jako jediná paměť navíc slouží pro dočasné proměnné při záměně dvou hodnot v poli. Výběrové řazení nikdy nevytváří více než O(N) swapů a může být užitečné, když je zápis do paměti nákladný.
bash zkontrolujte, zda je nastavena proměnná prostředí
Výhody algoritmu třídění výběru
- Jednoduché a snadno pochopitelné.
- Funguje dobře s malými datovými sadami.
Nevýhody algoritmu třídění výběru
- Výběrové řazení má časovou složitost O(n^2) v nejhorším a průměrném případě.
- Nefunguje dobře na velkých souborech dat.
- Nezachovává relativní pořadí položek se stejnými klíči, což znamená, že není stabilní.
Často kladené otázky o třídění výběru
Q1. Je algoritmus třídění výběru stabilní?
Výchozí implementace algoritmu třídění výběru je nestabilní . Může však být stabilní. Podívejte se prosím na stabilní výběrové řazení pro detaily.
Q2. Je algoritmus třídění výběru na místě?
Ano, Algoritmus třídění výběru je algoritmus na místě, protože nevyžaduje další místo.