Algoritmus triedenia výberu

V tomto návode sa dozviete, ako funguje triedenie výberu. Pracovné príklady triedenia výberu nájdete aj v jazykoch C, C ++, Java a Python.

Výberové triedenie je algoritmus, ktorý vyberie najmenší prvok z netriedeného zoznamu v každej iterácii a umiestni tento prvok na začiatok netriedeného zoznamu.

Ako funguje triedenie podľa výberu?

  1. Nastaviť prvý prvok ako minimum. Vyberte prvý prvok ako minimum
  2. Porovnaj minimums druhým prvkom. Ak je druhý prvok menší ako minimum, priraďte druhý prvok ako minimum.
    Porovnaj minimums tretím prvkom. Opäť platí, že ak je tretí prvok menší, potom priraďte minimumk tretiemu prvku inak nič. Proces pokračuje až do posledného prvku. Porovnajte minimum so zvyšnými prvkami
  3. Po každej iterácii minimumje značka umiestnená v prednej časti netriedeného zoznamu. Zamieňajte prvé s minimom
  4. Pre každú iteráciu sa indexovanie začína od prvého netriedeného prvku. Kroky 1 až 3 sa opakujú, kým nie sú všetky prvky umiestnené v správnej polohe. Prvá iterácia Druhá iterácia Tretia iterácia Štvrtá iterácia

Algoritmus triedenia výberu

 selectionSort (pole, veľkosť) repeat (size - 1) times set the first unorted element as the minimum for each of the unorted elements if element <currentMinimum set element as new minimum swap minimum with first unorted position end selectionSort

Príklady jazyka Python, Java a 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); )

Zložitosť

Cyklus Číslo porovnania
1 (n-1)
2 (n-2)
3 (n-3)
… …
posledný 1

Počet porovnaní: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2takmer sa rovná .n2

zložitosť =O(n2)

Tiež môžeme analyzovať zložitosť jednoduchým sledovaním počtu slučiek. K dispozícii sú 2 slučky, takže zložitosť je .n*n = n2

Časová zložitosť:

  • Najhoršia zložitosť: Ak chceme triediť vzostupne a pole je v zostupnom poradí, nastane najhorší prípad.O(n2)
  • Zložitosť najlepších prípadov: Vyskytuje sa, keď je pole už zoradenéO(n2)
  • Priemerná zložitosť prípadu: Vyskytuje sa, keď sú prvky poľa v neusporiadanom poradí (ani vzostupne, ani zostupne).O(n2)

Časová zložitosť výberu je vo všetkých prípadoch rovnaká. Na každom kroku musíte nájsť minimálny prvok a umiestniť ho na správne miesto. Minimálny prvok nie je známy, kým sa nedosiahne koniec poľa.

Zložitosť priestoru:

Zložitosť priestoru spočíva v tom, O(1)že sa používa ďalšia premenná temp.

Výber Triedenie aplikácií

Výber sa použije, keď:

  • malý zoznam sa má triediť
  • náklady na výmenu nie sú dôležité
  • kontrola všetkých prvkov je povinná
  • cena zápisu do pamäte je dôležitá ako vo flash pamäti (počet zápisov / swapov je O(n)v porovnaní s bublinovým triedením)O(n2)

Zaujímavé články...