Ταξινόμηση φυσαλίδας

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Ταξινόμηση φυσαλίδας
Ταξινόμηση
Dewey 519
MSC2010 68P10
Ταξινόμηση φυσαλίδας μιας λίστας τυχαίων αριθμών.

Ταξινόμηση φυσαλίδας (bubble sort) είναι το όνομα ενός απλού αλγόριθμου ταξινόμησης. Λειτουργεί συγκρίνοντας βηματικά τα στοιχεία μιας λίστας και εναλλάσοντας τα ώστε να βρεθούν σε σωστή σειρά. Τα βήματα επαναλαμβάνονται μέχρι να ταξινομηθεί ολόκληρη η λίστα.

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

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

BUBBLESORT(A)
1 for i ← 1 to length[A]
2 do for j ← length[A] downto i + 1
3 do if A[j] < A[j - 1]
4 then exchange A[j] ↔ A[j - 1]

όπου Α είναι ένας πίνακας στοιχείων.

Ανάλυση[Επεξεργασία | επεξεργασία κώδικα]

Ο χρόνος εκτέλεσης εξαρτάται από τον αριθμό των επαναλήψεων του βρόχου for στις γραμμές 2-4.

  • Για δεδομένη τιμή του i, o βρόχος (loop) επαναλαμβάνεται n-i φορές και
  • το i παίρνει τιμές 1,\ 2,\ ... ,\ n.

Συνεπώς, ο συνολικός αριθμός επαναλήψεων είναι:

 \sum_{i=1}^n (n-i) = \sum_{i=1}^n n - \sum_{i=1}^n i =

= n^2 - \frac{n(n+1)}{2} =
= n^2 - \frac{n^2}{2} - \frac{n}{2} =
= \frac{n^2 - n}{2}

Επομένως, ο χρόνος εκτέλεσης του αλγόριθμου ταξινόμησης φυσαλίδας είναι \Theta (n^2) σε όλες τις περιπτώσεις.

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (2nd Edition), MIT Press and McGraw-Hill, 2001
  • T. H. Cormen, C. Lee, E. Lin, Instructor's Manual to acompany Introduction to Algorithms (2nd Edition), MIT Press and McGraw-Hill, 2002
  • D. E. Knuth, The art of computer programming (Volume 3), Addison-Wesley, 2nd Edition, 1998