Valg Sorter algoritme

I denne vejledning lærer du, hvordan valgsortering fungerer. Du finder også arbejdseksempler på valgsortering i C, C ++, Java og Python.

Selektionssortering er en algoritme, der vælger det mindste element fra en usorteret liste i hver iteration og placerer elementet i begyndelsen af ​​den usorterede liste.

Hvordan fungerer sortering?

  1. Indstil det første element som minimum. Vælg det første element som minimum
  2. Sammenlign minimummed det andet element. Hvis det andet element er mindre end minimum, tildel det andet element som minimum.
    Sammenlign minimummed det tredje element. Igen, hvis det tredje element er mindre, så tildel minimumtil det tredje element ellers gør ingenting. Processen fortsætter indtil det sidste element. Sammenlign minimum med de resterende elementer
  3. Efter hver iteration minimumplaceres forrest på den usorterede liste. Skift den første med minimum
  4. For hver iteration starter indeksering fra det første usorterede element. Trin 1 til 3 gentages, indtil alle elementerne er placeret i deres korrekte positioner. Den første iteration Den anden iteration Den tredje iteration Den fjerde iteration

Valg Sorter algoritme

 selectionSort (array, størrelse) gentag (størrelse - 1) gange indstil det første usorterede element som minimum for hvert af de usorterede elementer, hvis elementet <nuværendeMinimum indstillet element som nyt minimums swap-minimum med det første usorterede placeringsendevalgSort

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

Cyklus Antal sammenligninger
1. (n-1)
2. plads (n-2)
3. (n-3)
… …
sidst 1

Antal sammenligninger: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2svarer næsten til .n2

Kompleksitet =O(n2)

Vi kan også analysere kompleksiteten ved blot at observere antallet af sløjfer. Der er 2 sløjfer, så kompleksiteten er .n*n = n2

Tidskompleksiteter:

  • Worst Case-kompleksitet: Hvis vi vil sortere i stigende rækkefølge, og arrayet er i faldende rækkefølge, forekommer det værste tilfælde.O(n2)
  • Bedste kompleksitet: Det sker, når arrayet allerede er sorteretO(n2)
  • Gennemsnitlig sagskompleksitet: Det sker, når elementerne i arrayet er i sammenblandet rækkefølge (hverken stigende eller faldende).O(n2)

Valgssorteringens tidskompleksitet er den samme i alle tilfælde. Ved hvert trin skal du finde minimumselementet og placere det på det rigtige sted. Minimumselementet er ikke kendt, før slutningen af ​​arrayet ikke er nået.

Rumkompleksitet:

Rumkompleksitet O(1)skyldes, at der bruges en ekstra variabel temp.

Valg Sorter applikationer

Valgssorteringen bruges, når:

  • en lille liste skal sorteres
  • omkostningerne ved at bytte betyder ikke noget
  • kontrol af alle elementer er obligatorisk
  • omkostningerne ved at skrive til en hukommelse betyder noget som i flash-hukommelse (antallet af skrivninger / swaps er O(n)sammenlignet med en slags boble)O(n2)

Interessante artikler...