Γρήγορη ταξινόμηση

Στην επιστήμη των υπολογιστών η γρήγορη ταξινόμηση (Αγγλικά: Quick-sort ή ως partition-exchange sort ) είναι ένας αλγόριθμος ταξινόμησης ο οποίος αναπτύχθηκε από τον Tony Hoare, που κατά μέσο όρος κάνει O(nlogn) συγκρίσεις για να ταξινομήσει n στοιχεία. Στην χειρότερη, σπάνια περίπτωση κάνει O(n²) συγκρίσεις. Ο αλγόριθμος γρήγορης ταξινόμησης συχνά είναι γρηγορότερος από αντίστοιχους άλλους  O(nlogn) αλγορίθμους και κατατάσσεται στους αλγορίθμους διαίρει και βασίλευε (όπου το πρόβλημα διασπάται σε μικρότερα προβλήματα και λύνεται το κάθε πρόβλημα ξεχωριστά).  Ο αλγόριθμος αυτός μπορεί να υλοποιηθεί με αναδρομική συνάρτηση.

Ιστορία

Ο αλγόριθμος γρήγορης ταξινόμησης αναπτύχθηκε το 1960 από τον Tony Hoare την εποχή που αυτός ήταν επισκέπτης-φοιτητής στο Κρατικό Πανεπιστήμιο της Μόσχας. Εκείνη την εποχή εργαζόταν σε ένα έργο σχετικό με μηχανική μετάφραση στο Κρατικό Εργαστήριο Φυσικής (National Physical Laboratory) στην Αγγλία. Υπήρχε την εποχή εκείνη ένα λεξικό μεταφρασμένων λέξεων από τα Ρωσικά στα Αγγλικά αποθηκευμένο αλφαβητικά μέσα σε μαγνητική ταινία το οποίο ήθελε να χρησιμοποιήσει για την μηχανική μετάφραση. Έτσι ανέπτυξε τον αλγόριθμο γρήγορης ταξινόμησης με σκοπό να ταξινομήσει αλφαβητικά τις λέξεις που έπρεπε να μεταφραστούν και να χρησιμοποιήσει τα δεδομένα της μαγνητικής ταινίας. 
Ο αλγόριθμος γρήγορης ταξινόμησης κέρδισε την γενικότερη αποδοχή και για παράδειγμα στη βιβλιοθήκη προγραμμάτων του Unix ενσωματώθηκε ως η κύρια συνάρτηση ταξινόμησης. Στην πρότυπη βιβλιοθήκη της γλώσσας προγραμματισμού C πήρε το όνομα  qsort η οποία ενσωματώθηκε αργότερα και στην Java. Ο Robert Sedgewick έκανε διδακτορικό το 1975 στο Πανεπιστήμιο Stanford με αντικείμενο τον αλγόριθμο αυτό. Μέσα στη διδακτορική μελέτη έκανε εκτενή ανάλυση του αλγορίθμου αυτού και πρότεινε νέες βελτιώσεις.

C

/* Για να ταξινομηθεί ένας πίνακας a[] μήκους n καλούμε: qsort(a,0,n-1) */void qsort(int a[], int lo, int hi) {
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p)) 
          l = l+1;
      while ((h > l) && (a[h] >= p))
          h = h-1;
      if (l < h) {
          t = a[l];
          a[l] = a[h];
          a[h] = t;
      }
    } while (l < h);

    a[hi] = a[l];
    a[l] = p;

    qsort( a, lo, l-1 );
    qsort( a, l+1, hi );
  }}

Haskell

quicksort :: Ord a => [a] -> [a]quicksort []     = []quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs
Αν για παράδειγμα έχουμε τη λίστα [3,5,1,4,2] και καλέσουμε τη συνάρτηση quicksort[3,5,1,4,2], θα εκτελεστούν τα παρακάτω βήματα  (το ++ στην Haskell είναι ένωση λιστών και ως στοιχείο pivot - άξονα επιλέγεται το πρώτο στοιχείο της λίστας):
   quicksort[3,5,1,4,2]
=        { εφαρμογή quicksort }
   quicksort[1,2] ++ [3] ++ quicksort[5,4]
=        { εφαρμογή quicksort }
   (quicksort[] ++ [1] ++ quicksort[2]) ++ [3] ++ (quicksort[4] ++ [5] ++ quicksort[])
=        { η quicksort σε λίστα με ένα ή κανένα στοιχείο θεωρεί ότι είναι ήδη ταξινομημένη }
   ([] ++ [1] ++ [2]) ++ [3] ++ ([4] ++ [5] ++ [])
=  (συνένωση λιστών / ++)
   [1,2] ++ [3] ++ [4,5]
=  (συνένωση λιστών / ++)
   [1,2,3,4,5]