Algoritem sortiranja izbora

V tej vadnici boste izvedeli, kako deluje razvrščanje po izboru. Prav tako boste našli delovne primere razvrščanja v C, C ++, Java in Python.

Izbirno razvrščanje je algoritem, ki izbere najmanjši element s nesortiranega seznama v vsaki ponovitvi in ​​ga postavi na začetek nesortiranega seznama.

Kako deluje sortiranje izbora?

  1. Prvi element nastavite kot minimum. Izberite najmanj prvi element
  2. Primerjaj minimumz drugim elementom. Če je drugi element manjši od minimumdrugega, dodelite drugemu elementu minimum.
    Primerjaj minimums tretjim elementom. Če je tretji element manjši, ga dodelite minimumtretjemu elementu, sicer ne naredite ničesar. Postopek se nadaljuje do zadnjega elementa. Primerjajte najmanj s preostalimi elementi
  3. Po vsaki ponovitvi minimumse postavi na sprednji del nerazvrščenega seznama. Zamenjajte prvo z minimalno
  4. Za vsako ponovitev se indeksiranje začne s prvim nesortiranim elementom. Koraki od 1 do 3 se ponavljajo, dokler se vsi elementi ne postavijo v pravilne položaje. Prva ponovitev Druga ponovitev Tretja ponovitev Četrta ponovitev

Algoritem sortiranja izbora

 selectionSort (matrika, velikost) ponovitev (velikost - 1) krat nastavi prvi nesortirani element kot minimum za vsakega od nesortiranih elementov, če element <currentMinimum set element kot nov najmanjši swap minimum s prvo nesortirano pozicijo na koncu selectionSort

Primeri Python, Java in 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); )

Kompleksnost

Cikel Število primerjav
1. (n-1)
2. (n-2)
3. (n-3)
… …
zadnji 1.

Število primerjav: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2skoraj enako .n2

Kompleksnost =O(n2)

Zapletenost lahko analiziramo tudi tako, da preprosto opazujemo število zank. Obstajata 2 zanki, tako da je zapletenost .n*n = n2

Časovne zapletenosti:

  • Najslabša zapletenost: če želimo razvrstiti v naraščajočem vrstnem redu in je matrika v padajočem vrstnem redu, se zgodi najslabši primer.O(n2)
  • Najboljša zapletenost: Pojavi se, ko je polje že razvrščenoO(n2)
  • Povprečna zapletenost primerov: Pojavi se, če so elementi matrike v vrstnem redu (niti naraščajoče niti padajoče).O(n2)

Časovna zapletenost izbire je v vseh primerih enaka. Na vsakem koraku morate najti najmanjši element in ga postaviti na pravo mesto. Najmanjši element ni znan, dokler ni dosežen konec matrike.

Zapletenost vesolja:

Zapletenost prostora je O(1)zato, ker se uporablja dodatna spremenljivka temp.

Aplikacije za razvrščanje po izboru

Razvrstitev izbora se uporablja, kadar:

  • majhen seznam je treba razvrstiti
  • stroški zamenjave niso pomembni
  • preverjanje vseh elementov je obvezno
  • stroški pisanja v pomnilnik so pomembni, kot v bliskovnem pomnilniku (število zapisov / zamenjav je O(n)v primerjavi z mehurčki)O(n2)

Zanimive Članki...