logo

TechCodeview

Triedenie výberu – Štruktúra údajov a návody na algoritmy

Triedenie výberu je jednoduchý a efektívny triediaci algoritmus, ktorý funguje tak, že opakovane vyberá najmenší (alebo najväčší) prvok z nezoradené časti zoznamu a presúva ho do triedenej časti zoznamu.

Algoritmus opakovane vyberie najmenší (alebo najväčší) prvok z nezoradenej časti zoznamu a vymení ho s prvým prvkom nezoradenej časti. Tento proces sa opakuje pre zostávajúcu nevytriedenú časť, kým sa nezoradí celý zoznam.



Ako funguje algoritmus triedenia výberu?

Uvažujme ako príklad nasledujúce pole: arr[] = {64, 25, 12, 22, 11}

Prvý prechod:

  • Pre prvú pozíciu v triedenom poli sa postupne prechádza celé pole od indexu 0 po 4. Prvá pozícia, kde 64 je momentálne uložený, po prejdení celého poľa je jasné, že jedenásť je najnižšia hodnota.
  • Preto nahraďte 64 11. Po jednej iterácii jedenásť , čo je zhodou okolností najmenšia hodnota v poli, má tendenciu sa objavovať na prvej pozícii zoradeného zoznamu.

Algoritmus triedenia výberu | Zámena 1. prvku s minimom v poli



Druhý prechod:

  • Pre druhú pozíciu, kde je prítomná 25, opäť prejdite zvyšok poľa postupne.
  • Po traverzovaní sme to zistili 12 je druhá najnižšia hodnota v poli a mala by sa objaviť na druhom mieste v poli, preto tieto hodnoty zameňte.

Algoritmus triedenia výberu | zámena i=1 s ďalším minimálnym prvkom

Tretí prechod:



  • Teraz o tretie miesto, kde 25 je opäť prítomný, prejdite zvyšok poľa a nájdite tretiu najmenšiu hodnotu prítomnú v poli.
  • Pri prechádzaní, 22 vyšla ako tretia najmenšia hodnota a mala by sa objaviť na treťom mieste v poli, teda swap 22 s prvkom prítomným na tretej pozícii.

Algoritmus triedenia výberu | zámena i=2 s ďalším minimálnym prvkom

Štvrtý prechod:

  • Podobne pre štvrtú pozíciu prejdite zvyšok poľa a nájdite štvrtý najmenší prvok v poli
  • Ako 25 je 4. najnižšia hodnota, preto sa umiestni na štvrtej pozícii.

Algoritmus triedenia výberu | zámena i=3 s ďalším minimálnym prvkom

Piaty prechod:

  • Nakoniec sa najväčšia hodnota nachádzajúca sa v poli automaticky umiestni na poslednú pozíciu v poli
  • Výsledné pole je zoradené pole.

Algoritmus triedenia výberu | Povinné zoradené pole

Výber odporúčanej praxe Zoradiť Vyskúšajte!

Nižšie je uvedená implementácia vyššie uvedeného prí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; }>
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 # Vymeňte nájdený minimálny prvok za # prvý prvok A[i], A[min_idx] = A[min_idx], A[i] # Kód ovládača na testovanie vyššie ('Sorted array ') pre i v rozsahu(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; } } } // Kód ovládača $arr = array(64, 25, 12, 22, 11); $len = pocet($arr); select_sort($arr, $len); echo 'Zoradené pole: 
'; pre ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>
Výkon 
Sorted array: 11 12 22 25 64>

Analýza zložitosti výberu druhu

Časová zložitosť: Časová zložitosť triedenia výberu je O(N 2 ) pretože existujú dve vnorené slučky:

  • Jedna slučka na výber prvku poľa jeden po druhom = O(N)
  • Ďalšia slučka na porovnanie tohto prvku s každým iným prvkom poľa = O(N)
  • Preto celková zložitosť = O(N) * O(N) = O(N*N) = O(N2)

Pomocný priestor: O(1) ako jediná používaná dodatočná pamäť je určená na dočasné premenné pri výmene dvoch hodnôt v poli. Výberové triedenie nikdy nerobí viac ako O(N) swapov a môže byť užitočné, keď je zápis do pamäte nákladný.

krájanie java

Výhody algoritmu triedenia výberu

  • Jednoduché a ľahko pochopiteľné.
  • Funguje dobre s malými súbormi údajov.

Nevýhody algoritmu triedenia výberu

  • Výberové triedenie má časovú zložitosť O(n^2) v najhoršom a priemernom prípade.
  • Nefunguje dobre na veľkých súboroch údajov.
  • Nezachováva relatívne poradie položiek s rovnakými kľúčmi, čo znamená, že nie je stabilné.

Často kladené otázky o triedení výberu

Q1. Je algoritmus triedenia výberu stabilný?

Predvolená implementácia algoritmu triedenia výberu je nie stabilné . Dá sa však stabilizovať. Pozrite si prosím stabilný výberový rad pre podrobnosti.

Q2. Je algoritmus triedenia výberu zavedený?

Áno, Algoritmus triedenia výberu je algoritmus na mieste, pretože nevyžaduje priestor navyše.