Urvals sorteringsalgoritm

I den här handledningen lär du dig hur urvalsortering fungerar. Du hittar också arbetsexempel på urvalsortering i C, C ++, Java och Python.

Urvalsortering är en algoritm som väljer det minsta elementet från en osorterad lista i varje iteration och placerar det elementet i början av den osorterade listan.

Hur fungerar urvalssortering?

  1. Ställ in det första elementet som minimum. Välj det första elementet som minimum
  2. Jämför minimummed det andra elementet. Om det andra elementet är mindre än minimum, tilldela det andra elementet som minimum.
    Jämför minimummed det tredje elementet. Återigen, om det tredje elementet är mindre, så tilldela minimumdet tredje elementet annars gör ingenting. Processen pågår tills det sista elementet. Jämför minimum med de återstående elementen
  3. Efter varje iteration minimumplaceras det framför den osorterade listan. Byt den första med ett minimum
  4. För varje iteration börjar indexering från det första osorterade elementet. Steg 1 till 3 upprepas tills alla element är placerade i rätt position. Den första iteration Den andra iteration Den tredje iteration Den fjärde iteration

Urvals sorteringsalgoritm

 selectionSort (array, size) repeat (storlek - 1) gånger ställer in det första osorterade elementet som minimum för vart och ett av de osorterade elementen om elementet <currentMinimum set element som nytt minimum swap minimum med första osorterade positionens slutval

Python, Java och C / C ++ exempel

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

Komplexitet

Cykel Antal jämförelser
1: a (n-1)
2: a (n-2)
3: e (n-3)
… …
sista 1

Antal jämförelser: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2nästan lika med .n2

Komplexitet =O(n2)

Vi kan också analysera komplexiteten genom att helt enkelt observera antalet slingor. Det finns två slingor så komplexiteten är .n*n = n2

Tidskomplexitet:

  • Värstfallskomplexitet: Om vi ​​vill sortera i stigande ordning och matrisen är i fallande ordning inträffar det värsta fallet.O(n2)
  • Bästa fallskomplexitet: Det inträffar när arrayen redan är sorteradO(n2)
  • Genomsnittlig fallkomplexitet: Det inträffar när elementen i matrisen är i rörlig ordning (varken stigande eller fallande).O(n2)

Tidskomplexiteten för urvalssorten är i alla fall densamma. I varje steg måste du hitta minimielementet och placera det på rätt plats. Minimielementet är inte känt förrän slutet av matrisen inte nås.

Rymdkomplexitet:

Rymdkomplexitet O(1)beror på att en extra variabel tempanvänds.

Val Sortera applikationer

Urvalssorteringen används när:

  • en liten lista ska sorteras
  • kostnaden för att byta spelar ingen roll
  • kontroll av alla element är obligatorisk
  • kostnaden för att skriva till ett minne spelar roll som i flashminnet (antalet skrivningar / byten är O(n)jämfört med bubblansortering)O(n2)

Intressanta artiklar...