Γρήγορη Ταξινόμηση με Αντικείμενο και Γεγονότα

Το παράδειγμα θέλει την αναθεώρηση 44 που χρησιμοποιεί σωστά την Insertion Sort στις καταστάσεις τύπου Ουρά (μόνο για το τελευταίο μέρος του)

Το πρόγραμμα φτιάχνει μια κλάση που δεν γνωρίζει τι θα ταξινομήσει. Αυτή η κλάση φτιάχνει ένα αντικείμενο που έχει τρια γεγονότα. Συνδέουμε στα γεγονότα τις συναρτήσεις που θα καλούνται όταν "συμβαίνουν". Καλούμε την ταξινόμηση δηλώνοντας τον αριθμό στοιχείων που θα ταξινομήσουμε, εδώ 10.
Ο αλγόριθμος δουλεύει για όλα τα στοιχεία αλλά όταν χρειάζεται να συγκρίνει ή να αλλάξει στοιχεία τότε καλεί τα γεγονότα αντίστοιχα. Αν δεν βάλουμε τις συναρτήσεις στα γεγονότα, θα τερματίσει χωρίς να έχει κάνει κάποια σύγκριση και κάποια αλλαγή, επειδή τα γεγονότα καλούνται χωρίς πρόβλημα ακόμα και αν δεν υπάρχει κάτι για να τα εξυπηρετήσει.
Πρέπει να δηλώσουμε τι είδος παραμέτρων θα έχει κάθε συνάρτηση που καλεί το γεγονός (μπορούμε να βάλουμε παραπάνω από μια συνάρτηση). Δείτε ότι σε ένα γεγονός δηλώνουμε μια μ που θα περνάει με αναφορά. Τη θέλουμε για να μας επιστρέφει τιμή. Τα γράμματα των παραμέτρων στον ορισμό του Γεγονότος δεν έχουν σημασία, απλά διαβάζει ο διερμηνευτής αν θα είναι αριθμοί, γράμματα (αλφαριθμητικά) και αν θα είναι με αναφορά ή όχι. Στη κλήση του γεγονότος, πρέπει να δώσουμε ότι ακριβώς ζητάει, ακόμα και αν δεν έχουμε δώσει συνάρτηση, ή αν τα έχουμε ανενεργά. Αν δώσουμε κάτι λιγότερο, ή περισσότερο, ή διαφορετικό πχ γράμματα αντί για αριθμό, ή εκεί που ζητάει αναφορά δεν δώσουμε αναφορά, τότε βγαίνει λάθος.

Οι συναρτήσεις που δίνουμε στα γεγονότα, μπορεί να είναι κανονικές ή όπως εδώ να είναι με αυτό που λέμε "κλήση προς τα πίσω". Δηλαδή αντί να περάσουμε τη συνάρτηση ως έχει περνάμε τον κώδικά της σαν να είναι κώδικας του τμήματος όπου ορίστηκε, παράγοντας μια άλλη συνάρτηση με όνομα το όνομα του τμήματος. Με αυτόν τον τρόπο η συνάρτηση έχει θέαση των μεταβλητών του τμήματος. Το θέλουμε αυτό για να έχουμε πρόσβαση στη κλήση των γεγονότων του πίνακα πινακ$() με τα ονόματα των πόλεων.

Αν δεν είχαμε την δυνατότητα να περνάμε συναρτήσεις με κλήση "προς τα πίσω", τότε θα έπρεπε να περνάμε εκτός από τις συναρτήσεις και το πίνακα με αναφορά κάθε φορά που θα καλούσαμε την γρήγορη ταξινόμηση. Το μειονέκτημα με το αντικείμενο ως έχει, είναι ότι όταν πάρει τις συναρτήσεις εξυπηρέτησης των γεγονότων τότε "δένει" με το πίνακα που σε αυτές χρησιμοποιούνται. Μπορεί να είναι οτιδήποτε, γιατί το αντικείμενο δεν νοιάζεται καν για το τι περιέχουν αυτές. Μπορούμε να φτιάξουμε ένα δεύτερο με αντιγραφή του πρώτου ή με δημιουγία με την κλάση (η κλάση είναι συναρτηση που γυρίζει αντικείμενο τύπου ομάδα). Σε αυτό το δεύτερο μπορούμε να δώσουμε άλλες συναρτήσεις.

Γενικά όταν δίνουμε συναρτήσεις για χρήση με την κλήση προς τα πίσω (callback), οι συναρτήσεις είναι κάπως δεμένες στο χώρο που ορίζονται. Αν επιστρέψουμε το αντικείμενο Ταξινόμησε από το τμήμα που ορίσαμε τις συναρτήσεις, αυτές θα υπάρχουν στα γεγονότα σε αυτό το αντικείμενο, αλλά δεν θα υπάρχει ο πίνακας και αυτό θα κάνει τις συναρτήσεις να μην δουλέψουν. Αν όμως ο πίνακας είχε οριστεί γενικός πριν καλέσουμε το τμήμα όπου ορίσαμε τις συναρτήσεις που τον χρησιμοποιούν, τότε θα μπορέσουν να δουλέψουν. Η αλλη περίπτωση είναι να έχουμε τον πίνακα στο ίδιο το αντικείμενο, αλλά τότε τα γεγονότα δεν χρειάζονται, βάζουμε τις συναρτήσεις στο αντικείμενο και τις καλούμε από εκεί.

Όπως θα δείτε οι συναρτήσεις καλούνται σαν τμήματα, δηλαδή δεν επιστρέφουν τιμή. Αυτό είναι όμοιο με την κλήση με την εντολή Κάλεσε. Η διαφορά με την Κάλεσε Γεγονός είναι ότι στη δεύτερη μετράει επακριβώς τι και πόσα ορίσματα στέλνουμε, βάσει του τι ακριβώς ζητάει το γεγονός. Η επιστροφή τιμής για τη σύγκριση γίνεται με πέρασμα μεταβλητής με αναφορά, οπότε η αλλαγή διαβάζεται στην επιστροφή

Δείτε επίσης ότι στο τμήμα ΓρήγορηΤαξινόμηση έχουμε κλήσεις με την Κάλεσε Τοπικά. Αυτή η κλήση κάνει τη συνάρτηση που καλεί να είναι και αυτή ως να καλέστηκε με όνομα το όνομα του τμήματος, και έτσι έχει θέαση σε ότι έχει το τμήμα. Έτσι μέσα από την συνάρτηση ΤμήμαΣτοιχείων καλούμε την ΓρήγορηΤαξινόμηση. Κανονικά οι συναρτήσεις βλέπουν ότι έχουν δικό τους ή ότι είναι γενικό, ή ότι είναι του αντικειμένου που ανήκουν (της ομάδας). Εδώ τα ΓρήγορηΤαξινόμηση και ΤμήμαΣτοιχείων, δεν εμπίπτουν σε αυτά τα τρία, δεν είναι γενικές συναρτήσεις, δεν ανήκει κάποια στην άλλη, και δεν ανοίκουν σε αντικείμενο (ανοίκουν σε τμήμα που ανοίκει σε αντικείμενο).
Σε άλλες γλώσσες προγραμματισμού υπάρχει μια πιο οριζόντια θέαση, έτσι ουσιαστικά ότι είναι εντός βλέπει και ότι είναι εκτός αυτού. Εδώ για να το πετύχουμε αυτό πρέπει να καλέσουμε με συγκεκριμένο τρόπο, και μόνο για το τμήμα που περιέχονται, και όχι πιο πάνω. Έτσι όταν καλούμε αυτό:
Κάλεσε Τοπικά ΓρήγορηΤαξινόμηση(0, .πόσα-1)
Η ΓρήγορηΤαξινόμηση() είναι τοπική συνάρτηση, το .πόσα είναι μέλος του αντικειμένου και είναι θεατό μόνο στα μέλη του αντικειμένου (άρα δεν θα είναι θεατά στις συναρτήσεις του τμήματος ΓρήγορηΤαξινόμηση, αν τις χρησιμοποιούσαμε αλλιώς), όπως και τα άλλα μέλη, τα γεγονότα ΣύγκρινεΣτοιχείο, ΆλλαξεΣτοιχείο και ΘέσεΈνα. Θέλουμε όμως να είναι θεατά ακόμα και αν έχουμε αναδρομική κλήση (δείτε ότι η συνάρτηση ΓρήγορηΤαξινόμηση καλεί τον εαυτό της ανάλογα με τις συνθήκες). Κάθε φορά που καλούμε με την Κάλεσε Τοπικά ο διερμηνευτής βρίσκει την συνάρτηση και πριν την εκτελέσει αλλάζει το όνομα στο όνομα του τμήματος που τρέχει. Εδώ βέβαια βλέπουμε ίδια ονόματα, αλλά στην ουσία είναι διαφορετικά γραμμένα, έχουν προθέματα που δεν βλέπουμε κατά την εκτέλεση.

Μια μικρή εξήγηση για την Γρήγορη Ταξινόμηση. Σε κάθε κλήση της εσωτερικής ΓρήγορηΤαξινόμηση() αν έχουμε μόνο δυο στοιχεία κάνουμε μια μικρή ταξινόμηση αν χρειαστεί και διακόπτουμε (επιστρέφει η συνάρτηση μετά από εκεί που κλήθηκε). Για να γίνει σύγκριση απαιτείται να έχουμε βάλει ένα σταθερό ή Pivot βάσει του οποίου θα γίνει όλη η επεξεργασία. Αν έχουμε πάνω από δυο στοιχεία τότε βρίσκουμε το μέσο και και αυτό το θέτουμε ως βάση (pivot). Αλλά δείτε μια διαφορά, δεν κρατάμε δείκτη στη βάση, αλλά βάζουμε το προς έλεγχο στοιχείο. Μέσα στο αντικείμενο δεν ξέρουμε ακριβώς τι είναι αυτό, παρά μόνο τον αριθμό του. Έτσι η Κάλεσε Γεγονός .ΘέσεΈνα (λ+π) δια 2 θα καλέσει το μέλος του αντικειμένου ΘέσεΈνα και θα του δώσει τον αριθμό, που εδώ είναι το μέσον των π και λ.
Αμέσως μετά μας ενδιαφέρουν δυο μεταβλητές η Μ1 και Μ2. Αυτές θα ξεκινήσουν από τα άκρα, τα π και λ, και αμέσως καλούμε την ΤμήμαΣτοιχείων(). Ο κώδικας γράφτηκε στη συνάρτηση αυτή περισσότερο για να φαίνεται πιο οργανωμένος ο κώδικας. Θα μπορούσε κανείς να ρίξει άμεσα το κώδικα στη θέση της κλήσης. Στη συνάρτηση, λοιπόν, αυτή θα γίνει η μετακίνηση στοιχείων. Δείτε πώς. Πρώτα ανεβάζουμε την Μ1 μέχρι να βρούμε κάτι που να μην είναι μικρότερο (ή μεγαλύτερο αν έχουμε δώσει "ΦΘΙΝΟΥΣΑ"), μετά μπαίνουμε σε μια επανάληψη για πάντα! Στην ουσία όταν συμβεί το  Μ1>Μ2 τότε θα βγούμε από την επανάληψη. Αυτό που μας ενδιαφέρει είναι να κοιτάμε που έχουμε μεγαλύτερο (ή μικρότερο αν έχουμε δώσει "ΦΘΙΝΟΥΣΑ") από το αποθηκευμένο για σύγκριση το οποίο λέμε Βάση (Pivot), και να το σημειώνουμε στο Μ2. Έτσι ενώ ξεκινάμε από τα Μ1=π και Μ2=λ θα φτάσουμε σε κάποια νέα Μ1 και Μ2 όπου θα ισχύει αυτό Μ1νέο>=Μ1 και Μ2νέο<=Μ2.  Μετά αρχίζουμε και συγκρίνουμε τα Μ1 και Μ2 αν ισχύει το Μ1<=Μ2 και αν ναι τότε κάνουμε αλλαγή των στοιχείων, και αυξάνουμε το Μ1 και μειώνουμε το Μ2. Αμέσως μετά κοιτάμε αν ισχύει το Μ1>Μ2 για να διακόψουμε το Επανέλαβε {} πάντα. Αν όχι συνεχίζουμε με το ψάξιμο του νέου Μ1, πάντα με σκοπό να μειώσουμε την απόσταση των Μ1 και Μ2 και όταν χρειάζεται να κάνουμε την αλλαγή τιμών με το γεγονός ΆλλαξεΣτοιχείο.
Θα περίμενε κανείς ότι αρκεί αυτή η "ταξινόμηση" στη ΤμήμαΣτοιχείων(), αλλα δεν αρκεί. Αμέσως μετά την επιστροφή καλούμε με αναδρομή δυο υποπεριοχές για ΓρήγορηΤαξινόμηση(). Θυμηθείτε εδώ ότι το Μ1>Μ2 ισχύει, αφού με αυτό βγήκαμε από την επανάληψη "Επανέλαβε {} πάντα". Η μια περιοχή ορίζεται από τα π και Μ2 και η άλλη από το Μ1 και λ. Το σίγουρο είναι ότι όταν φτάσουμε σε αυτό το σημείο κανένα στοιχείο από την μια περιοχή δεν ανοίκει ή όφειλε να βρίσκεται στην άλλη περιοχή, δηλαδή έχει επιτευχθεί ο διαχωρισμός σε δυο περιοχές. Ομοίως τώρα κάθε περιοχή θα σπάσει σε άλλες δυο και συνεχίζουμε μέχρι να φτάσουμε στο μέγιστο δύο στοιχεία (το ένα στοιχείο δεν ταξινομείται). Αυτό που έχουμε κρατήσει ως βάση έχει ήδη ταξινομηθεί στη σωστή θέση!

Στο τέλος του παραδείγματος χρησιμοποιούμε το αντικείμενο Κατάσταση και ταξινομούμε κλειδιά με την εσωτερική QuickSort (γρήγορη ταξινόμηση), η οποία δεν διαφέρει από αυτήν, παρά μόνο σε ένα στοιχείο που δεν έβαλα εδώ, και είναι αυτό που ονομάζω Extended QuickSort, και σώνει σε περίπτωση που έχουμε ίδια στοιχεία συνεχόμενα. Δεν το έβαλα για να μην δυσκολέψει ο κώδικας. Υπάρχει όμως εδώ σε Visual Basic 6

Δυο αλλαγές έγιναν, που δεν αλλάζουν την ουσία του κώδικα. Οι ορισμοί συναρτήσεων πήραν στο όνομα το () δηλαδή από Συνάρτηση ΓρήγορηΤαξινόμηση έγινε Συνάρτηση ΓρήγορηΤαξινόμηση(). Ο νεότερος διερμηνευτής το δέχεται και έτσι (δέχονταν τη λίστα παραμέτρων χωριστά, με διάστημα αλλά τροποποιήθηκε ο κώδικας και δέχεται τη λίστα και στο όνομα. Αυτό γίνεται και στα τμήματα αν θέλουμε, απλά στα τμήματα δεν μας βολεύει με την αναζήτηση με τα F2 και F3, δηλαδή κάνουμε κλικ το όνομα ενός τμήματος και με πατώντας το F2 ψάχνουμε προς τα πίσω, οπότε μας πάει στον ορισμό, και με ένα από τα F6, F7, F8 βάζουμε σελιδοδείκτη για να ξαναπάμε σε αυτό το σημείο). 
Η δεύτερη αλλαγή έγινε στο κώδικα της ΤμήμαΣτοιχείων. Μπήκε μέσα στην Επανέλαβε το πρώτο μέρος με την Κάλεσε Γεγονός και την Ενώ, και άλλαξε η Επανέλαβε { } Πάντα σε Επανέλαβε { } Μέχρι και έτσι γίνεται η έξοδος από τον έλεγχο τη συνθήκης έξω από το μπλοκ.

\\ Πρόγραμμα Γρήγορη Ταξινόμηση αναθ. 2

Άδειασε
Καθαρό
Κλάση ΑντικείμενοΤαξινόμησης {
      Γεγονός ΣύγκρινεΣτοιχείο {Διάβασε Νέο κ, &μ}
      Γεγονός ΆλλαξεΣτοιχείο {Διάβασε Νέο Μ1, κ}
      Γεγονός ΘέσεΈνα {Διάβασε Νέο Μ1}
      πόσα=0
      Τμήμα ΓρήγορηΤαξινόμηση {
            \\ τα Μ και Ν είναι κοινά επειδή καλούμε τοπικά!
            Συνάρτηση ΓρήγορηΤαξινόμηση() {
                   Διάβασε Νέο π,λ
                        Αν λ-π=1 Τότε {
                              Τοπική ρ
                              Κάλεσε Γεγονός .ΘέσεΈνα λ
                              Κάλεσε Γεγονός .ΣύγκρινεΣτοιχείο π, &ρ
                              Αν ρ=Ν Τότε Κάλεσε Γεγονός .ΆλλαξεΣτοιχείο π, λ
                              Διεκοψε  ' βγαίνει και από την συνάρτηση
                        }
                        Κάλεσε Γεγονός .ΘέσεΈνα (λ+π) δια 2
                        Τοπική Μ1=π, Μ2=λ
                        Κάλεσε Τοπικά ΤμήμαΣτοιχείων()
                        Αν π<Μ2 Τότε Κάλεσε Τοπικά ΓρήγορηΤαξινόμηση(π, Μ2)
                        Αν Μ1<λ Τότε Κάλεσε Τοπικά ΓρήγορηΤαξινόμηση(Μ1, λ)
            }
            Συνάρτηση ΤμήμαΣτοιχείων() {
                        Τοπική ρ
                          Επανέλαβε {
                              Κάλεσε Γεγονός .ΣύγκρινεΣτοιχείο Μ1, &ρ
                              Ενώ ρ=Μ {
                                    Μ1++
                                    Κάλεσε Γεγονός .ΣύγκρινεΣτοιχείο Μ1, &ρ
                              }
                              Κάλεσε Γεγονός .ΣύγκρινεΣτοιχείο Μ2, &ρ
                              Ενώ ρ=Ν {
                                    Μ2--
                                    Κάλεσε Γεγονός .ΣύγκρινεΣτοιχείο Μ2, &ρ
                              }
                              Αν Μ1<=Μ2 Τότε {
                                    Κάλεσε Γεγονός .ΆλλαξεΣτοιχείο Μ1, Μ2
                                    Μ1++
                                    Μ2--
                              }
                       } Μέχρι Μ1>Μ2
            }
            Τρόπος$="ΑΥΞΟΥΣΑ"
            Διάβασε ? Τρόπος$
            Τρόπος$=Κεφ$(Τρόπος$)
            Αν Τρόπος$="ΑΥΞΟΥΣΑ" Τότε {
                  Ν=1
            } Αλλιώς.Αν Τρόπος$="ΦΘΙΝΟΥΣΑ" Τότε {
                  Ν=-1
            } Αλλιώς {
                  Λάθος "Άγνωστη Επιλογή"
            }
            Μ=-Ν
            Αν .πόσα>1 Τότε Κάλεσε Τοπικά ΓρήγορηΤαξινόμηση(0,.πόσα-1)
      }
}
Φόρμα 80,50
Πίνακας πινακ$(10), παλιός$()
\\ Φτιάχνουμε το αντικείμενο Ταξινόμησε
Ταξινόμησε=ΑντικείμενοΤαξινόμησης()
\\ Οι συναρτήσεις θα κληθούν με Κάλεσε Τοπικά
\\ ως κλήσεις προς τα πίσω, στο τμήμα
\\ έτσι θα έχουν θέαση στους πίνακες.
Ένα$=""
Συνάρτηση ΘέσεΈνα() {
        Διάβασε Νέο κ
        Ένα$=πινακ$(κ)
}
Συνάρτηση ΣυγκρινεΣτοιχεία() {
        Διάβασε Νέο κ , &μ
        μ=Τάξη(πινακ$(κ), Ενα$) ' Εδώ μπορεί να χρησιμοποιηθεί και η Σύγκρινε()
}
Συνάρτηση ΆλλαξεΣτοιχεία() {
        Διάβασε Νέο Μ1, κ
        Αν Μ1<>Κ Τότε Άλλαξε πινακ$(Μ1), πινακ$(κ)
}
\\ Τώρα τροφοδοτούμε το αντικείμενο με τις συναρτήσεις
Για Ταξινόμησε {
      Γεγονός .ΘέσεΈνα Νέο Οκν$(&ΘέσεΈνα())
      Γεγονός .ΣύγκρινεΣτοιχείο Νέο Οκν$(&ΣυγκρινεΣτοιχεία())
      Γεγονός .ΆλλαξεΣτοιχείο Νέο Οκν$(&ΆλλαξεΣτοιχεία())
      .πόσα=10
}
πινακ$(0)="Πρέβεζα","Πάτρα","Θάσος","Βόλος","Κέρκυρα" ,"Αθήνα" ,"Καρδίτσα","Καβάλα","Κάρπαθος","Κάρυστος"
παλιός$()=πινακ$()
Αναλυτής
      Ταξινόμησε.ΓρήγορηΤαξινόμηση ' "ΦΘΙΝΟΥΣΑ"
Τύπωσε Γραφή$(Φόρτος,"0")
     Αναλυτής
           Ταξινόμησε.ΓρήγορηΤαξινόμηση
    Τύπωσε Γραφή$(Φόρτος,"0") , " χρόνος για ταξινόμηση ήδη ταξινομημένου πίνακα"
Για Μ1=0 Έως 9
      Τύπωσε πινακ$(Μ1), παλιός$(Μ1)
Επόμενο Μ1
παλιός$()=πινακ$()
Αναλυτής
      Ταξινόμησε.ΓρήγορηΤαξινόμηση "ΦΘΙΝΟΥΣΑ"
Τύπωσε Γραφή$(Φόρτος,"0")
Αναλυτής
      Ταξινόμησε.ΓρήγορηΤαξινόμηση "ΦΘΙΝΟΥΣΑ"
Τύπωσε Γραφή$(Φόρτος,"0") , " χρόνος για ταξινόμηση ήδη ταξινομημένου πίνακα"
Για Μ1=0 Έως 9
      Τύπωσε πινακ$(Μ1), παλιός$(Μ1)
Επόμενο Μ1
Πίνακας πινακ$(10)="Αθήνα"
παλιός$()=πινακ$()
Αναλυτής
      Ταξινόμησε.ΓρήγορηΤαξινόμηση "ΦΘΙΝΟΥΣΑ"
Τύπωσε Γραφή$(Φόρτος,"0") , " χρόνος για ταξινόμηση με όλα τα στοιχεία ίδια"
Για Μ1=0 Έως 9
      Τύπωσε πινακ$(Μ1), παλιός$(Μ1)
Επόμενο Μ1
\\ Το πιο γρήγορο είναι να χρησιμοποιήσουμε μια Κατάσταση
\\ η απλή κατάσταση θέλει ξεχωριστά κλειδιά, ενώ η Κατάσταση Ουρά παίρνει και όμοια κλειδιά.
Αναλυτής
Κατάσταση Πόλεις = "Πρέβεζα","Πάτρα","Θάσος","Βόλος","Κέρκυρα","Αθήνα","Καρδίτσα","Καβάλα","Κάρπαθος","Κάρυστος"
Ταξινόμηση Αύξουσα Πόλεις
Τύπωσε Γραφή$(Φόρτος,"0") , " χρόνος για ταξινόμηση σε Κατάσταση - Quick Sort"
Τύπωσε Πόλεις
\\ Η Κατάσταση τύπου Ουρά μπορεί να πάρει όμοια κλειδιά, και έχει stable ταξινόμηση με insertion sort
Αναλυτής
Κατάσταση Ουρά Πόλεις2 = "Πρέβεζα","Πάτρα","Καβάλα":="Καβάλα 1", "Θάσος","Βόλος","Κέρκυρα","Αθήνα","Καρδίτσα","Καβάλα":="Καβάλα 2", "Καβάλα":="Καβάλα 3", "Κάρπαθος","Κάρυστος"
Ταξινόμηση Αύξουσα Πόλεις2
Τύπωσε Γραφή$(Φόρτος,"0") , " χρόνος για ταξινόμηση σε Κατάσταση τύπου Ουρά - Insertion Sort - stable"
Τύπωσε Πόλεις2
Κατάσταση Πόλεις2 ' καθαρίζει την Κατάσταση
Αναλυτής
Κατάσταση Ουρά Πόλεις2 = "Πρέβεζα","Πάτρα","Καβάλα":="Καβάλα 1", "Θάσος","Βόλος","Κέρκυρα","Αθήνα","Καρδίτσα","Καβάλα":="Καβάλα 2", "Καβάλα":="Καβάλα 3", "Κάρπαθος","Κάρυστος"
Με Πόλεις2, "Stable", Ψευδής
\\ Τώρα χρησιμοποιούμε την QuickSort, αλλά δεν έχουμε πια Stable ταξινόμηση, τα όμοια κλειδιά μπορούν να αλλάξουν θέση
Ταξινόμηση Αύξουσα Πόλεις2
Τύπωσε Γραφή$(Φόρτος,"0") , " χρόνος για ταξινόμηση σε Κατάσταση τύπου Ουρά - QuickSort - όχι stable"
Τύπωσε Πόλεις2





Εικόνα από Wine (Ubuntu Studio)

Το πρόγραμμα με αγγλικές εντολές. Οι πόλεις παραμένουν γραμμένες στα Ελληνικά.

A quick description of Identifier Scope in M2000.
Modules and Functions have own scope. But if a function called as Local than means that at that moment function gain local scope of caller. So inside Module QuickSort (a member of QuickSortGroup), we use functions for local use.

Events are holders for functions and we have to declare the variables which must read. Names in the definitions of events can be anything. A &b means that this variable is passing by reference.
Events not know if a function is passing to called local or not. The Lazy$() take a reference of function and put a command to change scope to local. Here local scope is the module scope (which all program is running, and we didn't see that, all the code has to copied in a module say A, using Edit A, copy and then pressing Esc to exit editor and after that write A to run it, in M2000 console).
We want local scope in some functions for events for accessing arrays and the pivot holder. Pivot as we see is like a global here. This is not an error. Every time Pivot change used in a straight run, so can be changed after that run (old pivot not used any more).

Using scope modification we don't have to use global variables, or global functions.

Class QuckSortGroup is a constructor function for groups. Group is the user object in M2000. Groups are values types, not reference types. A special form of group is the SuperClass but here we don't use it. A SuperClass is a Group that is referenced inside a Group. Check Help Superclass from M2000 console.


Flush command needed here because when we call a module current stack for values are passing, carrying in top positions any parameter. Because we use QuickSort module with an optional parameter, if stack has any value before call we get error or if parameter is suitable for run then maybe we get undesired run. One way to not use Flush is to make calls to modules with optional parameters using ? as parameter. This means that stack get the "optional parameter" in position in stack, so reading from stack say to interpreter that "use default value for that parameter", and leave stack as before the call.
Calling Functions inside expressions always get new stack, so there is no problem if we miss the ? indicator.
So using QuickSortGroup.QuickSort ? is better if we wish to don't care about stack items before the call.
Check for the error by inserting a command Push "Ok" after Flush command.
Add in empty of parameters call QuickSortGroup.QuickSort a ? to see that is ok now
Also as last command insert a Print Letter$  (Letter$ pop a string from stack, else raise error).

Run the module A (if A is the name you give to that) with Test A to open Control Form and try step by step execution. Also clicking the left column of indicators in that form we get code, help for command, toggle view of current stack and colored code as it runs. 

\\ Program QuickSort

Flush  \\ empty stack for values
Clear
Class QuickSortGroup {
      Event CompareElements {Read New a, &b}
      Event SwapElements {Read New a, b}
      Event TakePivot {Read New a}
      many=0
      Module QuickSort {
            Function QuickSort() {
                   Read New p,k
                        If k-p=1 Then {
                              Local r
                              Call Event .TakePivot k
                              Call Event .CompareElements p, &r
                              If r=way Then Call Event .SwapElements p, k
                              Break  ' exit form Function too
                        }
                        Call Event .TakePivot (k+p) Div 2
                        Local M1=p, M2=k
                        Call Local Elements()
                        If p<M2 Then Call Local QuickSort(p, M2)
                        If M1<k Then Call Local QuickSort(M1, k)
            }
            Function Elements() {
                        Local r
                          Repeat {
                              Call Event .CompareElements M1, &r
                              While r=z {
                                    M1++
                                    Call Event .CompareElements M1, &r
                              }                          
                             Call Event .CompareElements M2, &r
                               While r=way {
                                     M2--
                                    Call Event .CompareElements M2, &r
                              }
                              If M1<=M2 Then {
                                    Call Event .SwapElements M1, M2
                                    M1++
                                    M2--
                              }
                       } Until M1>M2
            }
            Way$="ASCENDING"
            Read ? Way$
            Way$=Ucase$(Way$)
            If Way$="ASCENDING" Then {
                  way=1
            } Else.If Way$="DESCENDING" Then {
                  way=-1
            } Else {
                  Error "Invalid Parameter"
            }
            z=-way
            If .many>1 Then Call Local QuickSort(0,.many-1)
      }
}
Form 80,50
Dim Arr$(10), OldArr$()
QuickSortGroup=QuickSortGroup()
One$=""
Function TakePivot() {
        Read New x
        One$=Arr$(x)
}
Function CompareElements() {
        Read New x , &z
        z=Order(Arr$(x), One$)
}
Function SwapElements() {
        Read New M1, x
        If M1<>x Then Swap Arr$(M1), Arr$(x)
}
For QuickSortGroup {
      Event .TakePivot New Lazy$(&TakePivot())
      Event .CompareElements New Lazy$(&CompareElements())
      Event .SwapElements New Lazy$(&SwapElements())
      .many=10
}
Arr$(0)="Πρέβεζα","Πάτρα","Θάσος","Βόλος","Κέρκυρα" ,"Αθήνα" ,"Καρδίτσα","Καβάλα","Κάρπαθος","Κάρυστος"
OldArr$()=Arr$()
Profiler
      QuickSortGroup.QuickSort
Print Str$(TimeCount,"0")
     Profiler
           QuickSortGroup.QuickSort
    Print Str$(TimeCount,"0") , " Time For Sort ήδη ταξινομημένου πίνακα"
For M1=0 To 9
      Print Arr$(M1), OldArr$(M1)
Next M1
OldArr$()=Arr$()
Profiler
      QuickSortGroup.QuickSort "DESCENDING"
Print Str$(TimeCount,"0")
Profiler
      QuickSortGroup.QuickSort "DESCENDING"
Print Str$(TimeCount,"0") , " Time for sorting a sorted array"
For M1=0 To 9
      Print Arr$(M1), OldArr$(M1)
Next M1
Dim Arr$(10)="Αθήνα"
OldArr$()=Arr$()
Profiler
      QuickSortGroup.QuickSort "DESCENDING"
Print Str$(TimeCount,"0") , " Time for sorting with all items same"
For M1=0 To 9
      Print Arr$(M1), OldArr$(M1)
Next M1
Profiler
Inventory Towns = "Πρέβεζα","Πάτρα","Θάσος","Βόλος","Κέρκυρα","Αθήνα","Καρδίτσα","Καβάλα","Κάρπαθος","Κάρυστος"
Sort Ascending Towns
Print Str$(TimeCount,"0") , " Time For Sort σε Inventory - Quick Sort"
Print Towns
Profiler
Inventory Queue Towns2 = "Πρέβεζα","Πάτρα","Καβάλα":="Καβάλα 1", "Θάσος","Βόλος","Κέρκυρα","Αθήνα","Καρδίτσα","Καβάλα":="Καβάλα 2", "Καβάλα":="Καβάλα 3", "Κάρπαθος","Κάρυστος"
Sort Ascending Towns2
Print Str$(TimeCount,"0") , " Time for sorting in Inventory type Queue - Insertion Sort - stable"
Print Towns2
Inventory Towns2 ' καθαρίζει την Inventory
Profiler
Inventory Queue Towns2 = "Πρέβεζα","Πάτρα","Καβάλα":="Καβάλα 1", "Θάσος","Βόλος","Κέρκυρα","Αθήνα","Καρδίτσα","Καβάλα":="Καβάλα 2", "Καβάλα":="Καβάλα 3", "Κάρπαθος","Κάρυστος"
With Towns2, "Stable", False
Sort Ascending Towns2
Print Str$(TimeCount,"0") , " Time for sorting in Inventory type Queue - QuickSort - not stable"
Print Towns2