Selectie sorteeralgoritme

Inhoudsopgave

Hoe werkt selectiesortering?
Selectie sorteeralgoritme
Python, Java en C / C ++ voorbeelden
Complexiteit
Selectie Sorteerapplicaties

In deze tutorial leert u hoe selectiesortering werkt. Ook vindt u werkende voorbeelden van selectiesortering in C, C ++, Java en Python.

Selectie sorteren is een algoritme dat in elke iteratie het kleinste element uit een ongesorteerde lijst selecteert en dat element aan het begin van de ongesorteerde lijst plaatst.

Hoe werkt selectiesortering?

Stel het eerste element in als minimum. Selecteer minimaal het eerste element
Vergelijk minimummet het tweede element. Als het tweede element kleiner is dan minimum, wijs het tweede element dan toe als minimum.
Vergelijk minimummet het derde element. Nogmaals, als het derde element kleiner is, wijs minimumhet dan toe aan het derde element, anders doe je niets. Het proces gaat door tot het laatste element. Vergelijk minimum met de overige elementen
Na elke iteratie minimumwordt vooraan in de ongesorteerde lijst geplaatst. Verwissel de eerste met minimum
Voor elke iteratie begint het indexeren vanaf het eerste ongesorteerde element. Stap 1 t / m 3 worden herhaald totdat alle elementen op de juiste positie zijn geplaatst. De eerste iteratie De tweede iteratie De derde iteratie De vierde iteratie

Selectie sorteeralgoritme

 selectionSort (matrix, grootte) herhaal (grootte - 1) keer stel het eerste ongesorteerde element in als het minimum voor elk van de ongesorteerde elementen als element <huidig Minimum stel element in als nieuw minimum swap minimum met eerste ongesorteerde positie einde selectie

Python, Java en C / C ++ voorbeelden

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

Complexiteit

Fiets	Aantal vergelijkingen
1e	(n-1)
2e	(n-2)
3e	(n-3)
…	…
laatste	1

Aantal vergelijkingen: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2bijna gelijk aan .n²

Complexiteit =O(n²)

We kunnen ook de complexiteit analyseren door simpelweg het aantal lussen te observeren. Er zijn 2 loops, dus de complexiteit is .n*n = n²

Tijdscomplexiteit:

Complexiteit in het ergste geval: Als we in oplopende volgorde willen sorteren en de array is in aflopende volgorde, dan doet zich het ergste geval voor.O(n²)
Best Case Complexity: dit treedt op wanneer de array al is gesorteerdO(n²)
Gemiddelde hoofdlettercomplexiteit: treedt op wanneer de elementen van de array in een door elkaar gegooide volgorde staan (noch oplopend noch aflopend).O(n²)

De tijdcomplexiteit van de selectiesortering is in alle gevallen hetzelfde. Bij elke stap moet je het minimale element vinden en het op de juiste plaats plaatsen. Het minimumelement is pas bekend als het einde van de array niet is bereikt.

Ruimtecomplexiteit:

Ruimtecomplexiteit komt O(1)doordat er een extra variabele tempwordt gebruikt.

Selectie Sorteerapplicaties

De selectie sortering wordt gebruikt wanneer:

een kleine lijst moet worden gesorteerd
kosten van ruilen doen er niet toe
controle van alle elementen is verplicht
de kosten van het schrijven naar een geheugen zijn van belang zoals in het flash-geheugen (het aantal schrijfbewerkingen / swaps is O(n)in vergelijking met het soort bellen)O(n²)