Valinnan lajittelualgoritmi

Tässä opetusohjelmassa opit, miten valintalajittelu toimii. Lisäksi löydät toimivia esimerkkejä valintalajittelusta C, C ++, Java ja Python.

Valintalajittelu on algoritmi, joka valitsee pienimmän elementin lajittelemattomasta luettelosta kussakin iteraatiossa ja sijoittaa kyseisen elementin lajittelemattoman luettelon alkuun.

Kuinka valintalajittelu toimii?

  1. Aseta ensimmäinen elementti minimum. Valitse vähintään ensimmäinen elementti
  2. Vertaa minimumtoiseen elementtiin. Jos toinen elementti on pienempi kuin minimum, määritä toinen elementti nimellä minimum.
    Vertaa minimumkolmanteen elementtiin. Jälleen kerran, jos kolmas elementti on pienempi, määritä sitten minimumkolmannelle elementille muuten mitään. Prosessi jatkuu viimeiseen elementtiin asti. Vertaa minimiä muihin elementteihin
  3. Jokaisen iteraation jälkeen minimumsijoitetaan lajittelemattoman luettelon eteen. Vaihda ensimmäinen minimillä
  4. Kunkin iteraation kohdalla indeksointi alkaa ensimmäisestä lajittelemattomasta elementistä. Vaiheet 1-3 toistetaan, kunnes kaikki elementit on asetettu oikeisiin paikkoihinsa. Ensimmäinen iterointi Toinen iteraatio Kolmas iteraatio Neljäs iteraatio

Valinnan lajittelualgoritmi

 selectSort (taulukko, koko) toisto (koko - 1) kertaa aseta ensimmäinen lajittelematon elementti minimiksi jokaiselle lajittelemattomalle elementille, jos elementti <currentMinimum set elementti uudeksi vähimmäisvaihtominimiksi ensimmäisen lajittelemattoman sijainnin lopussa

Python-, Java- ja C / C ++ -esimerkkejä

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

Monimutkaisuus

Sykli Vertailun määrä
1 (n-1)
2. (n-2)
3. (n-3)
… …
kestää 1

Vertailujen lukumäärä: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2lähes yhtä suuri kuin .n2

Monimutkaisuus =O(n2)

Voimme myös analysoida monimutkaisuutta yksinkertaisesti tarkkailemalla silmukoiden määrää. Silmukoita on 2, joten monimutkaisuus on .n*n = n2

Ajan monimutkaisuus:

  • Pahimman tapauksen monimutkaisuus: Jos haluamme lajitella nousevassa järjestyksessä ja taulukko on laskevassa järjestyksessä, tapahtuu pahin tapaus.O(n2)
  • Parhaan tapauksen monimutkaisuus: Se tapahtuu, kun taulukko on jo lajiteltuO(n2)
  • Keskimääräinen tapauksen monimutkaisuus: Se tapahtuu, kun matriisin elementit ovat sekaisin (ei nousevia eikä laskevia).O(n2)

Valintalajin ajan monimutkaisuus on sama kaikissa tapauksissa. Jokaisessa vaiheessa sinun on löydettävä minimielementti ja laitettava se oikeaan paikkaan. Minimielementtiä ei tiedetä ennen kuin taulukon loppu on saavutettu.

Avaruuden monimutkaisuus:

Avaruuden monimutkaisuus johtuu O(1)siitä, että käytetään ylimääräistä muuttujaa temp.

Lajittele sovellukset

Valintalajittelua käytetään, kun:

  • pieni luettelo on lajiteltava
  • vaihtamisen kustannuksilla ei ole merkitystä
  • kaikkien elementtien tarkastaminen on pakollista
  • muistiin kirjoittamisen kustannukset ovat tärkeitä kuten flash-muistissa (kirjoitus- / vaihtosuhteiden määrä O(n)verrattuna kuplalajitteluun)O(n2)

Mielenkiintoisia artikkeleita...