Algoritam sortiranja odabira

U ovom vodiču naučit ćete kako funkcionira sortiranje odabira. Također ćete pronaći radne primjere sortiranja odabira na C, C ++, Java i Python.

Sortiranje odabira algoritam je koji odabire najmanji element s nerazvrstanog popisa u svakoj iteraciji i postavlja taj element na početak nesortiranog popisa.

Kako sortiranje odabira djeluje?

  1. Postavite prvi element kao minimum. Odaberite prvi element kao minimum
  2. Usporedite minimums drugim elementom. Ako je drugi element manji od minimum, dodijelite drugi element kao minimum.
    Usporedite minimums trećim elementom. Opet, ako je treći element manji, tada dodijelite minimumtrećem elementu, u suprotnom ne poduzmite ništa. Proces traje do posljednjeg elementa. Usporedite minimum s preostalim elementima
  3. Nakon svake iteracije minimumstavlja se ispred nerazvrstanog popisa. Zamijenite prvu s minimalnom
  4. Za svaku iteraciju indeksiranje započinje od prvog nesortiranog elementa. Koraci od 1 do 3 ponavljaju se dok se svi elementi ne postave na svoje točne položaje. Prva ponavljanja Druga ponavljanja Treća ponavljanja Četvrta ponavljanja

Algoritam sortiranja odabira

 selectionSort (array, size) repeat (size - 1) puta postavi prvi nerazvrstani element kao minimum za svaki od nerazvrstanih elemenata ako je element <currentMinimum set element kao novi minimalni swap minimum s prvim nerazvrstanim položajem na kraju selectionSort

Primjeri Pythona, Java i 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); )

Složenost

Ciklus Broj usporedbe
1. (n-1)
2. (n-2)
3. (n-3)
… …
posljednji 1

Broj usporedbi: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2gotovo jednako .n2

Složenost =O(n2)

Također, složenost možemo analizirati jednostavnim promatranjem broja petlji. Postoje 2 petlje pa je složenost .n*n = n2

Složenost vremena:

  • Najgori složeni slučaj: Ako želimo sortirati u rastućem redoslijedu, a niz je u silaznom redoslijedu, tada se događa najgori slučaj.O(n2)
  • Složenost najboljeg slučaja: Događa se kad je niz već sortiranO(n2)
  • Prosječna složenost slučaja: Događa se kada su elementi niza pomiješanim redoslijedom (niti uzlazno niti silazno).O(n2)

Složenost vremena odabira sorte u svim je slučajevima ista. Na svakom koraku morate pronaći minimalni element i postaviti ga na pravo mjesto. Minimalni element nije poznat dok se ne postigne kraj niza.

Složenost prostora:

Složenost prostora je O(1)zato što se koristi dodatna varijabla temp.

Aplikacije za sortiranje odabira

Razvrstavanje odabira koristi se kada:

  • treba sortirati mali popis
  • trošak zamjene nije važan
  • provjera svih elemenata je obavezna
  • trošak zapisivanja u memoriju važan je kao u flash memoriji (broj upisa / zamjena je O(n)u usporedbi s razvrstavanjem mjehurića)O(n2)

Zanimljivi članci...