Utvalg Sorteringsalgoritme

I denne veiledningen lærer du hvordan utvalgssortering fungerer. Du finner også arbeidseksempler på utvalgssortering i C, C ++, Java og Python.

Valgsortering er en algoritme som velger det minste elementet fra en usortert liste i hver iterasjon og plasserer elementet i begynnelsen av den usorterte listen.

Hvordan fungerer valgssortering?

  1. Sett det første elementet som minimum. Velg det første elementet som minimum
  2. Sammenlign minimummed det andre elementet. Hvis det andre elementet er mindre enn minimum, tilordner du det andre elementet som minimum.
    Sammenlign minimummed det tredje elementet. Igjen, hvis det tredje elementet er mindre, så tilordne minimumdet tredje elementet ellers gjør ingenting. Prosessen fortsetter til det siste elementet. Sammenlign minimum med gjenværende elementer
  3. Etter hver iterasjon, minimumer plassert foran den usorterte listen. Bytt den første med minimum
  4. For hver iterasjon starter indeksering fra det første usorterte elementet. Trinn 1 til 3 gjentas til alle elementene er plassert i riktig posisjon. Den første iterasjonen Den andre iterasjonen Den tredje iterasjonen Den fjerde iterasjonen

Utvalg Sorteringsalgoritme

 selectionSort (array, size) repeat (size - 1) times set the first usorted element as the minimum for each of the usorted elements if element <currentMinimum set element as new minimum swap minimum with first usorted position end selectionSort

Python, Java og C / C ++ eksempler

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

Kompleksitet

Syklus Antall sammenligninger
Første (n-1)
2. plass (n-2)
3. (n-3)
… …
siste 1

Antall sammenligninger: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2nesten lik .n2

Kompleksitet =O(n2)

Vi kan også analysere kompleksiteten ved å bare observere antall løkker. Det er to sløyfer så kompleksiteten er .n*n = n2

Tidskompleksiteter:

  • Verste sakskompleksitet: Hvis vi vil sortere i stigende rekkefølge og matrisen er i synkende rekkefølge, oppstår det verste tilfellet.O(n2)
  • Best case-kompleksitet: Det oppstår når matrisen allerede er sortertO(n2)
  • Gjennomsnittlig sakskompleksitet: Det oppstår når elementene i matrisen er i rotet rekkefølge (verken stigende eller synkende).O(n2)

Tids kompleksiteten til utvalget er i alle tilfeller den samme. Ved hvert trinn må du finne minimumselementet og sette det på rett sted. Minimumselementet er ikke kjent før slutten av matrisen ikke er nådd.

Romkompleksitet:

Romkompleksitet er O(1)fordi det brukes en ekstra variabel temp.

Valg Sorter applikasjoner

Valgsorteringen brukes når:

  • en liten liste skal sorteres
  • kostnadene ved å bytte spiller ingen rolle
  • kontroll av alle elementene er obligatorisk
  • kostnadene ved å skrive til et minne betyr noe som i flashminnet (antall skriver / bytter er O(n)sammenlignet med en slags boble)O(n2)

Interessante artikler...