Ταξινόμηση με εισαγωγή

Καλύτερη, χειρότερη και μέση περίπτωση

Η καλύτερη περίπτωση εισαγωγής είναι ένας πίνακας ο οποίος είναι ήδη ταξινομημένος. Σε αυτήν την περίπτωση, η ταξινόμηση με εισαγωγή έχει ένα γραμμικό χρόνο εκτέλεσης (δηλαδή Θ(n)). Κατά τη διάρκεια κάθε επανάληψης, το πρώτο στοιχείο της εισόδου είναι το μόνο σε σύγκριση με το πιο δεξιό στοιχείο από το ταξινομημένο υποτμήμα του πίνακα.
Η απλούστερη χειρότερη περίπτωση εισόδου είναι ένας πίνακας ταξινομημένος με την αντίστροφη σειρά. Το σύνολο όλων περιπτώσεων χειρότερης εισόδου περιλαμβάνει όλους τους πίνακες των οποίων κάθε στοιχείο είναι το μικρότερο ή το δεύτερο μικρότερο από τα στοιχεία που βρίσκονται πριν από αυτό. Σε αυτές τις περιπτώσεις κάθε επανάληψη στον εσωτερικό βρόχο θα σαρώσει και θα μετακινήσει το σύνολο του ταξινομημένου υποτμήματος του πίνακα πριν εισάγει το επόμενο στοιχείο. Αυτό έχει σαν αποτέλεσμα η ταξινόμηση με εισαγωγή εκτελείται σε τετραγωνικό χρόνο (δηλαδή Ο(n²)).
Η μέση περίπτωση είναι, επίσης, η τετραγωνική, η οποία χρησιμοποιεί ταξινόμηση με εισαγωγή που είναι πρακτική για ταξινόμηση σε μεγάλους πίνακες. Ωστόσο, η ταξινόμηση με εισαγωγή είναι ένας από τους γρηγορότερους αλγορίθμους για ταξινόμηση πολύ μικρών πινάκων, ακόμα πιο γρήγορα και από ότι η γρήγορη ταξινόμηση (quicksort). Πράγματι, οι καλές εφαρμογές γρήγορης ταξινόμησης χρησιμοποιούν ταξινόμηση με εισαγωγή για πίνακες μικρότερους από ένα συγκεκριμένο όριο, ακόμα και όταν προκύπτει ως υποπρόβλημα. Το ακριβές όριο πρέπει να είναι προσδιορισμένο πειραματικά και να εξαρτάται από το μηχάμημα, αλλά είναι συνήθως γύρω στο δέκα.
Παράδειγμα:
Ο πίνακας που ακολουθεί δέιχνει τα βήματα για την ταξινόμηση της ακολουθίας { 3, 7, 4, 9, 5, 2, 6, 1 }. Σε κάθε βήμα, το στοιχείο που εξετάζεται είναι υπογραμμισμένο. Το στοιχείο που μετακινείται (ή παραμένει στη θέση του επειδή θεωρείται ακόμα μεγαλύτερος) στο προηγούμενο βήμα εμφανίζεται με έντονο χρώμα.
37495261
37495261
37495261
34795261
34795261
34579261
23457961
23456791
12345679

Σύγκριση με άλλους αλγορίθμους ταξινόμησης

Η ταξινόμηση με εισαγωγή είναι παρόμοια με την ταξινόμηση επιλογής(selection sort). Όπως στην ταξινόμηση επιλογής, αφού το k περάσει σε έναν πίνακα, τα πρώτα k στοιχεία του πίνακα είναι ταξινομημένα. Για την ταξινόμηση επιλογής, αυτά είναι τα k μικρότερα στοιχεία, ενώ για την ταξινόμηση με εισαγωγή είναι ότι και τα k πρώτα στοιχεία στον μη ταξινομημένο πίνακα. Το πλεονέκτημα της ταξινόμησης με εισαγωγή είναι ότι σαρώνει μόνο όσα στοιχεία είναι απαραίτητα για να καθορίσουν τη σωστή τοποθεσία των k συν το πρώτο στοιχείο, ενώ η ταξινόμηση επιλογής πρέπει να σαρώσει όλα τα εναπομείναντα στοιχεία για να βρει το ακριβές μικρότερο στοιχείο.
Οι υπολογισμοί δείχνουν ότι η ταξινόμηση με εισαγωγή συνήθως εκτελεί περίπου τις μισές συγκρίσεις σε σχέση με την ταξινόμηση επιλογής. Υποθέτοντας ότι η θέση του k συν το πρώτο στοιχείο είναι τυχαία, η ταξινόμηση με εισαγωγή θα απαιτήσει κατά μέσο όρο ολίσθηση των μισών από τα προηγούμενα k στοιχεία, ενώ η ταξινόμηση επιλογής απαιτεί πάντα σάρωση όλων των μη ταξινομημένων στοιχείων. Εάν ο πίνακας εισόδου είναι ταξινομημένος αντίστροφα, η ταξινόμηση με εισαγωγή εκτελεί τόσες συγκρίσεις όσες και η ταξινόμηση επιλογής. Εάν ο πίνακας εισαγωγής είναι ήδη ταξινομημένος, η ταξινόμηση επιλογής εκτελεί τόσες λίγες συγκρίσεις όσες n-1, καθιστώντας έτσι την ταξινόμηση με εισαγωγή πιο αποτελεσματική όταν τις δίνονται ταξινομημένοι ή «σχεδόν ταξινομημένοι» πίνακες.
Ενώ η ταξινόμηση με εισαγωγή τυπικά εκτελεί λιγότερες συγκρίσεις σε σχέση με την ταξινόμηση επιλογής, απαιτεί περισσότερες εγγραφές διότι ο εσωτερικός βρόχος μπορεί να χρειαστεί ολίσθηση μεγάλων τμημάτων του ταξινομημένου μέρους του πίνακα. Γενικά, η ταξινόμηση με εισαγωγή γράφει στον πίνακα σε χρόνο O(n²), ενώ αντίθετα η ταξινόμηση επιλογής γράφει σε χρόνο μόνο O(n). Για το λόγο αυτό και η ταξινόμηση επιλογής προτιμάται σε περιπτώσεις όπου η εγγραφή στη μνήμη είναι σημαντικά πιο δαπανηρή απ’ ότι η ανάγνωση όπως με το EEPROM ή τη flash μνήμη(flash memory).
Μερικοί αλγόριθμοι Διαίρει και βασίλευε (υπολογιστές) όπως η γρήγορη ταξινόμηση(quicksort) and ταξινόμηση με συγχώνευση ταξινομούν διαιρώντας αναδρομικά τη λίστα σε μικρότερες υπό-λίστες, οι οποίες μετά ταξινομούνται. Μια χρήσιμη βελτίωση στην πράξη για αυτούς τους αλγορίθμους είναι η χρήση ταξινόμησης με εισαγωγή για την ταξινόμηση μικρών υπό-λιστών, όπου η ταξινόμηση με εισαγωγή υπερτερεί όλων αυτών των πιο περίπλοκων αλγορίθμων. Το μέγεθος της λίστας για το οποίο η ταξινόμηση με εισαγωγή πλεονεκτεί ποικίλλει ανάλογα με το περιβάλλον και την υλοποίηση, αλλά τυπικά είναι για οκτώ μέχρι είκοσι στοιχεία.

Παραλλαγές

O D.L. Shell έκανε σημαντικές βελτιώσεις στον αλγόριθμο• η τροποποιημένη εκδοχή ονομάζεται ταξινόμηση με κέλυφος(shell sort). Ο αλγόριθμος ταξινόμησης συγκρίνει στοιχεία που διαχωρίζονται από μια απόσταση που μειώνεται σε κάθε πέρασμα. Η ταξινόμηση με κέλυφος  έχει βελτιώσει σημαντικά τους χρόνους εκτέλεσης σε πρακτική εργασία, με δύο απλές παραλλαγές που απαιτούν O(n3/2) and O(n4/3) χρόνους εκτέλεσης.
Εάν το κόστος των συγκρίσεων υπερβαίνει το κόστος των ανταλλαγών, όπως στην περίπτωση για παράδειγμα των κλειδιών με αναφορά ή με ανθρώπινη αλληλεπίδραση( όπως για παράδειγμα διαλέγοντας ένα από τα ζευγάρια που εμφανίζονται το ένα δίπλα στο άλλο), μετά χρησιμοποιώντας δυαδική ταξινόμηση με εισαγωγή μπορούμε να επιτύχουμε καλύτερη εκτέλεση. Η δυαδική ταξινόμηση χρησιμοποιεί μια δυαδική αναζήτηση για να καθορίσει τη σωστή τοποθεσία για την εισαγωγή νέων στοιχείων, οπότε εκτελεί ⌈log₂(n)⌉ συγκρίσεις στη χειρότερη περίπτωση, που είναι O(n log n). Ο αλγόριθμος στο σύνολό του ακόμη έχει ένα χρόνο εκτέλεσης O(n²) κατά μέσο όρο λόγω του αριθμού των ανταλλαγών που απαιτούνται για κάθε εισαγωγή.
Ο αριθμός των ανταλλαγών μπορεί να μειωθεί υπολογίζοντας τη θέση πολλαπλών στοιχείων πριν τη μετακίνησή τους. Για παράδειγμα, εάν η θέση προορισμού δύο στοιχείων έχει υπολογιστεί πριν μετακινηθούν στη σωστή θέση, ο αριθμός των ανταλλαγών μπορεί να μειωθεί περίπου 25% για τυχαία δεδομένα. Στην ακραία περίπτωση αυτή η παραλλαγή λειτουργεί περίπου όμοια με την ταξινόμηση με συγχώνευση.
Για να αποφύγουμε να κάνουμε μια σειρά από ανταλλαγές για κάθε εισαγωγή, η είσοδος μπορεί να αποθηκευθεί σε μια συνδεδεμένη λίστα(linked list), η οποία επιτρέπει στα στοιχεία να συνδεθούν μέσα ή έξω από τη λίστα σε διαρκή χρόνο όταν η θέση στη λίστα δεν είναι γνωστή. Βέβαια, αναζητώντας την συνδεδεμένη λίστα απαιτεί να ακολουθεί διαδοχικά τους συνδέσμους τη επιθυμητής θέσης: μια συνδεδεμένη λίστα δεν έχει τυχαία πρόσβαση, οπότε δε μπορεί να χρησιμοποιήσει μια πιο γρήγορη μέθοδο όπως η δυαδική αναζήτηση. Για το λόγο αυτό, ο χρόνος εκτέλεσης που απαιτείται για αναζήτηση είναι Ο(n) και ο χρόνος για ταξινόμηση είναι O(n²). Αν χρησιμοποιείται μια πιο εξελιγμένη δομή δεδομένων (π.χ., στοίβα ή δυαδικό δέντρο), ο χρόνος που απαιτείται για αναζήτηση και ταξινόμηση μπορεί να μειωθεί σημαντικά. Αυτή είναι η ουσία της ταξινόμησης σωρού (heap sort) ή του δυαδικού δέντρου (binary tree sort).
Το 2004 οι Bender, Farach-Colton και Mosteiro δημοσίευσαν μια νέα παραλλαγή της ταξινόμησης με εισαγωγή με το όνομα ταξινόμηση βιβλιοθήκης(library sort) ή εισαγωγή με κενά που αφήνει ένα μικρό αριθμό από μη χρησιμοποιημένους χώρους (με άλλα λόγια, "κενά") τα οποίοι βρίσκονται διάσπαρτα σε όλο το εύρος του πίνακα. Τα πλεονεκτήματα είναι ότι οι ταξινομήσεις χρειάζονται ολίσθηση στοιχείων μέχρι να βρεθεί σε κενό. Οι συγγραφείς δείχνουν ότι αυτός ο αλγόριθμος ταξινόμησης τρέχει με υψηλή πιθανότητα σε O(n log n) χρόνο.
Αν χρησιμοποιείται μια skip list ο χρόνος μειώνεται σε O(log n), και οι ανταλλαγές δε χρειάζονται επειδή η skip list είναι υλοποιημένη σε δομή συνδεδεμένη λίστα. Ο τελικός χρόνος εκτέλεσης της ταξινόμησης θα ήταν O(n log n).
Η ταξινόμηση με εισαγωγή σε λίστα είναι μια παραλλαγή της ταξινόμησης με εισαγωγή. Μειώνει τον αριθμό των κινήσεων.

Κώδικας της ταξινόμησης με εισαγωγή σε λίστα σε C

Εάν τα στοιχεία είναι αποθηκευμένα σε συνδεδεμένη λίστα τότε η λίστα μπορεί να ταξινομηθεί σε O(1) επιπλέον χώρο. Ο αλγόριθμος ξεκινά με μια αρχικά κενή (και ως εκ τούτου τυχαία ταξινομημένη) λίστα. Τα στοιχεία εισόδου αφαιρούνται από τη λίστα ένα τη φορά και στη συνέχεια εισάγονται στο σωστό σημείο στην ταξινομημένη λίστα. Όταν η λίστα εισόδου είναι κενή, τότε οι ταξινομημένες λίστες έχουν το επιθυμητό αποτέλεσμα.
Ο αλγόριθμος χρησιμοποιεί trailing δείκτη για την εισαγωγή στην ταξινομημένη λίστα. Μια πιο απλή αναδρομική μέθοδος αναδομεί τη λίστα κάθε φορά (αντί να τη διασπά) και μπορεί να χρησιμοποιήσει O(n) χώρο στοίβας.
struct LIST{
  struct LIST * pNext;
  int           iValue;};struct LIST * SortList(struct LIST * pList){
  /* δημιουργία του ταξινομημένου πίνακα από κενή λίστα */
  struct LIST * pSorted = NULL;

  /* εξαγωγή ένα ένα των στοιχείων της λίστας εισαγωγής μέχρι να μείνει κενή */
  while (pList != NULL)
    {
      /* θυμίζουμε το πρώτο στοιχείο λίστας */
      struct LIST *   pHead  = pList;
      /* μετακινούμε το δείκτη για αποτελεσματική σύνδεση */
      struct LIST ** ppTrail = &pSorted;

      /* εξαγωγή του πρώτου στοιχείου της λίστας */
      pList = pList->pNext;

      /* εισαγωγή του πρώτου στοιχείου της λίστας στην ταξινομημένη λίστα στη σωστή θέση */
      while (TRUE)
        {
          /* ανήκει το πρώτο στοιχείο εδώ; */
          if (*ppTrail == NULL || pHead->iValue < (*ppTrail)->iValue)
            {
              /* εάν ανήκει */
              pHead->pNext = *ppTrail;
              *ppTrail = pHead;
              break;
            }
          else
            {
              /* εάν δεν ανήκει - συνέχιση στο υπόλοιπο της λίστας */
              ppTrail = & (*ppTrail)->pNext;
            }
        }
    }

  return pSorted;}