Ταξινόμηση εισαγωγής: Αλγόριθμος με C, C++, Java, Python Παραδείγματα
Σάρα Τσεν
Τι είναι η ταξινόμηση εισαγωγής;
Η ταξινόμηση εισαγωγής είναι ένας από τους αλγόριθμους σύγκρισης ταξινόμησης που χρησιμοποιούνται για την ταξινόμηση στοιχείων επαναλαμβάνοντας ένα στοιχείο κάθε φορά και τοποθετώντας το στοιχείο στη σωστή του θέση.
Κάθε στοιχείο εισάγεται διαδοχικά σε μια ήδη ταξινομημένη λίστα. Το μέγεθος της ήδη ταξινομημένης λίστας είναι αρχικά ένα. Ο αλγόριθμος ταξινόμησης εισαγωγής διασφαλίζει ότι τα πρώτα k στοιχεία ταξινομούνται μετά την kth επανάληψη.
Χαρακτηριστικά Αλγόριθμου Ταξινόμησης Εισαγωγής
Ο αλγόριθμος για την ταξινόμηση εισαγωγής έχει τα ακόλουθα σημαντικά χαρακτηριστικά:
- Είναι μια σταθερή τεχνική ταξινόμησης, επομένως δεν αλλάζει τη σχετική σειρά ίσων στοιχείων.
- Είναι αποτελεσματικό για μικρότερα σύνολα δεδομένων, αλλά δεν είναι αποτελεσματικό για μεγαλύτερες λίστες.
- Το Insertion Sort είναι προσαρμοστικό, το οποίο μειώνει τον συνολικό αριθμό των βημάτων του εάν είναι μερική ταξινόμηση. Παράταξη παρέχεται ως είσοδος για να είναι αποτελεσματική.
Πώς γίνεται η εισαγωγή Operaεργασία;
Στον αλγόριθμο Insertion Sort, η λειτουργία εισαγωγής χρησιμοποιείται για την ταξινόμηση μη ταξινομημένων στοιχείων. Βοηθά να εισαγάγετε ένα νέο στοιχείο σε μια ήδη ταξινομημένη λίστα.
Ψευδοκώδικας λειτουργίας εισαγωγής:
Σκεφτείτε μια λίστα Α με Ν στοιχεία.
A[N-1] is the element to be inserted in the 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 πρόκειται να εισαχθεί σε μια ήδη ταξινομημένη λίστα.
Βήμα 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) Συγκρίνουμε Α[1] και Α[2], και ως Α[1] < Α[2], δηλαδή, το αριστερό διπλανό στοιχείο δεν είναι πλέον μεγαλύτερο. Τώρα συμπεραίνουμε ότι το 6 έχει εισαχθεί σωστά και σταματάμε τον αλγόριθμο εδώ.
Πώς λειτουργεί η ταξινόμηση εισαγωγής
Η λειτουργία εισαγωγής που συζητήθηκε παραπάνω είναι η ραχοκοκαλιά της ταξινόμησης εισαγωγής. Η διαδικασία εισαγωγής εκτελείται σε κάθε στοιχείο και στο τέλος παίρνουμε την ταξινομημένη λίστα.
Το παραπάνω παράδειγμα σχήμα δείχνει τη λειτουργία της ταξινόμησης εισαγωγής στη δομή δεδομένων. Αρχικά, υπάρχει μόνο ένα στοιχείο στην ταξινομημένη υπολίστα, π.χ., 4. Μετά την εισαγωγή A[1], δηλαδή, 3, το μέγεθος της ταξινομημένης υπολίστας αυξάνεται σε 2.
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 για Ταξινόμηση Εισαγωγής
#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 Πρόγραμμα για ταξινόμηση εισαγωγής
#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). Η ταξινόμηση εισαγωγής είναι ένας από τους προσαρμοστικούς αλγόριθμους ταξινόμησης.
Πολυπλοκότητα Ταξινόμησης Εισαγωγής
Διαστημική πολυπλοκότητα
Η ταξινόμηση εισαγωγής δεν απαιτεί επιπλέον χώρο για την ταξινόμηση των στοιχείων, η πολυπλοκότητα του χώρου είναι σταθερή, π.χ. O(1).
Χρόνος πολυπλοκότητας
Καθώς η ταξινόμηση εισαγωγής επαναλαμβάνει κάθε στοιχείο ταυτόχρονα, απαιτεί N-1 περάσματα για την ταξινόμηση N στοιχείων. Για κάθε πέρασμα, μπορεί να κάνει μηδενικές εναλλαγές εάν τα στοιχεία είναι ήδη ταξινομημένα ή να εναλλάσσονται εάν τα στοιχεία είναι διατεταγμένα με φθίνουσα σειρά.
- Για το πάσο 1, οι ελάχιστες απαιτούμενες ανταλλαγές είναι μηδέν και οι μέγιστες απαιτούμενες ανταλλαγές είναι 1.
- Για το πάσο 2, οι ελάχιστες απαιτούμενες ανταλλαγές είναι μηδέν και οι μέγιστες απαιτούμενες ανταλλαγές είναι 2.
- Για το πέρασμα N, η ελάχιστη απαιτούμενη ανταλλαγή είναι μηδέν και οι μέγιστες απαιτούμενες ανταλλαγές είναι N.
- Η ελάχιστη εναλλαγή είναι μηδέν, επομένως η καλύτερη χρονική πολυπλοκότητα είναι O(N) για επανάληψη Ν περασμάτων.
- Οι συνολικές μέγιστες ανταλλαγές είναι (1+2+3+4+..+N) i. N(N+1)/2, η χειρότερη χρονική πολυπλοκότητα είναι O(N^2).
Ακολουθεί η σημαντική χρονική πολυπλοκότητα της ταξινόμησης εισαγωγής:
- Η χειρότερη πολυπλοκότητα της υπόθεσης: O(n2): Η ταξινόμηση ενός πίνακα σε φθίνουσα σειρά όταν είναι σε αύξουσα σειρά είναι το χειρότερο σενάριο.
- Καλυτερα Case Complexity: O(n): Καλυτερα Case Complexity εμφανίζεται όταν ο πίνακας είναι ήδη ταξινομημένος, ο εξωτερικός βρόχος εκτελείται για n φορές ενώ ο εσωτερικός βρόχος δεν εκτελείται καθόλου. Υπάρχει μόνο n αριθμός συγκρίσεων. Άρα, σε αυτή την περίπτωση, η πολυπλοκότητα είναι γραμμική.
- Μέση πολυπλοκότητα υπόθεσης: O(n2): Συμβαίνει όταν τα στοιχεία ενός πίνακα εμφανίζονται με μπερδεμένη σειρά, η οποία δεν είναι ούτε αύξουσα ούτε φθίνουσα.
Περίληψη
- Η ταξινόμηση εισαγωγής είναι μια μέθοδος αλγορίθμου ταξινόμησης που βασίζεται στη σύγκριση.
- Είναι μια σταθερή τεχνική ταξινόμησης, επομένως δεν αλλάζει τη σχετική σειρά ίσων στοιχείων.
- Σε κάθε στοιχείο, η λειτουργία εισαγωγής χρησιμοποιείται για την εισαγωγή του στοιχείου στην ταξινομημένη υπολίστα.
- Η ταξινόμηση εισαγωγής είναι ένας επιτόπιος αλγόριθμος ταξινόμησης.
- Η χειρότερη και μέση χρονική πολυπλοκότητα της ταξινόμησης εισαγωγής είναι η τετραγωνική, δηλ. O(N^2).
- Η ταξινόμηση εισαγωγής δεν απαιτεί βοηθητικό χώρο.
