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

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

Ιστορία

Ο αλγόριθμος γρήγορης ταξινόμησης αναπτύχθηκε το 1960 από τον Τόνι Χορ την εποχή που αυτός ήταν επισκέπτης-φοιτητής στο Κρατικό Πανεπιστήμιο της Μόσχας. Εκείνη την εποχή εργαζόταν σε ένα έργο σχετικό με μηχανική μετάφραση στο Κρατικό Εργαστήριο Φυσικής (National Physical Laboratory) στην Αγγλία. Υπήρχε την εποχή εκείνη ένα λεξικό μεταφρασμένων λέξεων από τα Ρωσικά στα Αγγλικά αποθηκευμένο αλφαβητικά μέσα σε μαγνητική ταινία το οποίο ήθελε να χρησιμοποιήσει για την μηχανική μετάφραση. Έτσι ανέπτυξε τον αλγόριθμο γρήγορης ταξινόμησης με σκοπό να ταξινομήσει αλφαβητικά τις λέξεις που έπρεπε να μεταφραστούν και να χρησιμοποιήσει τα δεδομένα της μαγνητικής ταινίας. ^[4]

Ο αλγόριθμος γρήγορης ταξινόμησης κέρδισε την γενικότερη αποδοχή και για παράδειγμα στη βιβλιοθήκη προγραμμάτων του Unix ενσωματώθηκε ως η κύρια συνάρτηση ταξινόμησης. Στην πρότυπη βιβλιοθήκη της γλώσσας προγραμματισμού C πήρε το όνομα qsort η οποία ενσωματώθηκε αργότερα και στην Java. Ο Robert Sedgewick έκανε διδακτορικό το 1975 στο Πανεπιστήμιο Στάνφορντ με αντικείμενο τον αλγόριθμο αυτό. Μέσα στη διδακτορική μελέτη έκανε εκτενή ανάλυση του αλγορίθμου αυτού και πρότεινε νέες βελτιώσεις.^[5]

Ο αλγόριθμος

Έστω ότι έχουμε ένα πίνακα/λίστα με στοιχεία που θέλουμε να ταξινομήσουμε ^[6]:

Aν ο πίνακας έχει 0 ή 1 στοιχεία δεν κάνουμε τίποτα (είναι ήδη ταξινομημένος)
Αλλιώς αναδρομικά κάνουμε:
1. Επιλέγουμε ένα στοιχείο p (το οποίο ονομάζουμε pivot - άξονα) και το αφαιρούμε από την πίνακα/λίστα εισόδου.
2. Χωρίζουμε τον πίνακα/λίστα σε 2 μέρη: S1 και S2, όπου το S1 θα περιέχει όλα τα στοιχεία που είναι μικρότερα από το p και το S2 όπου περιέχονται όλα τα υπόλοιπα στοιχεία τα οποία είναι μεγαλύτερα ή ίσα με p.
3. Καλούμε τον αλγόριθμο αναδρομικά στο S1, παίρνουμε απάντηση στο T1 και στο S2 και παίρνουμε απάντηση στο T2.
4. Επιστρέφουμε τον πίνακα [T1, p, T2]

Με μορφή ψευδογλώσσας, ο αλγόριθμος ταξινόμησης το οποίος ταξινομεί στοιχεία από το p μέχρι το r σε ένα πίνακα A μπορεί να εκφραστεί ως ^[7]

quicksort(A, p, r):
  if p < r:
    q = partition(A, p, r)
    quicksort(A, p, q - 1)
    quicksort(A, q + 1, r)

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

partition(A, p, r):
   x = A[r]
   i = p-1
   for j=p to r-1
       if A[j] <= x
           i = i+1
           αντιμετάθεση A[i] με A[j]
   αντιμετάθεση A[i+1] με A[r]
   return i+1

Αν θέλουμε να ταξινομήσουμε ολόκληρο τον πίνακα καλούμε quicksort(A,1,A.length). Παρακάτω παρουσιάζεται η υλοποίηση της γρήγορης ταξινόμησης σε C και Haskell^[8]:

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], θα εκτελεστούν τα παρακάτω βήματα ^[9] (το ++ στην 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]

Δείτε επίσης

Sedgewick, Robert· Wayne, Kevin. «Quicksort». Princeton University. Ανακτήθηκε στις 7 Νοεμβρίου 2014.
«Quicksort implementations». rosettacode.org. Ανακτήθηκε στις 7 Νοεμβρίου 2014.
Vogel, Lars. «Quicksort in Java - Tutorial». vogella.com. Ανακτήθηκε στις 7 Νοεμβρίου 2014.
Venugopal, Sesh. «Quicksort Part 1 - Algorithm (video)». Rutgers University. Ανακτήθηκε στις 7 Νοεμβρίου 2014.

Παραπομπές

↑ Hoare, C. A. R. (1961). «Algorithm 64: Quicksort». Communications of the ACM 4 (7): 321. doi:doi:10.1145/366622.366644.
↑ Steven S. Skiena (27 Απριλίου 2011). The Algorithm Design Manual. Springer. σελ. 129. ISBN 978-1-84800-069-8. Ανακτήθηκε στις 27 Νοεμβρίου 2012.
↑ «Data structures and algorithm: Quicksort». Auckland University. Αρχειοθετήθηκε από το πρωτότυπο στις 5 Δεκεμβρίου 2013. Ανακτήθηκε στις 7 Νοεμβρίου 2014.
↑ Shustek, Len (1 March 2009). «InterviewAn interview with C.A.R. Hoare». Communications of the ACM 52 (3): 38. doi:10.1145/1467247.1467261.
↑ Bentley, Jon L.; McIlroy, Douglas M. (November 1993). «Engineering a sort function». Software: Practice and Experience 23 (11): 1249–1265. doi:10.1002/spe.4380231105. https://archive.org/details/sim_software-practice-experience_1993-11_23_11/page/1249.
↑ Ανδρέου, Παναγιώτης. «Διάλεξη 10: Αλγόριθμοι Ταξινόμησης ΙΙ» (PDF). Πανεπιστήμιο Κύπρου - Τμήμα Πληροφορικής. Ανακτήθηκε στις 7 Νοεμβρίου 2014.
↑ Cormen, Thomas H.· Leiserson, Charles E.· Rivest, Ronald L.· Stein, Clifford (2009). Introduction to algorithms (3η έκδοση). Cambridge, Mass.: MIT Press. σελίδες 171. ISBN 0-262-03384-4.
↑ «Introduction to Haskell». haskell.org. Ανακτήθηκε στις 7 Νοεμβρίου 2014.
↑ Hutton, Graham (2007). Programming in Haskell (5. print. έκδοση). Cambridge [u.a.]: Cambridge Univ. Press. σελ. 8. ISBN 978-0-521-69269-4.

[1] Hoare, C. A. R. (1961). «Algorithm 64: Quicksort». Communications of the ACM 4 (7): 321. doi:doi:10.1145/366622.366644.

[2] Steven S. Skiena (27 Απριλίου 2011). The Algorithm Design Manual. Springer. σελ. 129. ISBN 978-1-84800-069-8. Ανακτήθηκε στις 27 Νοεμβρίου 2012.

[3] «Data structures and algorithm: Quicksort». Auckland University. Αρχειοθετήθηκε από το πρωτότυπο στις 5 Δεκεμβρίου 2013. Ανακτήθηκε στις 7 Νοεμβρίου 2014.

[4] Shustek, Len (1 March 2009). «InterviewAn interview with C.A.R. Hoare». Communications of the ACM 52 (3): 38. doi:10.1145/1467247.1467261.

[engineering-5] Bentley, Jon L.; McIlroy, Douglas M. (November 1993). «Engineering a sort function». Software: Practice and Experience 23 (11): 1249–1265. doi:10.1002/spe.4380231105. https://archive.org/details/sim_software-practice-experience_1993-11_23_11/page/1249.

[6] Ανδρέου, Παναγιώτης. «Διάλεξη 10: Αλγόριθμοι Ταξινόμησης ΙΙ» (PDF). Πανεπιστήμιο Κύπρου - Τμήμα Πληροφορικής. Ανακτήθηκε στις 7 Νοεμβρίου 2014.

[7] Cormen, Thomas H.· Leiserson, Charles E.· Rivest, Ronald L.· Stein, Clifford (2009). Introduction to algorithms (3η έκδοση). Cambridge, Mass.: MIT Press. σελίδες 171. ISBN 0-262-03384-4.

[8] «Introduction to Haskell». haskell.org. Ανακτήθηκε στις 7 Νοεμβρίου 2014.

[9] Hutton, Graham (2007). Programming in Haskell (5. print. έκδοση). Cambridge [u.a.]: Cambridge Univ. Press. σελ. 8. ISBN 978-0-521-69269-4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]