ΕΚΦΩΝΗΣΗ:
Ο αλγόριθμος της φυσαλίδας όπως διατυπώθηκε στην παράγραφο 3.7 έχει το μειονέκτημα ότι δεν είναι αρκετά “έξυπνος” ώστε να διαπιστώνει στην αρχή ή στο μέσο της διαδικασίας αν ο πίνακας είναι ταξινομημένος. Να σχεδιασθεί μία παραλλαγή του αλγορίθμου αυτού που να σταματά όταν διαπιστωθεί ότι τα στοιχεία του πίνακα είναι ήδη ταξινομημένα. Υπόδειξη: Να χρησιμοποιήσετε μία βοηθητική μεταβλητή που να ελέγχει το τέλος κάθε επανάληψης του εξωτερικού βρόχου (“Για i από 2 μέχρι n”) αν για την τρέχουσα τιμή του i έγιναν αντιμεταθέσεις στοιχείων.
ΛΥΣΗ:
Η εκφώνηση ουσιαστικά αναφέρεται στην παραλλαγή της ταξινόµησης φυσαλίδας που αντιλαµβάνεται πότε ο πίνακας έχει ουσιαστικά ταξινοµηθεί και αποφεύγει τα περιττά περάσµατα (που σε συνολικό αριθµό είναι n-1). Αυτό επιτυγχάνεται µε τη βοήθεια µίας λογικής µεταβλητής, (µίας σηµαίας flag), που πριν κάθε πέρασµα αρχικοποιείται ως ψευδής και αλλάζει ως αληθής αν σε κάποιο πέρασµα γίνει έστω και µία ανταλλαγή. Έτσι, αν σε κάποιο πέρασµα δεν εκτελεσθεί καµία ανταλλαγή, τότε η σηµαία παραµένει ψευδής και αυτοµάτως τελειώνει ο αλγόριθµος.
<span class="DL">ΠΡΟΓΡΑΜΜΑ</span> <span class="AN">Έξυπνη_Φυσαλίδα</span>
<span class="DL">ΣΤΑΘΕΡΕΣ</span>
<span class="AN">n</span> <span class="SB">=</span> <span class="AK">5</span>
<span class="DL">ΜΕΤΑΒΛΗΤΕΣ</span>
<span class="DL">ΑΚΕΡΑΙΕΣ</span><span class="SB">:</span> <span class="AN">i</span><span class="SB">,</span> <span class="AN">j</span><span class="SB">,</span> <span class="AN">table</span><span class="SB">[</span><span class="AN">n</span><span class="SB">]</span><span class="SB">,</span> <span class="AN">temp</span>
<span class="DL">ΛΟΓΙΚΕΣ</span><span class="SB">:</span> <span class="AN">flag</span>
<span class="DL">ΑΡΧΗ</span>
<span class="DL">ΓΙΑ</span> <span class="AN">i</span> <span class="DL">ΑΠΟ</span> <span class="AK">1</span> <span class="DL">ΜΕΧΡΙ</span> <span class="AN">n</span>
<span class="DL">ΔΙΑΒΑΣΕ</span> <span class="AN">table</span><span class="SB">[</span><span class="AN">i</span><span class="SB">]</span>
<span class="DL">ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
</span>
<span class="AN">flag</span> <span class="SB"><-</span> <span class="DL">ΑΛΗΘΗΣ</span>
<span class="AN">i</span> <span class="SB"><-</span> <span class="AK">2</span>
<span class="DL">ΟΣΟ</span> <span class="AN">i</span> <span class="SB"><=</span> <span class="AN">n</span> <span class="DL">ΚΑΙ</span> <span class="AN">flag</span> <span class="SB">=</span> <span class="DL">ΑΛΗΘΗΣ</span> <span class="DL">ΕΠΑΝΑΛΑΒΕ</span>
<span class="AN">flag</span> <span class="SB"><-</span> <span class="DL">ΨΕΥΔΗΣ</span>
<span class="DL">ΓΙΑ</span> <span class="AN">j</span> <span class="DL">ΑΠΟ</span> <span class="AN">n</span> <span class="DL">ΜΕΧΡΙ</span> <span class="AN">i</span> <span class="DL">ΜΕ</span> <span class="DL">ΒΗΜΑ</span> <span class="SB">-</span><span class="AK">1</span>
<span class="DL">ΑΝ</span> <span class="AN">table</span><span class="SB">[</span><span class="AN">j</span><span class="SB">]</span> <span class="SB"><</span> <span class="AN">table</span><span class="SB">[</span><span class="AN">j</span> <span class="SB">-</span> <span class="AK">1</span><span class="SB">]</span> <span class="DL">ΤΟΤΕ</span>
<span class="AN">temp</span> <span class="SB"><-</span> <span class="AN">table</span><span class="SB">[</span><span class="AN">j</span> <span class="SB">-</span> <span class="AK">1</span><span class="SB">]</span>
<span class="AN">table</span><span class="SB">[</span><span class="AN">j</span> <span class="SB">-</span> <span class="AK">1</span><span class="SB">]</span> <span class="SB"><-</span> <span class="AN">table</span><span class="SB">[</span><span class="AN">j</span><span class="SB">]</span>
<span class="AN">table</span><span class="SB">[</span><span class="AN">j</span><span class="SB">]</span> <span class="SB"><-</span> <span class="AN">temp
</span>
<span class="AN">flag</span> <span class="SB"><-</span> <span class="DL">ΑΛΗΘΗΣ</span>
<span class="DL">ΤΕΛΟΣ_ΑΝ</span>
<span class="DL">ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ</span>
<span class="AN">i</span> <span class="SB"><-</span> <span class="AN">i</span> <span class="SB">+</span> <span class="AK">1</span>
<span class="DL">ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ</span>
<span class="DL">ΓΙΑ</span> <span class="AN">i</span> <span class="DL">ΑΠΟ</span> <span class="AK">1</span> <span class="DL">ΜΕΧΡΙ</span> <span class="AN">n</span>
<span class="DL">ΓΡΑΨΕ</span> <span class="AN">table</span><span class="SB">[</span><span class="AN">i</span><span class="SB">]</span>
<span class="DL">ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ</span>
<span class="DL">ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ</span>
Πρόσφατα σχόλια