Σάββατο, 11 Φεβρουαρίου 2017

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

Εδώ έχω μια μικρή εφαρμογή που δείχνει την Γρήγορη ταξινόμηση ως ρουτίνα (και βοηθητικές) στην Μ2000 (οι ρουτίνες έχουν αναδρομή). Είναι σαν εφαρμογή, εμφανίζει τίτλο, αποτελέσματα, περιμένει ένα πλήκτρο και πάει στο επόμενο αποτέλεσμα.
Είναι γραμμένο με δυνατότητες από την 8.2 έκδοση, αν 15, οπότε καλό είναι όποιος έχει κατεβάσει παλαιότερη έκδοση να την αναβαθμίσει. Φαίνεται και η χρήση της λάμδα ως μετρητής, και η χρήση του χειριστή << για αλλαγή κάθε στοιχείου στο πίνακα στην εντολή Πίνακας.

Υπάρχει και αλλο πρόγραμμα με χρήση της γρήγορη ταξινόμηση αλλά σε στοιχεία του σωρού, με μετακινήσεις από και προς την κορυφή, και εκεί το πρόγραμμα βγάζει σειρές υποσυνόλων σε σύνολα, και ταξινομεί κάθε υποσύνολο: Δες εδώ

Υπάρχουν εντολές ταξινόμησης σε αντικείμενα τύπου Έγγραφο (Document) )και τύπου Κατάσταση (Inventory), αλλά εδώ βλέπουμε την μορφή της με εντολές της Μ2000.
Επειδή οι πίνακες μπορούν να έχουν πίνακες ή άλλα αντικείμενα, η εντολή Άλλαξε (Swap), λειτουργεί στο βάθος, και μεταφέρει 12byte, που μπορεί να έχουν την τιμή και το είδος, ή να έχουν δείκτη σε αντικείμενο. Γενικά η Μ2000 δεν αφήνει να διαβάσουμε δείκτη σε αντικείμενο, ούτε να βάλουμε δική μας τιμή στο δείκτη. Γνωρίζει τι είναι αντικείμενο, επειδή δημιουργεί αντικείμενα και ασχολείται με τους έτοιμους δείκτες όταν φτιάχνουμε νέα αντικείμενα. Εκτός από ειδική περίπτωση (δες Κατάσταση) όλα τα άλλα αντικείμενα έχουν αναλογία ένας δείκτης- ένα αντικείμενο. Οι αναφορές σε αυτά τα αντικείμενα είναι έμμεσος δείκτης στο πραγματικό δείκτη. Στις καταστάσεις μπορούμε να κάνουμε κυκλική αναφορά, δηλαδή να έχει η κατάσταση αναφορά στον εαυτό της, ή χειρότερα, αναφορά σε άλλη όπου η άλλη να έχει αναφορά στην πρώτη. Η Μ2000 έχει τρόπο να βρίσκει αυτές τις κυκλικές αναφορές και να τις καταστρέφει όταν πρέπει!

\\ γρήγορη ταξινόμηση
\\  φτιάχνουμε την οθόνη να δείχνει 40 γραμμές με 60 χαρακτήρες
Φόρμα 60,40
Οθόνη 5 : Πένα 14
\\ με το 2 βάζουμε στο κέντρο της γραμμής την αναφορά μας!


Διπλά  \\ διπλού ύψους και πλάτους γράμματα
Αναφορά 2,"Γρήγορη Ταξινόμηση με χρήση Ρουτινών με Αναδρομή"
Κανονικά
Οθόνη 1,2: Πένα 11 \\ το 2 σημαίνει ότι χωρίζει η οθόνη από την τρίτη γραμμή


\\ Δυο γεννήτριες αριθμών - φτιαγμένες σε συναρτήσεις τύπου λάμδα
\\ αυτές μπορούν να έχουν δικές τους μεταβλητές που δεν σβήνουν μετά την κλήση
\\ αυτό μας βολεύει για να φτιάχνουμε μετρητές.


Counter =Λάμδα x=1 ->{ =x : x++}
CounterRev =Λάμδα x=30 ->{ =x : x--}


\\
\\ φτιάχνουμε δυο πίνακες, και γεμίζουμε τον ένα


Βάση 0 \\ εξ ορισμού είναι 0 αλλά δεν μας πειράζει να το ορίσουμε ξανά


\\ οι πίνακες κρατούν την βάση 0 ή 1 μέχρι να χαθούν.
\\ ο χειριστής << δηλώνει εδώ "εκτέλεσε την συνάρτηση δεξιά για κάθε στοιχείο"


Πίνακας arr(30)<<CounterRev(), old()


\\ αν θέλουμε σκιάζουμε την παρακάτω με \\
\\ η παρακάτω εντολή σημαίνει βάλε από το 0 και πάνω τα στοιχεία μετά το =
\\ άλλαξε το (0) με (10) για να πάβε από το 10 και μετά...
arr(0)=4,2,3,102,23,21,1,54,26,9


\\ αντιγραφή του πίνακα για να μπορούμε να δείξουμε τον παλιό με τον κανούριο
old()=arr()


\\ ξεκινάμε από τη βάση
γρήγορη_ταξινόμηση(&arr(), 0, 29)
Διαμέσου τύπωσε_πίνακα
περίμενε_πλήκτρο()


\\ όλα τα στοιχεία ίδια
Πίνακας arr(30)=1, old() : old()=arr() : γρήγορη_ταξινόμηση(&arr(), 0, 29)
Διαμέσου τύπωσε_πίνακα
περίμενε_πλήκτρο()


\\ ταξινομημένος
Πίνακας arr(30)<<counter(), old() : old()=arr() : γρήγορη_ταξινόμηση(&arr(), 0, 29)
Διαμέσου τύπωσε_πίνακα
περίμενε_πλήκτρο()
\\ κρατάμε αντίγραφο της λάμδα σε μια μεταβλητή ως νέα λάμδα συνάρτηση
counterrev2=counterrev


\\ δοκιμάζουμε σε νέους πίνακες με βάση 1 (από 1 έως 30 αντί από 0 έως 29)
\\ η γρήγορη ταξινόμηση δεν αλλάζει, γιατί δίνουμε πάντα από την αρχή το διάστημα που θα λειτουργήσει


Βάση 1 : Πίνακας arr1(30)<<counterrev(), old1() : old1()=arr1() : Βάση 0 \\ να μη τον ξεχνάμε!
γρήγορη_ταξινόμηση(&arr1(), 1, 30)
Διαμέσου τύπωσε_πίνακα1
περίμενε_πλήκτρο()


Βάση 1 : Πίνακας arr1(30)<<counterrev2()*4, old1()
για i=2 έως 30 ανα 2 : arr1(i)-! : arr1(i)+=4 : επομενο i
old1()=arr1() : Βάση 0 \\ να μη τον ξεχνάμε!
γρήγορη_ταξινόμηση(&arr1(), 1, 30)
Διαμέσου τύπωσε_πίνακα1
περίμενε_πλήκτρο()


Τέλος
τύπωσε_πίνακα:
      \\ Απλή ρουτίνα, δεν έχουμε κάτι να περάσουμε
      \\ ούτε να δημιουργήσουμε τοπικά όπως κάνουμε στις ρουτίνες.
      \\ η Διαμέσου είναι η Gosub. Και οι ρουτίνες μπορούν να κληθούν με Διαμέσου
      \\ και πρέπει αν το όνομα της ρουτίνας είναι ίδιο όνομα πίνακα στο τμήμα.   
      Για i=0 Έως 29
            Τύπωσε μορφη$("{0:-8}={1::4}  {2::-4}",μορφη$("arr({0})", i),arr(i), old(i))
      Επόμενο i
Επιστροφή
τύπωσε_πίνακα1:
      Για i=1 Έως 30
            Τύπωσε μορφη$("{0:-9}={1::4}  {2::-4}",μορφη$("arr1({0})",i), arr1(i), old1(i))
      Επόμενο i
Επιστροφή
Ρουτίνα περίμενε_πλήκτρο()
      Διπλά
      Αναφορά 2, "Πάτησε ένα πλήκτρο"
      Κανονικά
      Τοπική a$=Κομ$
Τέλος Ρουτίνας
\\ τα ονόματα των ρουτινών αν είναι ελληνικά τότε πρέπει να έχουν και την εντολή ρουτίνα με ελληνικά
\\ αν είναι στα αγγλικά πρέπει να έχουν την εντολή Sub και στο τέλος End Sub.
\\ με & σημαίνει με αναφορά. Εδώ το Α() δείχνει ότι το arr()
Ρουτίνα γρήγορη_ταξινόμηση(&A())
      \\ Αυτή χρειάστηκε μόνο για να δημιουργήσει την Α()
      \\ που είναι αναφορά της arr()
      \\ μέχρι το τέλος αυτής της ρουτίνας, θα υπάρχει και αυτή η αναφορά
      \\ τα δυο νούμερα που έχουμε περάσει τα αφήνουμε να τα διαβάσει
      \\ η γρήγορη()
      Αναλυτής
      γρήγορη()
      Οθόνη : Τύπωσε Φόρτος \\ μετράμε τον φόρτο ως  χρόνος εκτέλεσης
Τέλος Ρουτίνας
Ρουτίνα ταξινόμησε(p,r)
      Τοπική x = A(r), i = p-1
      Για j=p Έως r-1
            Αν A(j) <= x Τότε i = i+1 : Άλλαξε A(i),A(j)
      Επόμενο j
      Άλλαξε A(i+1),A(r)
      Βάλε i+1
      \\ οι ρουτίνες είναι μέρη τμήματος, και χειρίζονται τον ίδιο σωρό τιμών\
      \\ έτσι μπορούν να διαβάζουν από αυτόν αλλά και να βάζουν τιμές σε αυτόν
Τέλος Ρουτίνας
Ρουτίνα γρήγορη(p, r)
      Αν p >= r Τότε Έξοδος Ρουτίνας
      ταξινόμησε(p, r) : Διάβασε τοπικά q
      γρήγορη(p, q - 1)
      γρήγορη(q + 1, r)
Τέλος Ρουτίνας



Τέλος εδώ είναι η QuickSort στα αγγλικά και χωρίς τη χρήση ρουτινών. Η κλήση της quicksort γίνεται με την Call Local (Κλήση τοπικά) για να συμβαίνει ότι και με τις υπορουτίνες, να εκτελούνται ως μέρη του τμήματος, άρα να βλέπουν την partition. Διαφορετικά θα έπρεπε να κάνουμε Global την partition (Function Global partition { ... }) και να αφαιρέσουμε το Local στο Call (κλήση). Πιο κάτω είναι η άλλη λύση με τη χρήση αναδρομής σε συνάρτηση ομάδας (Group)

Base 0
\\ Quick Sort using Call Local
Function partition {
         Read &A(), p, r
         x = A(r)
         i = p-1
         For j=p to r-1 {
             If A(j) <= x Then {
                       i = i+1
                    Swap A(i),A(j)
                 }
          }
          Swap A(i+1),A(r)
         = i+1
      }
Function quicksort {
     Read New &A(), p, r
     If p < r Then {
       q = partition(&A(), p, r)
       Call Local quicksort(&A(), p, q - 1)
       Call Local quicksort(&A(), q + 1, r)
    }
}


Dim arr(10), old()
arr(0)=23,21,1,4,2,3,102,54,26,9
old()=arr()
Call Local quicksort(&arr(), 0, 9)
For i=0 to 9
      Print arr(i), old(i)
Next i


Εδώ έχουμε ομάδα (Group) με συναρτήσεις. Οι συναρτήσεις σε μια ομάδα βλέπουν τις άλλες συναρτήσεις της ομάδας (και τυχόν δικές τους), εφόσον ορίζονται στο ίδιο επίπεδο, αλλά και συναρτήσεις άλλων υποομάδων στην ομάδα. Την συνάρτηση partition την έχουμε ιδιωτική (private), δηλαδή δεν μπορεί να κληθεί απ΄έξω!

Base 0
\\ Using a Group
Group Quick {
Private:
      Function partition {
               Read &A(), p, r
               x = A(r)
               i = p-1
               For j=p to r-1 {
                   If A(j) <= x Then {
                             i = i+1
                          Swap A(i),A(j)
                       }
                }
                Swap A(i+1),A(r)
               = i+1
            }
Public:
      Function quicksort {
           Read &A(), p, r
           If p < r Then {
             q = .partition(&A(), p, r)
             Call .quicksort(&A(), p, q - 1)
             Call .quicksort(&A(), q + 1, r)
          }
      }
}
Dim arr(10), old()
arr(0)=23,21,1,4,2,3,102,54,26,9
old()=arr()
Call Quick.quicksort(&arr(), 0, 9)
For i=0 to 9
      Print arr(i), old(i)
Next i