Αλγόριθμος Ταξινόμησης Εισαγωγής

Πίνακας περιεχομένων

Πώς λειτουργεί η ταξινόμηση εισαγωγής;
Αλγόριθμος ταξινόμησης εισαγωγής
Παραδείγματα Python, Java και C / C ++
Περίπλοκο
Εφαρμογές ταξινόμησης εισαγωγής

Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί η ταξινόμηση εισαγωγής. Επίσης, θα βρείτε λειτουργικά παραδείγματα τύπου εισαγωγής σε C, C ++, Java και Python.

Η ταξινόμηση εισαγωγής λειτουργεί παρόμοια με την ταξινόμηση καρτών στο χέρι μας σε ένα παιχνίδι καρτών.

Υποθέτουμε ότι η πρώτη κάρτα έχει ήδη ταξινομηθεί, επιλέγουμε μια κάρτα χωρίς ταξινόμηση. Εάν η μη ταξινομημένη κάρτα είναι μεγαλύτερη από την κάρτα στο χέρι, τοποθετείται στα δεξιά διαφορετικά, προς τα αριστερά. Με τον ίδιο τρόπο, άλλες κάρτες που δεν έχουν ταξινομηθεί λαμβάνονται και τοποθετούνται στη σωστή τους θέση.

Μια παρόμοια προσέγγιση χρησιμοποιείται από το είδος εισαγωγής.

Το είδος εισαγωγής είναι ένας αλγόριθμος ταξινόμησης που τοποθετεί ένα μη ταξινομημένο στοιχείο στην κατάλληλη θέση του σε κάθε επανάληψη.

Πώς λειτουργεί η ταξινόμηση εισαγωγής;

Ας υποθέσουμε ότι πρέπει να ταξινομήσουμε τον ακόλουθο πίνακα.

Αρχικός πίνακας

Το πρώτο στοιχείο στον πίνακα θεωρείται ότι έχει ταξινομηθεί. Πάρτε το δεύτερο στοιχείο και αποθηκεύστε το ξεχωριστά key.
Συγκρίνετε keyμε το πρώτο στοιχείο. Εάν το πρώτο στοιχείο είναι μεγαλύτερο από key, τότε το κλειδί τοποθετείται μπροστά από το πρώτο στοιχείο. Εάν το πρώτο στοιχείο είναι μεγαλύτερο από το κλειδί, τότε το κλειδί τοποθετείται μπροστά από το πρώτο στοιχείο.
Τώρα, τα πρώτα δύο στοιχεία ταξινομούνται.
Πάρτε το τρίτο στοιχείο και συγκρίνετέ το με τα στοιχεία στα αριστερά του. Τοποθετήθηκε ακριβώς πίσω από το στοιχείο μικρότερο από αυτό. Εάν δεν υπάρχει στοιχείο μικρότερο από αυτό, τοποθετήστε το στην αρχή του πίνακα. Θέση 1 στην αρχή
Ομοίως, τοποθετήστε κάθε μη ταξινομημένο στοιχείο στη σωστή του θέση. Θέση 4 πίσω από 1 Θέση 3 πίσω από 1 και η σειρά ταξινομείται

Αλγόριθμος ταξινόμησης εισαγωγής

 insertionSort (array) επισημάνετε το πρώτο στοιχείο ως ταξινομημένο για κάθε στοιχείο που δεν έχει ταξινομηθεί X «εξαγάγετε» το στοιχείο X για j X μετακινήστε το ταξινομημένο στοιχείο προς τα δεξιά κατά 1 βρόχο διακοπής και εισαγάγετε το X εδώ τέλος εισαγωγής Ταξινόμηση

Παραδείγματα Python, Java και C / C ++

Python Java C C ++

 # Insertion sort in Python def insertionSort(array): for step in range(1, len(array)): key = array(step) j = step - 1 # Compare key with each element on the left of it until an element smaller than it is found # For descending order, change keyarray(j). while j>= 0 and key < array(j): array(j + 1) = array(j) j = j - 1 # Place key at after the element just smaller than it. array(j + 1) = key data = (9, 5, 1, 4, 3) insertionSort(data) print('Sorted Array in Ascending Order:') print(data)

  // Insertion sort in Java import java.util.Arrays; class InsertionSort ( void insertionSort(int array()) ( int size = array.length; for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (j>= 0 && key < array(j)) ( array(j + 1) = array(j); --j; ) // Place key at after the element just smaller than it. array(j + 1) = key; ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 5, 1, 4, 3 ); InsertionSort is = new InsertionSort(); is.insertionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Insertion sort in C #include // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( printf("%d ", array(i)); ) printf(""); ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); printf("Sorted array in ascending order:"); printArray(data, size); )

 // Insertion sort in C++ #include using namespace std; // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void insertionSort(int array(), int size) ( for (int step = 1; step < size; step++) ( int key = array(step); int j = step - 1; // Compare key with each element on the left of it until an element smaller than // it is found. // For descending order, change keyarray(j). while (key = 0) ( array(j + 1) = array(j); --j; ) array(j + 1) = key; ) ) // Driver code int main() ( int data() = (9, 5, 1, 4, 3); int size = sizeof(data) / sizeof(data(0)); insertionSort(data, size); cout << "Sorted array in ascending order:"; printArray(data, size); )

Περίπλοκο

Χρόνος πολυπλοκότητας

Χειρότερη περίπλοκη περίπτωση: Ας υποθέσουμε ότι ένας πίνακας είναι σε αύξουσα σειρά και θέλετε να τον ταξινομήσετε σε φθίνουσα σειρά. Σε αυτήν την περίπτωση, εμφανίζεται χειρότερη περίπλοκη περίπτωση Κάθε στοιχείο πρέπει να συγκριθεί με κάθε ένα από τα άλλα στοιχεία, έτσι, για κάθε ένατο στοιχείο, γίνεται αριθμός συγκρίσεων. Έτσι, ο συνολικός αριθμός συγκρίσεων =O(n²)

(n-1)
n*(n-1) ~ n²
Βέλτιστη πολυπλοκότητα περιπτώσεων: O(n)
Όταν ο πίνακας έχει ήδη ταξινομηθεί, ο εξωτερικός βρόχος λειτουργεί για nαρκετές φορές ενώ ο εσωτερικός βρόχος δεν λειτουργεί καθόλου Υπάρχουν μόνο nσυγκρίσεις. Έτσι, η πολυπλοκότητα είναι γραμμική.
Μέση πολυπλοκότητα περίπτωσης: Εμφανίζεται όταν τα στοιχεία ενός πίνακα είναι σε ανάμικτη σειρά (ούτε αύξουσα ούτε φθίνουσα).O(n²)