Συνήθως στη ταξινόμηση φυσαλίδας δείχνουν μια ταξινόμηση ενός σταθερού πίνακα τιμών που ξεκινάει από το πρώτο στοιχείο προς το τελευταίο, και με διαδοχικά περάσματα ο αλγόριθμος σταματάει ότι σε ένα πέρασμα δεν γίνεται καμία αλλαγή
Στο πρόγραμμα που ακολουθεί (το γράφουμε σε ένα τμήμα, με αντιγραφή από εδώ), βλέπουμε δυο αλγόριθμους, ένας δουλεύει από κάτω προς τα πάνω και ένας ανάποδα. Στη πράξη αν ο πίνακας αυξάνεται από το τέλος, δηλαδή είχε 10 στοιχεία και τα κάνουμε 11, τότε θα θέλαμε η ταξινόμηση να γίνεται από πάνω προς τα κάτω, ειδικά όταν τα πρώτα 10 είναι ήδη ταξινομημένα! Αυτό το πρόγραμμα δείχνει με οπτικό τρόπο γιατί μας συμφέρει αυτό! Ο στάνταρ τρόπος θα ήταν καλός αν βάζαμε τα νέα στοιχεία πριν από τα παλιά, δηλαδή τα παλιά να μετακινηθούν ένα στοιχείο για να έχουμε θέση για το πρώτο νέο στοιχείο. Αυτό είναι εύκολο στη Μ2000 γιατί με το Α#Αρχή((200,)) βάζουμε τον αυτόματο πίνακα ενός στοιχείου, το (200,) πριν από τα στοιχεία του Α() και ο νέος πίνακας γίνεται ο νέος Α(), που στην ρουτίνα ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ_1 είναι τοπική ως Α() άρα δεν είναι το Α() πριν την κλήση.
Σε κάθε περίπτωση μετράμε τις αλλαγές και τις συγκρίσεις και καλούμε μια απλή ρουτίνα (μόνο με μια ΔΙΑΜΕΣΟΥ (GOSUB) και επιστροφή με το ΕΠΙΣΤΡΟΦΗ (RETURN) (όπως στη BASIC).
Γενικά οι Ρουτίνες (ΡΟΥΤΙΝΑ/ΤΕΛΟΣ ΡΟΥΤΙΝΑΣ) όπως και οι απλές ρουτίνες (ΕΤΙΚΕΤΑ/ΕΠΙΣΤΡΟΦΗ), έχουν θέαση στα στοιχεία του τμήματος. Η απλή ρουτίνα δεν έχει τοπικές μεταβλητές (αν φτιάξουμε με το ΤΟΠΙΚΗ ή ΤΟΠΙΚΕΣ δεν θα μας πει οχι το σύστημα αλλά στην επιστροφή δεν θα τις σβήσει, άρα σε κάθε κλήση θα σκιάζουμε τις προηγούμενες με το ίδιο όνομα!
Τα τμήματα διαφέρουν από τις ρουτίνες γιατί εντός ενός τμήματος βλέπουμε ότι φτιάχνουμε και μόνο ότι έχει δηλωθεί και φτιαχτεί πιο πριν ως γενικό, αλλά πάντα κάτι τοπικό με το ίδιο όνομα σκιάζει το γενικό. Σς αντικελίμενα το τμήμα είναι μεθοδος και βλέπει επίσης και τις ιδιότητες, μεταβλητές και τμήματα/συναρτήσεις του αντικειμένου. Επίσης δεν μπορούμε να κάνουμε άλματα ή να καλέσουμ διαμέσου ετικέτας σε ετικέτα εκτός του τμήματος, όπως μπορούμε να κάνουμε σε ρουτίνα. Ένα τμήμα δεν βλέπει ούτε το "αδελφάκι" τμήμα που φτιάχτηκε στο ίδιο "γονικό" τμήμα (με εξαίρεση τα τμήματα ενός αντικειμένου που αποτελούν μεθόδους του. Επίσης δεν μπορεί να καλέσει τον εαυτό του με το όνομά του μόνο (θέλει μια ΚΑΛΕΣΕ όνομα_τμήματος). Μια ρουτίνα μπορεί να καλέσει τον εαυτό της!
Τα τμήματα όπως και οι ρουτίνες μεταβιβάζουν τον τρέχον σωρό στη κλήση οπότε αν θέλουμε (με προσοχή) μπορούμε να αφήνουμε στοιχεία στο σωρό τιμών. Για παράδειγμα μπορούμε να βάλουμε στο σωρό τιμών το όρισμα της παραμέτρου (του Α()) και μετά να καλέσουμε τη ρούτινα:
ΒΑΛΕ Α()#ΑΡΧΗ((200,)): ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ_1
Η ρουτίνα ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ_1 παίρνει τον πίνακα και τον βάζει στο Α() χωρίς να ορίσουμε με την ΠΙΝΑΚΑΣ τον πίνακα. Επειδή δουλεύουμε εδώ με μιας διάστασης πίνακα, μαθαίνουμε πόσα στοιχεία έχει με την ΜΗΚΟΣ(Α()) και εξ ορισμού η βάση των πινάκων είναι το 0 άρα έχουμε από το 0 έως το ΜΗΚΟΣ(Α())-1 δείκτες για στοιχεία στο Α(). Και στις δυο ρουτίνες δουλεύουμε με δυο μεταβλητές που αυξάνουμε μαζί ή μειώνουμε ανάλογα από που ξεκινάμε.
1 100 87 55 45 3 2
1 2 100 87 55 45 3
1 2 3 100 87 55 45
1 2 3 45 100 87 55
1 2 3 45 55 100 87
1 2 3 45 55 87 100
1 2 3 45 55 87 100
ΑΛΛΑΓΕΣ:21
ΣΥΓΚΡΙΣΕΙΣ:42
1 2 3 45 55 87 100
1 2 3 45 55 87 100
ΑΛΛΑΓΕΣ:0
ΣΥΓΚΡΙΣΕΙΣ:6
2 3 45 55 87 100 1
1 2 3 45 55 87 100
1 2 3 45 55 87 100
ΑΛΛΑΓΕΣ:6
ΣΥΓΚΡΙΣΕΙΣ:12
100 1 2 3 45 55 87
1 100 2 3 45 55 87
1 2 100 3 45 55 87
1 2 3 100 45 55 87
1 2 3 45 100 55 87
1 2 3 45 55 100 87
1 2 3 45 55 87 100
1 2 3 45 55 87 100
ΑΛΛΑΓΕΣ:6
ΣΥΓΚΡΙΣΕΙΣ:42
100 1 2 3 45 55 87
1 2 3 45 55 87 100
1 2 3 45 55 87 100
ΑΛΛΑΓΕΣ:6
ΣΥΓΚΡΙΣΕΙΣ:12
1 2 55 3 45 87 100
1 2 3 55 45 87 100
1 2 3 45 55 87 100
1 2 3 45 55 87 100
ΑΛΛΑΓΕΣ:2
ΣΥΓΚΡΙΣΕΙΣ:18
1 2 55 3 45 87 100
1 2 3 45 55 87 100
1 2 3 45 55 87 100
ΑΛΛΑΓΕΣ:2
ΣΥΓΚΡΙΣΕΙΣ:12
1 2 3 45 55 87 100 -10
-10 1 2 3 45 55 87 100
-10 1 2 3 45 55 87 100
ΑΛΛΑΓΕΣ:7
ΣΥΓΚΡΙΣΕΙΣ:14
200 -10 1 2 3 45 55 87 100
-10 1 2 3 45 55 87 100 200
-10 1 2 3 45 55 87 100 200
ΑΛΛΑΓΕΣ:8
ΣΥΓΚΡΙΣΕΙΣ:16
ΣΤΑΤΙΚΗ ΡΟΥΤΙΝΑ ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ_1
' για να καλούμε τη ρουτίνα χωρίς παρενθέσεις.
ΜΕΤΑΒΛΗΤΕΣ ΑΛΛΑΓΕΣ, ΣΥΓΚΡΙΣΕΙΣ, ΠΡΟΗΓΟΥΜΕΝΕΣ
ΜΕΤΑΒΛΗΤΕΣ Κ, Ι, Τ1, Τ2
ΤΥΠΩΣΕ "ΤΑΞΙΜΟΜΗΣΗ ΦΥΣΑΛΙΔΑΣ"
ΠΙΝΑΚΑΣ Α()
Α()=(100,87,55,45,3, 2,1) ' 21 ΑΛΛΑΓΕΣ 42 ΣΥΓΚΡΙΣΕΙΣ
ΔΙΑΜΕΣΟΥ ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ
Α()=(1,2,3,45,55,87,100) ' 0 ΑΛΛΑΓΕΣ 6 ΣΥΓΚΡΙΣΕΙΣ
ΔΙΑΜΕΣΟΥ ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ
Α()=(2,3,45,55,87,100,1) ' 6 ΑΛΛΑΓΕΣ 12 ΣΥΓΚΡΙΣΕΙΣ
ΔΙΑΜΕΣΟΥ ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ
Α()=(100,1,2,3,45,55,87)
ΔΙΑΜΕΣΟΥ ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ ' 6 ΑΛΛΑΓΕΣ 42 ΣΥΓΚΡΙΣΕΙΣ
ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ_1 (100,1,2,3,45,55,87) ' 6 ΑΛΛΑΓΕΣ 12 ΣΥΓΚΡΙΣΕΙΣ
Α()=(1,2,55,3,45,87,100) ' 2 ΑΛΛΑΓΕΣ 18 ΣΥΓΚΡΙΣΕΙΣ
ΔΙΑΜΕΣΟΥ ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ
' 2 ΑΛΛΑΓΕΣ 18 ΣΥΓΚΡΙΣΕΙΣ
ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ_1 (1,2,55,3,45,87,100)
' ΕΔΩ ΕΙΝΑΙ ΤΟ ΚΕΡΔΟΣ ΑΝ ΕΧΟΥΜ ΗΔΗ ΤΑΞΙΝΟΜΗΜΕΜΟ ΠΙΝΑΚΑ
' ΑΝΑΛΟΓΑ ΑΝ ΒΑΛΟΥΜΕ ΕΝΑ ΝΕΟ ΣΤΟΙΧΕΙΟ ΣΤΗΝ ΑΡΧΗ Η ΣΤΟ ΤΕΛΟΣ
' ΔΙΑΛΕΓΟΥΜΕ ΡΟΥΤΙΝΑ
' ΒΆΖΟΥΜΕ ΕΝΑΝ ΠΙΝΑΚΑ ΣΤΟ ΤΕΛΟΣ ΤΟΥ ΠΙΝΑΚΑ
Α()=Α()#ΤΕΛΟΣ((-10,)) ' ΣΥΜΦΕΡΕΙ Η ΑΝΑΣΤΡΟΦΗ
ΔΙΑΜΕΣΟΥ ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ ' 7 ΑΛΛΑΓΡΣ 14 ΣΥΓΚΡΙΣΕΙΣ
' ΒΑΖΟΥΜΕ ΕΝΑΝ ΠΙΝΑΚΑ ΣΤΗΝ ΑΡΧΗ ΤΟΥ ΠΙΝΑΚΑ
ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ_1 Α()#ΑΡΧΗ((200,)) ' 8 ΑΛΛΑΓΕΣ 16 ΣΥΓΚΡΙΣΕΙΣ
ΤΕΛΟΣ
' ΧΡΗΣΗ ΡΟΥΤΙΝΑΣ ΜΕ ΤΟΠΙΚΕΣ ΜΕΤΑΒΛΗΤΕΣ
' ΚΛΗΣΗ ΑΠΛΩΝ ΡΟΥΤΙΝΩΝ ΜΕΣΑ ΑΠΟ ΤΗΝ ΡΟΥΤΙΝΑ
' ΞΕΚΙΝΑΕΙ ΑΠΟ ΤΟ ΠΡΩΤΟ ΣΤΟΙΧΕΙΟ ΠΡΟΣ ΤΟ ΤΕΛΕΥΤΑΙΟ
ΡΟΥΤΙΝΑ ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ_1(Α())
ΤΟΠΙΚΕΣ ΑΛΛΑΓΕΣ=0, ΣΥΓΚΡΙΣΕΙΣ=0, ΠΡΟΗΓΟΥΜΕΝΕΣ=0
ΤΟΠΙΚΕΣ Τ1=ΜΗΚΟΣ(Α()), Τ2=Τ1-1, Κ, Ι
ΑΝ Τ2<1 ΤΟΤΕ ΛΑΘΟΣ "ΘΕΛΩ ΤΟΥΛΑΧΙΣΤΟΝ ΔΥΟ ΣΤΟΙΧΕΙΑ"
ΔΙΑΜΕΣΟΥ ΕΜΦΑΝΙΣΗ_ΠΙΝΑΚΑ
ΕΠΑΝΕΛΑΒΕ
Κ=0:Ι=Κ+1: ΠΡΟΗΓΟΥΜΕΝΕΣ=ΑΛΛΑΓΕΣ
ΕΠΑΝΕΛΑΒΕ ΣΥΓΚΡΙΣΕΙΣ++
ΑΝ Α(Ι)<Α(Κ) ΤΟΤΕ ΑΛΛΑΞΕ Α(Ι), Α(Κ): ΑΛΛΑΓΕΣ++
Ι++:Κ++
ΟΣΟ Ι<Τ1
ΔΙΑΜΕΣΟΥ ΕΜΦΑΝΙΣΗ_ΠΙΝΑΚΑ
ΟΣΟ ΠΡΟΗΓΟΥΜΕΝΕΣ<>ΑΛΛΑΓΕΣ
ΔΙΑΜΕΣΟΥ ΑΠΟΤΕΛΕΣΜΑΤΑ
ΤΕΛΟΣ ΡΟΥΤΙΝΑΣ
' ΧΡΗΣΗ ΑΠΛΗΣ ΡΟΥΤΙΝΑΣ ΧΩΡΙΣ ΤΟΠΙΚΕΣ ΜΕΤΑΒΛΗΤΕΣ
' ΕΠΙΣΗΣ ΧΡΗΣΗ ΕΤΙΚΕΤΩΝ ΚΑΙ ΤΗΣ ΠΡΟΣ (GOTO)
' ΞΕΚΙΝΑΕΙ ΑΠΟ ΤΕΛΕΥΤΑΙΟ ΣΤΟΙΧΕΙΟ ΠΡΟΣ ΤΟ ΠΡΩΤΟ
ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ:
ΑΛΛΑΓΕΣ=0:ΣΥΓΚΡΙΣΕΙΣ=0:ΠΡΟΗΓΟΥΜΕΝΕΣ=0
Τ1=ΜΗΚΟΣ(Α()):Τ2=Τ1-1
ΑΝ Τ2<1 ΤΟΤΕ ΛΑΘΟΣ "ΘΕΛΩ ΤΟΥΛΑΧΙΣΤΟΝ ΔΥΟ ΣΤΟΙΧΕΙΑ"
ΔΙΑΜΕΣΟΥ ΕΜΦΑΝΙΣΗ_ΠΙΝΑΚΑ
ΕΚΚΙΝΗΣΗ: ' στις ετικέτες μπορούμε να βάλουμε δίπλα μόνο σημειώσεις.
Κ=Τ2:Ι=Κ-1: ΠΡΟΗΓΟΥΜΕΝΕΣ=ΑΛΛΑΓΕΣ
10ΣΥΓΚΡΙΣΕΙΣ++
ΑΝ Α(Ι)>Α(Κ) ΤΟΤΕ ΑΛΛΑΞΕ Α(Ι), Α(Κ): ΑΛΛΑΓΕΣ++
Ι--:Κ--:ΑΝ Ι>=0 ΤΟΤΕ 10
ΔΙΑΜΕΣΟΥ ΕΜΦΑΝΙΣΗ_ΠΙΝΑΚΑ
ΑΝ ΠΡΟΗΓΟΥΜΕΝΕΣ<>ΑΛΛΑΓΕΣ ΤΟΤΕ ΠΡΟΣ ΕΚΚΙΝΗΣΗ
ΔΙΑΜΕΣΟΥ ΑΠΟΤΕΛΕΣΜΑΤΑ
ΕΠΙΣΤΡΟΦΗ
ΑΠΟΤΕΛΕΣΜΑΤΑ:
ΤΥΠΩΣΕ "ΑΛΛΑΓΕΣ:";ΑΛΛΑΓΕΣ
ΤΥΠΩΣΕ "ΣΥΓΚΡΙΣΕΙΣ:";ΣΥΓΚΡΙΣΕΙΣ
ΤΥΠΩΣΕ "ΠΑΤΑ ΕΝΑ ΠΛΗΚΤΡΟ": ΒΑΛΕ ΚΟΜ$: ΠΕΤΑ
ΕΠΙΣΤΡΟΦΗ
ΕΜΦΑΝΙΣΗ_ΠΙΝΑΚΑ:
ΤΥΠΩΣΕ Α()#ΓΡΑΦΗ$(" ")
ΕΠΙΣΤΡΟΦΗ
Υπάρχει και ένας τρόπος βελτιστοποίησης, όπου όμως αν παρατηρήσετε απλά λιγοστεύει τις συγκρίσεις όταν δεν έχουμε ταξινομημένο πίνακα. Δείτε στα τελευταία δυο παραδείγματα γλιτώνουμε μόνο μια σύγκριση!
ΤΑΞΙΝΟΜΗΣΗ_ΦΥΣΑΛΙΔΑΣ:
ΑΛΛΑΓΕΣ=0:ΣΥΓΚΡΙΣΕΙΣ=0:ΠΡΟΗΓΟΥΜΕΝΕΣ=0
Τ1=ΜΗΚΟΣ(Α()):Τ2=Τ1-1
ΑΝ Τ2<1 ΤΟΤΕ ΛΑΘΟΣ "ΘΕΛΩ ΤΟΥΛΑΧΙΣΤΟΝ ΔΥΟ ΣΤΟΙΧΕΙΑ"
ΔΙΑΜΕΣΟΥ ΕΜΦΑΝΙΣΗ_ΠΙΝΑΚΑ
Ν=0
ΕΚΚΙΝΗΣΗ: ' στις ετικέτες μπορούμε να βάλουμε δίπλα μόνο σημειώσεις.
Κ=Τ2:Ι=Κ-1: ΠΡΟΗΓΟΥΜΕΝΕΣ=ΑΛΛΑΓΕΣ
10ΣΥΓΚΡΙΣΕΙΣ++
ΑΝ Α(Ι)>Α(Κ) ΤΟΤΕ ΑΛΛΑΞΕ Α(Ι), Α(Κ): ΑΛΛΑΓΕΣ++
Ι--:Κ--:ΑΝ Ι>=Ν ΤΟΤΕ 10
ΔΙΑΜΕΣΟΥ ΕΜΦΑΝΙΣΗ_ΠΙΝΑΚΑ
ΑΝ ΠΡΟΗΓΟΥΜΕΝΕΣ<>ΑΛΛΑΓΕΣ ΤΟΤΕ Ν++: ΠΡΟΣ ΕΚΚΙΝΗΣΗ
ΔΙΑΜΕΣΟΥ ΑΠΟΤΕΛΕΣΜΑΤΑ
ΕΠΙΣΤΡΟΦΗ
Στη Ρουτίνα βάζουμε μια Ν, που γίνεται Τ1+1 γιατί με το που θα μπούμε στην εξωτερική ΕΠΑΝΕΛΑΒΕ θα κάνουμε το Ν-- και στην εσωτερική ΕΠΑΝΕΛΑΒΕ στην ΟΣΟ βάζουμε το Ι<Ν από το Ι<Τ1
ΤΟΠΙΚΕΣ ΑΛΛΑΓΕΣ=0, ΣΥΓΚΡΙΣΕΙΣ=0, ΠΡΟΗΓΟΥΜΕΝΕΣ=0
ΤΟΠΙΚΕΣ Τ1=ΜΗΚΟΣ(Α()), Τ2=Τ1-1, Κ, Ι, Ν
ΑΝ Τ2<1 ΤΟΤΕ ΛΑΘΟΣ "ΘΕΛΩ ΤΟΥΛΑΧΙΣΤΟΝ ΔΥΟ ΣΤΟΙΧΕΙΑ"
ΔΙΑΜΕΣΟΥ ΕΜΦΑΝΙΣΗ_ΠΙΝΑΚΑ
Ν=Τ1+1
ΕΠΑΝΕΛΑΒΕ
Ν--
Κ=0:Ι=Κ+1: ΠΡΟΗΓΟΥΜΕΝΕΣ=ΑΛΛΑΓΕΣ
ΕΠΑΝΕΛΑΒΕ ΣΥΓΚΡΙΣΕΙΣ++
ΑΝ Α(Ι)<Α(Κ) ΤΟΤΕ ΑΛΛΑΞΕ Α(Ι), Α(Κ): ΑΛΛΑΓΕΣ++
Ι++:Κ++
ΟΣΟ Ι<Ν
ΔΙΑΜΕΣΟΥ ΕΜΦΑΝΙΣΗ_ΠΙΝΑΚΑ
ΟΣΟ ΠΡΟΗΓΟΥΜΕΝΕΣ<>ΑΛΛΑΓΕΣ
ΔΙΑΜΕΣΟΥ ΑΠΟΤΕΛΕΣΜΑΤΑ
ΤΕΛΟΣ ΡΟΥΤΙΝΑΣ
Για να εξάγουμε τα στοιχεία και να τα βάλουμε σε κάποιο blog ή έγγραφο:
ΤΥΠΩΣΕ "ΑΛΛΑΓΕΣ:";ΑΛΛΑΓΕΣ
ΤΥΠΩΣΕ "ΣΥΓΚΡΙΣΕΙΣ:";ΣΥΓΚΡΙΣΕΙΣ
εγ$="ΑΛΛΑΓΕΣ:"+ΑΛΛΑΓΕΣ+{
}+"ΣΥΓΚΡΙΣΕΙΣ:"+ΣΥΓΚΡΙΣΕΙΣ+{
}
ΤΥΠΩΣΕ "ΠΑΤΑ ΕΝΑ ΠΛΗΚΤΡΟ": ΒΑΛΕ ΚΟΜ$: ΠΕΤΑ
ΕΠΙΣΤΡΟΦΗ
ΕΜΦΑΝΙΣΗ_ΠΙΝΑΚΑ:
εγ$=Α()#ΓΡΑΦΗ$(" ")+{
}
ΤΥΠΩΣΕ Α()#ΓΡΑΦΗ$(" ")
ΕΠΙΣΤΡΟΦΗ
Συστημα "notepad", κατ$+"bubble.txt"
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου
You can feel free to write any suggestion, or idea on the subject.