Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί το είδος επιλογής. Επίσης, θα βρείτε λειτουργικά παραδείγματα επιλογής σε C, C ++, Java και Python.
Το είδος επιλογής είναι ένας αλγόριθμος που επιλέγει το μικρότερο στοιχείο από μια λίστα χωρίς ταξινόμηση σε κάθε επανάληψη και τοποθετεί αυτό το στοιχείο στην αρχή της λίστας χωρίς ταξινόμηση.
Πώς λειτουργεί η επιλογή ταξινόμησης;
- Ορίστε το πρώτο στοιχείο ως
minimum.
Επιλέξτε το πρώτο στοιχείο ως ελάχιστο - Συγκρίνετε
minimumμε το δεύτερο στοιχείο. Εάν το δεύτερο στοιχείο είναι μικρότερο απόminimum, αντιστοιχίστε το δεύτερο στοιχείο ωςminimum.
Συγκρίνετεminimumμε το τρίτο στοιχείο. Και πάλι, εάν το τρίτο στοιχείο είναι μικρότερο, τότε εκχωρήστεminimumστο τρίτο στοιχείο διαφορετικά μην κάνετε τίποτα. Η διαδικασία συνεχίζεται μέχρι το τελευταίο στοιχείο.
Συγκρίνετε το ελάχιστο με τα υπόλοιπα στοιχεία - Μετά από κάθε επανάληψη,
minimumτοποθετείται στο μπροστινό μέρος της λίστας χωρίς ταξινόμηση.
Ανταλλάξτε το πρώτο με ελάχιστο - Για κάθε επανάληψη, η ευρετηρίαση ξεκινά από το πρώτο μη ταξινομημένο στοιχείο. Τα βήματα 1 έως 3 επαναλαμβάνονται έως ότου όλα τα στοιχεία τοποθετηθούν στις σωστές θέσεις τους.
Η πρώτη επανάληψη 
Η δεύτερη επανάληψη 
Η τρίτη επανάληψη 
Η τέταρτη επανάληψη
Αλγόριθμος επιλογής ταξινόμησης
Επιλογή Ταξινόμηση (πίνακας, μέγεθος) επανάληψη (μέγεθος - 1) φορές ορίστε το πρώτο στοιχείο χωρίς ταξινόμηση ως το ελάχιστο για κάθε ένα από τα μη ταξινομημένα στοιχεία εάν το στοιχείο <τρέχον Ελάχιστο στοιχείο ρύθμισης ως νέο ελάχιστο ελάχιστο ανταλλαγής με την επιλογή τελικής θέσης
Παραδείγματα Python, Java και 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); )
Περίπλοκο
| Κύκλος | Αριθμός σύγκρισης |
|---|---|
| 1ος | (ν-1) |
| 2ος | (ν-2) |
| 3ος | (ν-3) |
| … | … |
| τελευταίος | 1 |
Αριθμός συγκρίσεων: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2σχεδόν ισούται με .n2
Πολυπλοκότητα =O(n2)
Επίσης, μπορούμε να αναλύσουμε την πολυπλοκότητα παρατηρώντας απλώς τον αριθμό των βρόχων. Υπάρχουν 2 βρόχοι, έτσι η πολυπλοκότητα είναι .n*n = n2
Χρόνος πολυπλοκότητας:
- Χειρότερη περίπλοκη περίπτωση : Εάν θέλουμε να ταξινομήσουμε με αύξουσα σειρά και ο πίνακας είναι σε φθίνουσα σειρά τότε, εμφανίζεται η χειρότερη περίπτωση.
O(n2) - Βέλτιστη πολυπλοκότητα περιπτώσεων: Εμφανίζεται όταν ο πίνακας έχει ήδη ταξινομηθεί
O(n2) - Μέση πολυπλοκότητα περίπτωσης: Εμφανίζεται όταν τα στοιχεία του πίνακα είναι σε ανάμικτη σειρά (ούτε αύξουσα ούτε φθίνουσα).
O(n2)
Η πολυπλοκότητα του χρόνου επιλογής είναι η ίδια σε όλες τις περιπτώσεις. Σε κάθε βήμα, πρέπει να βρείτε το ελάχιστο στοιχείο και να το τοποθετήσετε στη σωστή θέση. Το ελάχιστο στοιχείο δεν είναι γνωστό έως ότου δεν επιτευχθεί το τέλος του πίνακα.
Διαστημική πολυπλοκότητα:
Η πολυπλοκότητα του χώρου είναι O(1)επειδή χρησιμοποιείται μια επιπλέον μεταβλητή temp.
Εφαρμογές Ταξινόμησης Επιλογής
Το είδος επιλογής χρησιμοποιείται όταν:
- μια μικρή λίστα πρέπει να ταξινομηθεί
- το κόστος ανταλλαγής δεν έχει σημασία
- Ο έλεγχος όλων των στοιχείων είναι υποχρεωτικός
- Το κόστος της γραφής σε μια μνήμη έχει σημασία όπως στη μνήμη flash (ο αριθμός εγγραφών / ανταλλαγών είναι
O(n)σε σύγκριση με το είδος φυσαλίδων)O(n2)
