Ebben az oktatóanyagban megtudhatja, hogyan működik a kiválasztás rendezése. Ezenkívül a C, C ++, a Java és a Python nyelvekben is talál példákat a kiválasztás rendezésére.
A Selection sort egy olyan algoritmus, amely minden iterációban kiválasztja a legkisebb elemet egy rendezetlen listából, és az elemet a nem rendezett lista elejére helyezi.
Hogyan működik a Selection Sort?
- Az első elemet állítsa be
minimum.
Válassza az első elemet minimumként - Hasonlítsa
minimumössze a második elemmel. Ha a második elem kisebbminimum, akkor a második elemet rendelje hozzáminimum.
Hasonlítsaminimumössze a harmadik elemmel. Ismételten, ha a harmadik elem kisebb, akkor rendeljeminimumhozzá a harmadik elemhez, különben ne tegyen semmit. A folyamat az utolsó elemig tart.
Hasonlítsa össze a minimumot a többi elemmel - Minden iteráció
minimumután a nem rendezett lista elé kerül.
Cserélje az elsőt a minimummal - Minden iteráció esetén az indexelés az első rendezetlen elemtől indul. Az 1–3. Lépéseket addig ismételjük, amíg az összes elem a megfelelő helyzetbe nem kerül.
Az első iteráció 
A második iteráció 
A harmadik iteráció 
A negyedik iteráció
Kiválasztás rendezési algoritmus
selectSort (tömb, méret) ismétlés (méret - 1) alkalommal állítsa be az első rendezetlen elemet a minimumként a rendezetlen elemek mindegyikéhez, ha az elem <currentMinimum set elem új minimális swap minimumként az első rendezetlen pozíció végének kiválasztásával
Példák Python, Java és C / C ++
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); )
Bonyolultság
| Ciklus | Összehasonlítás száma |
|---|---|
| 1 | (n-1) |
| 2. | (n-2) |
| 3 | (n-3) |
| … | … |
| utolsó | 1 |
Az összehasonlítások száma: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2majdnem megegyezik .n2
Komplexitás =O(n2)
Ezenkívül elemezhetjük a bonyolultságot a hurkok számának egyszerű megfigyelésével. 2 hurok van, tehát a bonyolultság .n*n = n2
Időkomplexumok:
- Legrosszabb eset komplexitás: Ha növekvő sorrendben akarunk rendezni, és a tömb csökkenő sorrendben van, akkor a legrosszabb eset következik be.
O(n2) - Legjobb eset komplexitás: Akkor fordul elő, amikor a tömb már rendezve van
O(n2) - Átlagos esetbonyolultság: Akkor fordul elő, amikor a tömb elemei összetévesztett sorrendben vannak (sem emelkedő, sem csökkenő).
O(n2)
A kiválasztási sorrend időbeli összetettsége minden esetben azonos. Minden lépésnél meg kell találnia a minimális elemet, és a megfelelő helyre kell tennie. A minimális elem addig nem ismert, amíg a tömb végét el nem érik.
Tér összetettsége:
A tér összetettsége O(1)azért van, mert egy extra változót temphasználnak.
Alkalmazások rendezése
A kiválasztási sorrend akkor használható, ha:
- egy kis listát kell rendezni
- a csere költsége nem számít
- az összes elem ellenőrzése kötelező
- A memóriába történő írás költsége számít, mint például a flash memóriában (az írások / cserék száma
O(n)összehasonlítva a buborékok rendezésével)O(n2)
