Pasirinkimo rūšiavimo algoritmas

Šioje pamokoje sužinosite, kaip veikia atrankos rūšiavimas. Taip pat rasite veikiančių pasirinkimo rūšiavimo pavyzdžių C, C ++, Java ir Python.

Pasirinkimo rūšiavimas yra algoritmas, kuris pasirenka mažiausią elementą iš nerūšiuoto sąrašo kiekvienoje iteracijoje ir padeda tą elementą nerūšiuoto sąrašo pradžioje.

Kaip veikia atrankos rūšiavimas?

  1. Pirmąjį elementą nustatykite kaip minimum. Pasirinkite bent jau pirmąjį elementą
  2. Palyginkite minimumsu antruoju elementu. Jei antrasis elementas yra mažesnis nei minimum, priskirkite antrąjį elementą kaip minimum.
    Palyginkite minimumsu trečiuoju elementu. Vėlgi, jei trečiasis elementas yra mažesnis, tada priskirkite minimumtrečiajam elementui kitaip nieko nedarykite. Procesas tęsiasi iki paskutinio elemento. Palyginkite minimumą su likusiais elementais
  3. Po kiekvieno pakartojimo minimumdedamas į nerūšiuoto sąrašo priekį. Pirmąjį pakeiskite minimaliu
  4. Kiekvienos kartojimo atveju indeksavimas pradedamas nuo pirmo nerūšiuoto elemento. 1–3 žingsniai kartojami tol, kol visi elementai bus išdėstyti teisingose ​​vietose. Pirmas kartojimas Antras kartojimas Trečias kartojimas Ketvirtas kartojimas

Pasirinkimo rūšiavimo algoritmas

 selectionSort (masyvas, dydis) pakartojimas (dydis - 1) kartus nustatykite pirmąjį nerūšiuotą elementą kaip minimumą kiekvienam nerūšiuotam elementui, jei elementas <currentMinimum nustatytas elementas kaip naujas minimalus apsikeitimo minimumas su pirmuoju nerūšiuotu pozicijos pabaigos pasirinkimu

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

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

Sudėtingumas

Ciklas Palyginimo skaičius
1-oji (n-1)
2-oji (n-2)
3 d (n-3)
… …
paskutinis 1

Palyginimų skaičius: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2beveik lygus .n2

Sudėtingumas =O(n2)

Be to, mes galime analizuoti sudėtingumą, tiesiog stebėdami kilpų skaičių. Yra 2 kilpos, taigi sudėtingumas yra .n*n = n2

Laiko sudėtingumas:

  • Blogiausio atvejo sudėtingumas: Jei norime rūšiuoti didėjimo tvarka ir masyvas yra mažėjimo tvarka, įvyksta blogiausias atvejis.O(n2)
  • Geriausio atvejo sudėtingumas: jis atsiranda, kai masyvas jau yra rūšiuojamasO(n2)
  • Vidutinis atvejo sudėtingumas: Tai įvyksta, kai masyvo elementai yra susimaišę (nei didėjant, nei mažėjant).O(n2)

Pasirinkimo rūšiavimo laiko sudėtingumas visais atvejais yra vienodas. Kiekviename žingsnyje turite rasti minimalų elementą ir įdėti jį į reikiamą vietą. Minimalus elementas nėra žinomas, kol nepasiekiama masyvo pabaiga.

Erdvės sudėtingumas:

Erdvė yra sudėtinga, O(1)nes naudojamas papildomas kintamasis temp.

Pasirinkimas Rūšiuoti programas

Pasirinkimo rūšiavimas naudojamas, kai:

  • nedidelis sąrašas turi būti rūšiuojamas
  • apsikeitimo kaina neturi reikšmės
  • patikrinti visus elementus yra privaloma
  • rašymo į atmintį kaina yra svarbi kaip „flash“ atmintyje (rašymo / apsikeitimo skaičius yra O(n)lyginamas su burbulų rūšiavimu)O(n2)

Įdomios straipsniai...