Επειδή ζητήθηκε, δίνεται επεξήγηση του Αλγόριθμου φυσαλίδας:
Αλγόριθμος Φυσαλίδα
___Για i από 2 μέχρι N
______Για j από N μέχρι i
_________Αν A[j-1]>A[j] τότε
____________temp <- A[j]
____________A[j] <- A[j-1]
____________A[j-1] <- temp
_________Τέλος_αν
______Τέλος_επανάληψης
___Τέλος_επανάληψης
Τέλος_αλγορίθμου
Ξεκινώντας από μέσα προς τα έξω (Αν, εσωτερικό Για, εξωτερικό Για):
Αν ικανοποιείται η συνθήκη, δηλαδή, το πάνω στοιχεία είναι μεγαλύτερο από το κάτω, τότε αλλάζουν θέση, ώστε να υπάρχει αύξουσα σειρά μεταξύ των δύο τους.
Ο εσωτερικός βρόγχος ξεκινάει από το τελευταίο στοιχείο του πίνακα και ανεβαίνει προς τα πάνω, μέχρι να βρει το στοιχείο i, ελέγχοντας και εφαρμόζοντας τη συνθήκη στα στοιχεία j και j-1.
Ο εξωτερικός βρόγχος, ουσιαστικά, υπάρχει ως φράγμα για τον εσωτερικό. Ξεκινάει από την τιμή 2 γιατί, αν ξεκινούσε από την 1, το j θα ανέβαινε ως την πρώτη θέση και θα σύγκρινε το στοιχείο της με το απο πάνω... το οποίο δεν υπάρχει (δεν ορίζεται A[0]. Επίσης γίνεται για την βελτιστοποίηση της ταχύτητας εκτέλεσης τους αλγορίθμου (εξηγείται παρακάτω).
Για να φαίνεται σχηματικά, έστω ο πίνακα [5,9,4,7,0,2,1]
Ξεκινάει να εκτελείται ο αλγόριθμος, το i παίρνει την τιμή 2 και εισέρχεται στον εσωτερικό βρόγχο. Το j παίρνει την τιμή 7 και ελέγχεται το 7ο και 6ο κελί. Το 1<2, άρα αντιμετίθονται.
[5,9,4,7,0,1,2]
To j παίρνει την τιμή 6 και ελέγχεται το 6ο και 5ο κελί. 1>0 άρα δεν αλλάζει τίποτα.
Η διαδικασία συνεχίζεται ως εξής:
j:5 -> [5,9,4,0,7,1,2]
j:4 -> [5,9,0,4,7,1,2]
j:3 -> [5,0,9,4,7,1,2]
j:2 -> [0,5,9,4,7,1,2]
Πλέον, το μικρότερο στοιχείο του πίνακα βρίσκεται στην 1η θέση. Το i αυξάνεται και γίνεται 3 και ξαναρχίζει από την αρχή ο εσωτερικός βρόγχος:
j:7 -> [0,5,9,4,7,1,2]
j:6 -> [0,5,9,4,1,7,2]
j:5 -> [0,5,9,1,4,7,2]
j:4 -> [0,5,1,9,4,7,2]
j:3 -> [0,1,5,9,4,7,2]
Αν ο εσωτερικός βρόγχος δεν σταματούσε στο i, αλλά στο 2, ΔΕΝ θα υπήρχε πρόβλημα. Θα γίνονταν κανονικά η σύγκριση 1>0 και η σειρά θα έμενε ίδια. ΟΜΩΣ, κατά την πρώτη ταξινόμηση, βεβαιωθήκαμε ότι το 1ο στοιχείο του πίνακα είναι το μικρότερο δυνατό. Άρα, ο έλεγχος αν το 1 είναι μικρότερο του 0 είναι περιττός.
Κατά παρόμοιο τρόπο, μετά το πέρας της 3ης εξωτερικής επανάληψης θα έχουμε:
j:4 -> [0,1,2,5,9,4,7]
Κατά τις 2 πρώτες εκτελέσεις βεβαιωθήκαμε ότι το 1ο στοιχείο είναι το μικρότερο, το 2ο στοιχείο είναι το 2ο στη σειρά μικρότερο. Επομένως, είναι περιττό να ελέγξουμε το 2 με το 1 και το 1 με το 0...
Κατά την τελευταία εκτέλεση του αλγορίθμου, θα εξεταστούν ΜΟΝΟ το τελευταίο και προτελευταίο στοιχείο, θα τελειώσουν και οι δύο βρόγχοι και ο αλγόριθμος θα τερματίσει.
Ο πίνακας θα έχει την εξής μορφή:
[0,1,2,4,5,7,9]
Σημείωση: Το μήνυμα αυτό γράφτηκε 10 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.
Αρχική Forum
Ρωτήστε κάτι
Προσωπικές Συζητήσεις
Πανελλαδικές
Αγγελίες
Συνδεδεμένοι Χρήστες
Λίστα Αποκλεισμένων
Υπεύθυνοι του Forum
e-steki
)
