Algoritmus řazení

V tomto kurzu se dozvíte, jak funguje třídění výběru. Pracovní příklady výběru řazení najdete také v jazycích C, C ++, Java a Python.

Třídění výběru je algoritmus, který vybere nejmenší prvek z netříděného seznamu v každé iteraci a umístí tento prvek na začátek netříděného seznamu.

Jak funguje řazení výběru?

  1. Nastavte první prvek jako minimum. Jako první vyberte první prvek
  2. Porovnejte minimums druhým prvkem. Pokud je druhý prvek menší než minimum, přiřaďte druhý prvek jako minimum.
    Porovnejte minimums třetím prvkem. Opět platí, že pokud je třetí prvek menší, pak přiřaďte minimumtřetímu prvku, jinak nedělejte nic. Proces pokračuje až do posledního prvku. Porovnejte minimum se zbývajícími prvky
  3. Po každé iteraci minimumje umístěn v přední části netříděného seznamu. Zaměňte první s minimem
  4. Pro každou iteraci začíná indexování od prvního netříděného prvku. Kroky 1 až 3 se opakují, dokud nejsou všechny prvky umístěny do správné polohy. První iterace Druhá iterace Třetí iterace Čtvrtá iterace

Algoritmus výběru řazení

 selectionSort (array, size) 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

Python, Java a C / C ++ příklady

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); )

Složitost

Cyklus Počet srovnání
1. místo (n-1)
2. místo (n-2)
3. místo (n-3)
… …
poslední 1

Počet srovnání: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2téměř se rovná .n2

Složitost =O(n2)

Můžeme také analyzovat složitost pouhým sledováním počtu smyček. K dispozici jsou 2 smyčky, takže složitost je .n*n = n2

Časová složitost:

  • Složitost nejhoršího případu: Pokud chceme třídit vzestupně a pole je v sestupném pořadí, nastane nejhorší případ.O(n2)
  • Složitost nejlepších případů: Objeví se, když je pole již tříděnoO(n2)
  • Průměrná složitost případu: Dochází k němu, když jsou prvky pole v neuspořádaném pořadí (ani vzestupně, ani sestupně).O(n2)

Časová složitost výběru je ve všech případech stejná. Na každém kroku musíte najít minimální prvek a umístit jej na správné místo. Minimální prvek není znám, dokud není dosaženo konce pole.

Složitost prostoru:

Složitost prostoru spočívá v tom, O(1)že se používá zvláštní proměnná temp.

Výběr Třídit aplikace

Výběr se používá, když:

  • malý seznam je třeba třídit
  • náklady na výměnu nezáleží
  • kontrola všech prvků je povinná
  • náklady na zápis do paměti jsou důležité jako ve flash paměti (počet zápisů / swapů je O(n)ve srovnání s bublinovým tříděním)O(n2)

Zajímavé články...