Προτεινόμενοι Σύνδεσμοι:    greece   -   greece hotels   -   ειδησεις   -   greece news   -   ταβλι στο internet   -   livescore   -   νέα
 easypedia

Easypedia.gr
Ελλάδα
Αρχαία Ελλάδα
Ελληνες
Πρωθυπουργοί
Οικονομία
Γεωγραφία
Ιστορία
Γλώσσα
Πληθυσμός
Μυθολογία
Πολιτισμός & Τέχνες
Ζωγραφική
Θέατρο
Κινηματογράφος
Λογοτεχνία
Μουσική
Αρχιτεκτονική
Γλυπτική
Αθλητισμός
Μυθολογία
Θρησκεία
Θετικές & Φυσικές Επιστήμες
Ανθρωπολογία
Αστρονομία
Βιολογία
Γεωλογία
Επιστήμη υπολογιστών
Μαθηματικά
Τεχνολογία
Φυσική
Χημεία
Ιατρική
Φιλοσοφία & Κοινωνικ. Επιστήμες
Αρχαιολογία
Γλωσσολογία
Οικονομικά
Φιλοσοφία
Ψυχολογία
Γεωγραφία
Ασία
Αφρική
Ευρώπη
Πόλεις
Χώρες
Θάλασσες
Ιστορία
Ελληνική Ιστορία
Αρχαία Ιστορία
Βυζάντιο
Ευρωπαϊκή Ιστορία
Πόλεμοι
Ρωμαϊκή Αυτοκρατορία
Σύγχρονη Ιστορία
 

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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Αυτό το άρθρο είναι ορφανό καθώς λίγα ή και καθόλου άρθρα συνδέουν σε αυτό.

Παρακαλούμε βοηθήστε βάζοντας συνδέσμους προς αυτό σε άρθρα για σχετικά θέματα. (Ιανουαρίου 2008)

Ταξινόμηση φυσαλίδας μιας λίστας τυχαίων αριθμών.
Ταξινόμηση φυσαλίδας μιας λίστας τυχαίων αριθμών.

Ταξινόμηση φυσαλίδας (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} =
= n^2 - \frac{n}{2}


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

Βιβλιογραφία

  • 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