Ταξινόμηση των στοιχείων μονοδιάστατου πίνακα Ν στοιχείων κατά αύξουσα σειρά με τη μέθοδο «ταξινόμηση φυσαλίδας» (bubble sort)

Διδακτικοί στόχοι

Στόχος της δραστηριότητας αυτής είναι:

§ Να γνωρίσετε μια από τις μεθόδους ταξινόμησης στοιχείων ενός πίνακα, γνωστή με το όνομα ταξινόμηση φυσαλίδας (bubble sort), καθώς και την ανάλυσή της σε αλγοριθμικά βήματα.

§ Να εξασκηθείτε στη διαχείριση των στοιχείων ενός πίνακα με τη χρήση εμφωλευμένων εντολών επανάληψης.

Ζητούμενο

Να μελετήσετε τον αλγόριθμο «ταξινόμηση φυσαλίδας» (bubble sort) και στη συνέχεια να κατασκευάσετε τον ψευδοκώδικα που εφαρμόζει τον αλγόριθμο αυτό για την ταξινόμηση των στοιχείων ενός πίνακα Α που περιέχει Ν στοιχεία, όπου Ν ακέραιος αριθμός ο οποίος εισάγεται από το πληκτρολόγιο κατά την εκτέλεση του προγράμματος. Στην αρχή του προγράμματος εισάγονται στα στοιχεία του πίνακα Α τυχαίοι αριθμοί μεταξύ του 1 και του 450. Αποθηκεύστε το πρόγραμμα με το όνομα Ask_4.elp. Εκτελέστε το και δείτε τα αποτελέσματα.

Υπόδειξη

Στη δραστηριότητα αυτή, για να ταξινομήσουμε τα στοιχεία του πίνακα Α, θα πρέπει προηγουμένως, εκτός από τη δημιουργία του, να εκχωρήσουμε (τυχαίες) τιμές στα στοιχεία του.

Για να εκχωρήσουμε σε μια μεταβλητή ή σε στοιχείο ενός πίνακα έναν τυχαίο ακέραιο μεταξύ του 1 και ενός αριθμού Χ, χρησιμοποιούμε την εντολή:

-Θέσε .. ίσο με τυχαίο αριθμό από 1 έως ..

Στο πρώτο κενό της εντολής εισάγεται η μεταβλητή στην οποία θα εκχωρηθεί ο τυχαίος ακέραιος αριθμός από το 1 έως τον ακέραιο Χ που εισάγεται στο δεύτερο κενό.

Περιγραφή της μεθόδου «ταξινόμηση φυσαλίδας»

Στη μέθοδο «ταξινόμηση φυσαλίδας», ξεκινώντας από το πρώτο στοιχείο του πίνακα που θέλουμε να ταξινομήσουμε, σαρώνουμε όλα τα στοιχεία του πίνακα σειριακά, συγκρίνοντας κάθε στοιχείο με το επόμενο. Αν το τρέχον στοιχείο είναι μεγαλύτερο από το επόμενο, τότε τα δύο αυτά στοιχεία ανταλλάσσουν θέση στον πίνακα. Με αυτό τον τρόπο το μεγαλύτερο στοιχείο προωθείται στην τελευταία θέση του πίνακα. Έτσι, την πρώτη φορά θα σαρωθεί ο πίνακας και για τα Ν στοιχεία του, με αποτέλεσμα στο τέλος της διαδικασίας το μεγαλύτερο από αυτά να καταλήξει στη Ν-οστή θέση. Τη δεύτερη φορά γίνεται η ίδια διαδικασία για τα πρώτα Ν-1 στοιχεία του πίνακα, οπότε το μεγαλύτερο από αυτά καταλήγει στη (Ν-1)-οστή θέση. Την τρίτη φορά επαναλαμβάνεται η διαδικασία αυτή για τα πρώτα Ν-2 στοιχεία κ.ο.κ. Η διαδικασία συγκρίσεως των στοιχείων ανά δύο συνεχίζεται, μειώνοντας κάθε φορά κατά 1 το πλήθος των στοιχείων του πίνακα που θα σαρωθούν.

Για να ολοκληρωθεί η ταξινόμηση ενός πίνακα Ν στοιχείων, με τη μέθοδο «ταξινόμηση φυσαλίδας», απαιτούνται συνολικά Ν-2 επαναλήψεις σάρωσης και

Αλγόριθμος

Ø Διάβασε και βάλε στη μεταβλητή Ν το πλήθος των στοιχείων που θα ταξινομηθούν.

Ø Δημιούργησε έναν κενό πίνακα, με όνομα Α, Ν στοιχείων.

Ø Ξεκινώντας από το 1, επανάλαβε Ν φορές τα παρακάτω βήματα:

o Βάλε στο I-οστό στοιχείο του πίνακα Α έναν τυχαίο ακέραιο από 1 έως 450, όπου I ο μετρητής της επαναληπτικής διαδικασίας.

o Εμφάνισε το I-οστό στοιχείο του πίνακα Α και στη συνέχεια τους χαρακτήρες κενό+παύλα+κενό, ως διαχωριστικό των αποτελεσμάτων.

Ø Άφησε δύο κενές γραμμές (για την ευκρίνεια των αποτελεσμάτων).

Ø Ξεκινώντας από το 1, επανάλαβε Ν-2 φορές, με μετρητή το I, τα παρακάτω βήματα:

o Ξεκινώντας από το 1, επανάλαβε Ν-I φορές, με μετρητή το J, τα παρακάτω βήματα:

q Συνέκρινε το J-οστό στοιχείο του πίνακα Α,  με το επόμενο (J+1)-οστό

v αν A[J] > A[J+1] τότε, μετάθεσε τις τιμές τους ως εξής:

i. Βάλε στη μεταβλητή TEMP το περιεχόμενο του στοιχείου A[J].

ii. Βάλε στο στοιχείο A[J] το περιεχόμενο του στοιχείου A[J+1].

iii. Βάλε στο στοιχείο A[J+1] το περιεχόμενο της μεταβλητής TEMP.

Ø Ξεκινώντας από το 1, επανάλαβε Ν φορές:

o Εμφάνισε το I-οστό στοιχείο του πίνακα Α και στη συνέχεια κενό+παύλα+κενό, ως διαχωριστικό των αποτελεσμάτων. Όπου I ο μετρητής της επαναληπτικής διαδικασίας.