Selection sort är en enkel sorteringsalgoritm. Denna sorteringsalgoritm är en jämförelsebaserad algoritm på plats där listan är uppdelad i två delar, den sorterade delen i vänster ände och den osorterade delen i höger ände. Ursprungligen är den sorterade delen Tom och den osorterade delen är hela listan.
det minsta elementet väljs från den osorterade matrisen och byts ut med det vänstra elementet, och det elementet blir en del av den sorterade matrisen. Denna process fortsätter att flytta osorterad matrisgräns med ett element till höger.
denna algoritm är inte lämplig för stora datamängder eftersom dess genomsnittliga och värsta fall komplexitet är av 0B(N2), där n är antalet objekt.
Hur Selection Sort Fungerar?
Tänk på följande avbildade array som ett exempel.
för den första positionen i den sorterade listan skannas hela listan i följd. Den första positionen där 14 lagras för närvarande söker vi i hela listan och upptäcker att 10 är det lägsta värdet.
så vi ersätter 14 med 10. Efter en iteration 10, som råkar vara minimivärdet i listan, visas i den första positionen i den sorterade listan.
för den andra positionen, där 33 är bosatt, börjar vi skanna resten av listan på ett linjärt sätt.
vi finner att 14 är det näst lägsta värdet i listan och det ska visas på andra plats. Vi byter dessa värden.
efter två iterationer placeras två minst värden i början på ett sorterat sätt.
samma process tillämpas på resten av objekten i matrisen.
Följande är en bildbild av hela sorteringsprocessen −
låt oss nu lära oss några programmeringsaspekter av selection sort.
algoritm
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted
pseudokod
procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list < list then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list and list end if end forend procedure
för att veta om val Sortera implementering i C-programmeringsspråk, klicka här.