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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Ταξινόμηση φυσαλίδας μιας λίστας τυχαίων αριθμών.
Παράδειγμα ταξινόμησης φυσαλίδας. Ξεκινώντας από την αρχή της λίστας, συγκρίνουμε κάθε γειτονικό ζεύγος, αλλάζουμε τις τιμές αν δεν είναι στην σωστή σειρά. Σε κάθε επανάληψη του αλγόριθμου μια λιγότερη τιμή χρειάζεται να ελεγχθεί. Το αλγόριθμος τερματίζει όταν δεν υπάρχουν άλλα αντικείμενα να συγκριθούν και να γίνουν εναλλαγές.

Ταξινόμηση φυσαλίδας (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]

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

Υλοποίηση σε Java[Επεξεργασία | επεξεργασία κώδικα]

Υπάρχουν διάφορες παραλλαγές υλοποίησης της ταξινόμησης φυσαλίδας. Παρακάτω παρουσιάζεται η κλασική περίπτωση με σταθερό αριθμό επαναλήψεων. [2]

public static void bubbleSort(int[] x) {
    int n = x.length;  
    for (int pass=1; pass < n; pass++) {                          // 1 for i ← 1 to length[A]
        // η επόμενη επανάληψη ολοένα και γίνεται μικρότερη
        for (int i=0; i < n-pass; i++) {                          // 2 do for j ← length[A] downto i + 1
            if (x[i] > x[i+1]) {                                  // 3 do if A[j] < A[j - 1]
                // ανταλλαγή μεγαλύτερου <-> μικρότερου
                int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;  // 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) σε όλες τις περιπτώσεις [3] [4].

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

  1. Knuth, Donald E. (1973). Sorting and searching. Boston [u.a.]: Addison-Wesley. σελ. 106-107. ISBN 978-0201896855. 
  2. Swartz, Fred. «Bubble Sorts». http://www.leepoint.net. http://www.leepoint.net/notes-java/data/arrays/32arraybubblesort.html. Ανακτήθηκε στις 31 Μαΐου 2014. 
  3. T. H. Cormen, C. Lee, E. Lin (2002). Instructor's Manual to acompany Introduction to Algorithms. MIT Press and McGraw-Hill. σελ. 2-21. 
  4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to algorithms (2nd ed. έκδοση). Cambridge, Mass.: MIT Press. σελ. Problem 2-2, pg. 40. ISBN 0-262-03293-7. 

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]