Atlase Kārtot algoritmu

Šajā apmācībā jūs uzzināsiet, kā darbojas atlases kārtošana. Jūs atradīsit arī atlases kārtošanas piemērus C, C ++, Java un Python.

Atlases kārtošana ir algoritms, kas izvēlas mazāko elementu no nešķirotā saraksta katrā atkārtojumā un ievieto šo elementu nešķirotā saraksta sākumā.

Kā darbojas atlases kārtošana?

  1. Pirmo elementu iestatiet kā minimum. Atlasiet pirmo elementu kā minimumu
  2. Salīdziniet minimumar otro elementu. Ja otrais elements ir mazāks par minimum, piešķiriet otro elementu kā minimum.
    Salīdziniet minimumar trešo elementu. Atkal, ja trešais elements ir mazāks, tad piešķiriet minimumtrešajam elementam citādi neko nedarīt. Process turpinās līdz pēdējam elementam. Salīdziniet minimumu ar atlikušajiem elementiem
  3. Pēc katras atkārtošanas minimumtiek ievietots nešķirotā saraksta priekšpusē. Apmainiet pirmo ar minimālo
  4. Katrā atkārtojumā indeksēšana sākas no pirmā nešķirotā elementa. 1. līdz 3. darbību atkārto, līdz visi elementi ir novietoti pareizajā pozīcijā. Pirmais atkārtojums Otrais atkārtojums Trešais atkārtojums Ceturtais atkārtojums

Atlase Kārtot algoritmu

 sortSort (masīvs, izmērs) atkārtot (izmērs - 1) reizes iestatiet pirmo nešķiroto elementu kā minimumu katram no nešķirotajiem elementiem, ja elements <currentMinimum iestatītais elements kā jauns minimālais mijmaiņas minimums ar pirmo nešķiroto pozīcijas beigu atlasi

Python, Java un C / C ++ piemēri

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

Sarežģītība

Cikls Salīdzināšanas numurs
1 (n-1)
2 (n-2)
3 (n-3)
… …
Pēdējais 1

Salīdzinājumu skaits: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2gandrīz vienāds ar .n2

Sarežģītība =O(n2)

Tāpat mēs varam analizēt sarežģītību, vienkārši novērojot cilpu skaitu. Ir 2 cilpas, tāpēc sarežģītība ir .n*n = n2

Laika sarežģītība:

  • Sliktākā gadījuma sarežģītība: ja mēs vēlamies kārtot augošā secībā un masīvs ir dilstošā secībā, notiek vissliktākais gadījums.O(n2)
  • Labākā gadījuma sarežģītība: tas notiek, ja masīvs jau ir sakārtotsO(n2)
  • Vidējā gadījuma sarežģītība: tā notiek, ja masīva elementi ir sajaukti secībā (ne augšupejoši, ne dilstoši).O(n2)

Atlases kārtošanas laika sarežģītība visos gadījumos ir vienāda. Katrā solī jums jāatrod minimālais elements un jānovieto tas pareizajā vietā. Minimālais elements nav zināms, kamēr nav sasniegta masīva beigas.

Kosmosa sarežģītība:

Kosmoss ir sarežģīts O(1)tāpēc, ka temptiek izmantots papildu mainīgais .

Atlasiet Lietojumu kārtošana

Atlases kārtošana tiek izmantota, ja:

  • ir jāšķiro neliels saraksts
  • maiņas izmaksām nav nozīmes
  • visu elementu pārbaude ir obligāta
  • rakstīšanas atmiņā izmaksas ir svarīgas, piemēram, zibatmiņā (rakstīšanas / mijmaiņas darījumu skaits ir O(n)salīdzināms ar burbuļu kārtošanu)O(n2)

Interesanti raksti...