Ταξινόμηση φυσαλίδας: Διαφορά μεταξύ των αναθεωρήσεων
μ Αντικατάσταση παρωχημένου προτύπου με references tag |
|||
Γραμμή 35: | Γραμμή 35: | ||
</source> |
</source> |
||
== Ανάλυση == |
== Ανάλυση Sapounakios == |
||
Ο χρόνος εκτέλεσης εξαρτάται από τον αριθμό των επαναλήψεων του βρόχου '''<code>for</code>''' στις γραμμές <code>2-4</code>. |
Ο χρόνος εκτέλεσης εξαρτάται από τον αριθμό των επαναλήψεων του βρόχου '''<code>for</code>''' στις γραμμές <code>2-4</code>. |
||
* Για δεδομένη τιμή του <code>i</code>, o βρόχος (loop) επαναλαμβάνεται <code>n-i</code> φορές και |
* Για δεδομένη τιμή του <code>i</code>, o βρόχος (loop) επαναλαμβάνεται <code>n-i</code> φορές και |
Έκδοση από την 13:39, 22 Νοεμβρίου 2017
Ταξινόμηση φυσαλίδας (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]
}
}
}
}
Ανάλυση Sapounakios
Ο χρόνος εκτέλεσης εξαρτάται από τον αριθμό των επαναλήψεων του βρόχου for
στις γραμμές 2-4
.
- Για δεδομένη τιμή του
i
, o βρόχος (loop) επαναλαμβάνεταιn-i
φορές και - το
i
παίρνει τιμές .
Συνεπώς, ο συνολικός αριθμός επαναλήψεων είναι:
Επομένως, ο χρόνος εκτέλεσης του αλγόριθμου ταξινόμησης φυσαλίδας είναι σε όλες τις περιπτώσεις [3] [4].
Παραπομπές
- ↑ Knuth, Donald E. (1973). Sorting and searching. Boston [u.a.]: Addison-Wesley. σελίδες 106–107. ISBN 978-0201896855.
- ↑ Swartz, Fred. «Bubble Sorts». http://www.leepoint.net. Ανακτήθηκε στις 31 Μαΐου 2014. Εξωτερικός σύνδεσμος στο
|publisher=
(βοήθεια) - ↑ T. H. Cormen, C. Lee, E. Lin (2002). Instructor's Manual to acompany Introduction to Algorithms. MIT Press and McGraw-Hill. σελίδες 2–21.
- ↑ 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.
Εξωτερικοί σύνδεσμοι
- Ταξινόμηση φυσαλίδας (Bubble sort), Αλεξάνδρειο Τεχνολογικό Εκπαιδευτικό Ίδρυμα Θεσσαλονίκης.