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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Πήδηση στην πλοήγηση Πήδηση στην αναζήτηση
Η γρήγορη ταξινόμηση κατά τη διάρκεια δράσης. Οι οριζόντιες τιμές είναι οι τιμές άξονα (pivot values).

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

Ιστορία[Επεξεργασία | επεξεργασία κώδικα]

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

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

Ο αλγόριθμος[Επεξεργασία | επεξεργασία κώδικα]

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

  • 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 μπορεί να εκφραστεί ως [6]

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[7]:

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

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. Steven S. Skiena (27 April 2011). The Algorithm Design Manual. Springer, σελ. 129. ISBN 978-1-84800-069-8. http://books.google.com/books?id=7XUSn0IKQEgC. Ανακτήθηκε στις 27 November 2012. 
  2. «Data structures and algorithm: Quicksort». Auckland University. 
  3. Shustek, Len (1 March 2009). «InterviewAn interview with C.A.R. Hoare». Communications of the ACM 52 (3): 38. doi:10.1145/1467247.1467261. 
  4. Bentley, Jon L.; McIlroy, M. Douglas (November 1993). «Engineering a sort function». Software: Practice and Experience 23 (11): 1249–1265. doi:10.1002/spe.4380231105. 
  5. Ανδρέου, Παναγιώτης. «Διάλεξη 10: Αλγόριθμοι Ταξινόμησης ΙΙ» (PDF). Πανεπιστήμιο Κύπρου - Τμήμα Πληροφορικής. Ανακτήθηκε στις 7 Νοεμβρίου 2014. 
  6. al.], Thomas H. Cormen ... [et (2009). Introduction to algorithms (3rd ed. έκδοση). Cambridge, Mass.: MIT Press, σελ. 171. ISBN 0-262-03384-4. 
  7. «Introduction to Haskell». haskell.org. Ανακτήθηκε στις 7 Νοεμβρίου 2014. 
  8. Hutton, Graham (2007). Programming in Haskell (5. print. έκδοση). Cambridge [u.a.]: Cambridge Univ. Press, σελ. 8. ISBN 978-0-521-69269-4. http://books.google.gr/books?id=olp7lAtpRX0C&pg=PA8#v=onepage&q&f=false. 
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Quicksort της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).