Αλγόριθμος Ταξινόμησης Εισαγωγής με C, C++, Java, Python Παραδείγματα

Τι είναι η ταξινόμηση εισαγωγής;

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

Κάθε στοιχείο εισάγεται διαδοχικά σε μια ήδη ταξινομημένη λίστα. Το μέγεθος της ήδη ταξινομημένης λίστας αρχικά είναι ένα. Ο αλγόριθμος ταξινόμησης με εισαγωγή διασφαλίζει ότι τα πρώτα k στοιχεία ταξινομούνται μετά την k-οστή επανάληψη του εξωτερικού βρόχου.

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

Χαρακτηριστικά Αλγόριθμου Ταξινόμησης Εισαγωγής

Ο αλγόριθμος για την ταξινόμηση με εισαγωγή έχει τα ακόλουθα σημαντικά χαρακτηριστικά που εξηγούν τη συμπεριφορά του σε πραγματικά φόρτα εργασίας:

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

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

Πώς γίνεται η εισαγωγή Operaεργασία;

Στον αλγόριθμο ταξινόμησης με εισαγωγή, η λειτουργία εισαγωγής χρησιμοποιείται για την ταξινόμηση μη ταξινομημένων στοιχείων. Βοηθά στην εισαγωγή ενός νέου στοιχείου σε μια ήδη ταξινομημένη λίστα, διατηρώντας παράλληλα την υπάρχουσα σειρά της ταξινομημένης περιοχής.

Ψευδοκώδικας της λειτουργίας εισαγωγής:

Σκεφτείτε μια λίστα Α με Ν στοιχεία.

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

Στο παραπάνω παράδειγμα, ένα νέο στοιχείο 6 εισάγεται σε μια ήδη ταξινομημένη λίστα. Ακολουθούν τα ακόλουθα βήματα: tracτον εσωτερικό βρόχο καθώς το νέο στοιχείο μεταναστεύει αριστερά προς τη σωστή του θέση.

Βήμα 1) Σε σύγκριση με το αριστερό παρακείμενο στοιχείο του A[5], 9 > 6, ανταλλάσσουμε τη θέση του 9 και του 6. Τώρα το στοιχείο 6 μετακινείται στο A[4].

Βήμα 2) Τώρα, συγκρίνουμε τα A[4] και A[3], και βρίσκουμε ότι A[3] > A[4], οπότε αλλάζουμε ξανά τη θέση των 6 και 8.

Βήμα 3) Τώρα συγκρίνετε τα A[3] και A[2]. Ως A[2] > A[3], εναλλάσσουμε τη θέση των 7 και 6.

Βήμα 4) Συγκρίνουμε τα A[1] και A[2]. Καθώς A[1] < A[2], το αριστερό γειτονικό στοιχείο δεν είναι πλέον μεγαλύτερο. Συμπεραίνουμε ότι το 6 έχει εισαχθεί σωστά και σταματάμε τον εσωτερικό βρόχο εδώ.

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

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

Το παραπάνω σχήμα δείχνει τη λειτουργία της Ταξινόμησης με Εισαγωγή σε μια δομή δεδομένων. Αρχικά, μόνο ένα στοιχείο βρίσκεται στην ταξινομημένη υπολίστα, δηλαδή, 4. Μετά την εισαγωγή του A[1], δηλαδή, 3, το μέγεθος της ταξινομημένης υπολίστας αυξάνεται σε 2 και ο αλγόριθμος συνεχίζει αυτό το μοτίβο μέχρι να τοποθετηθούν όλα τα στοιχεία.

Με την εννοιολογική ροή σε ισχύ, οι ακόλουθες ενότητες παρουσιάζουν συγκεκριμένες υλοποιήσεις σε C++, C, και Python ώστε να μπορείτε να συγκρίνετε δομές βρόχων σε όλες τις γλώσσες.

C++ Πρόγραμμα για ταξινόμηση εισαγωγής

The C++ Η παρακάτω υλοποίηση χρησιμοποιεί δύο ένθετους βρόχους: ο εξωτερικός βρόχος επιλέγει το επόμενο μη ταξινομημένο στοιχείο και ο εσωτερικός βρόχος το μετατοπίζει προς τα αριστερά μέχρι να βρεθεί η σωστή θέση.

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

Παραγωγή:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code για ταξινόμηση με εισαγωγή

Η ίδια λογική μεταφράζεται απευθείας στο C. Το πρότυπο printf Οι κλήσεις αντικαθιστούν την έξοδο ροής, αλλά το μοτίβο εναλλαγής μέσα στον εσωτερικό βρόχο είναι πανομοιότυπο με το C++ εκδοχή.

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Παραγωγή:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Πρόγραμμα για ταξινόμηση εισαγωγής

Python υποστηρίζει ανταλλαγή πλειάδωνping σε μία μόνο έκφραση, έτσι ο εσωτερικός βρόχος είναι πιο συμπαγής από το C και C++ αντίστοιχα διατηρώντας παράλληλα την ίδια αλγοριθμική συμπεριφορά.

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Παραγωγή:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Ιδιότητες της Ταξινόμησης Εισαγωγής

Ακολουθούν σημαντικές ιδιότητες της Εισαγωγικής Ταξινόμησης που σας βοηθούν να αποφασίσετε πότε είναι το σωστό εργαλείο:

• Συνδεδεμένοι: Η Ταξινόμηση με Εισαγωγή μπορεί να ταξινομήσει στοιχεία καθώς τα λαμβάνει. Εάν έχουμε ήδη ταξινομήσει μια λίστα στοιχείων και έχουμε προσθέσει περισσότερα στοιχεία στη λίστα, τότε δεν χρειάζεται να εκτελέσουμε ξανά ολόκληρη τη διαδικασία ταξινόμησης. Αντίθετα, επαναλαμβάνουμε μόνο τα στοιχεία που προστέθηκαν πρόσφατα.
• Στη θέση: Η πολυπλοκότητα χώρου του αλγορίθμου ταξινόμησης με εισαγωγή είναι σταθερή και δεν απαιτεί επιπλέον χώρο. Αυτός ο αλγόριθμος ταξινομεί τα στοιχεία στη θέση τους.
• Σταθερός: Στην Ταξινόμηση με Εισαγωγή, δεν ανταλλάσσουμε στοιχεία εάν οι τιμές τους είναι ίσες. Για παράδειγμα, εάν δύο στοιχεία, x και y, είναι ίσα και το x εμφανίζεται πριν από το y στη μη ταξινομημένη λίστα, τότε στη ταξινομημένη λίστα, το x θα εξακολουθεί να εμφανίζεται πριν από το y. Αυτό καθιστά την Ταξινόμηση με Εισαγωγή σταθερή.
• Προσαρμοστικό: A αλγόριθμος ταξινόμησης είναι προσαρμοστική αν χρειάζεται λιγότερος χρόνος όταν τα στοιχεία εισόδου ή ένα υποσύνολο στοιχείων είναι ήδη ταξινομημένα. Όπως συζητήσαμε παραπάνω, ο καλύτερος χρόνος εκτέλεσης της Ταξινόμησης με Εισαγωγή είναι O(N) και ο χειρότερος χρόνος εκτέλεσης είναι O(N^2). Η Ταξινόμηση με Εισαγωγή είναι ένας από τους προσαρμοστικούς αλγόριθμους ταξινόμησης.

Πολυπλοκότητα Ταξινόμησης Εισαγωγής

Η παρακάτω συζήτηση για την πολυπλοκότητα καλύπτει τόσο τη χρήση μνήμης όσο και τον χρόνο εκτέλεσης, ώστε να μπορείτε να τοποθετήσετε την Ταξινόμηση με Εισαγωγή σε σχέση με εναλλακτικές λύσεις όπως Bubble Ταξινόμηση και Γρήγορη ταξινόμηση.

Διαστημική πολυπλοκότητα

Η ταξινόμηση με εισαγωγή δεν απαιτεί επιπλέον χώρο για την ταξινόμηση των στοιχείων. Η πολυπλοκότητα του χώρου είναι σταθερή, δηλαδή O(1), επειδή χρησιμοποιούνται μόνο λίγες προσωρινές μεταβλητές ανεξάρτητα από το μέγεθος εισόδου.

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

Επειδή η Ταξινόμηση με Εισαγωγή επαναλαμβάνει ένα στοιχείο κάθε φορά, απαιτεί N-1 περάσματα για την ταξινόμηση N στοιχείων. Για κάθε πέρασμα, μπορεί να κάνει μηδενικές εναλλαγές εάν τα στοιχεία είναι ήδη ταξινομημένα ή μπορεί να χρειαστεί πολλές εναλλαγές εάν τα στοιχεία είναι ταξινομημένα σε φθίνουσα σειρά.

• Για το πάσο 1, οι ελάχιστες απαιτούμενες ανταλλαγές είναι μηδέν και οι μέγιστες απαιτούμενες ανταλλαγές είναι 1.
• Για το πάσο 2, οι ελάχιστες απαιτούμενες ανταλλαγές είναι μηδέν και οι μέγιστες απαιτούμενες ανταλλαγές είναι 2.
• Για το πέρασμα N, η ελάχιστη απαιτούμενη ανταλλαγή είναι μηδέν και οι μέγιστες απαιτούμενες ανταλλαγές είναι N.
• Η ελάχιστη εναλλαγή είναι μηδέν, επομένως η καλύτερη χρονική πολυπλοκότητα είναι O(N) για επανάληψη Ν περασμάτων.
• Οι συνολικές μέγιστες ανταλλαγές είναι (1+2+3+4+…+N), δηλαδή N(N+1)/2, επομένως η χειρότερη χρονική πολυπλοκότητα είναι O(N^2).

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

• Η χειρότερη πολυπλοκότητα της υπόθεσης: O(n^2): Η ταξινόμηση ενός πίνακα σε φθίνουσα σειρά όταν απαιτείται να είναι αύξουσα είναι το χειρότερο σενάριο.
• Καλυτερα Case Complexity: O(n): Η καλύτερη περίπτωση συμβαίνει όταν ο πίνακας είναι ήδη ταξινομημένος. Ο εξωτερικός βρόχος εκτελείται n φορές, ενώ ο εσωτερικός βρόχος δεν εκτελείται καθόλου. Υπάρχουν μόνο n συγκρίσεις, επομένως η πολυπλοκότητα είναι γραμμική.
• Μέση πολυπλοκότητα υπόθεσης: O(n^2): Αυτό συμβαίνει όταν τα στοιχεία του πίνακα εμφανίζονται σε μια μπερδεμένη σειρά που δεν είναι ούτε αύξουσα ούτε φθίνουσα.

Συχνές Ερωτήσεις