Έστω ότι ο αρχικός πίνακας αποτελείται από εννέα κλειδιά τα εξής: 52, 12, 71, 56, 5, 10, 19, 90 και 45. Η μέθοδος εφαρμοζόμενη σε αυτά τα εννέα κλειδιά εξελίσσεται όπως φαίνεται στο επόμενο σχήμα. Κάθε φορά το ταξινομημένο τμήμα του πίνακα εμφανίζεται με χρώμα, ενώ τα στοιχεία που σαν φυσαλίδες ανέρχονται μέσα στον πίνακα εντοπίζονται με το αντίστοιχο βέλος στα δεξιά τους. Κάθε φορά εμφανίζεται η τάξη της επανάληψης (i).
Σχ.3.7 Ταξινόμηση φυσαλίδας.
ΛΥΣΗ:
Η ταξινόμηση φυσαλίδας υλοποιείται με τον επόμενο αλγόριθμο.
Αλγόριθμος Φυσαλίδα
Δεδομένα //table , n //
Για i από 2 μέχρι n
Για j από n μέχρι i με_βήμα -1
Αν table[j-1] > table[j] τότε
αντιμετάθεσε table[j-1], table[j]
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης
Αποτελέσματα // table //
Τέλος Φυσαλίδα
Στον αλγόριθμο αυτό ως είσοδος δίνεται η μεταβλητή table με n ακεραίους που πρέπει να ταξινομηθούν. Φυσικά η επιλογή του ακέραιου τύπου για το κλειδί είναι αυθαίρετη, αφού μπορεί να χρησιμοποιηθεί οποιοσδήποτε άλλος τύπος, όπου ορίζεται μία συνάρτηση διάταξης, όπως για παράδειγμα ο τύπος του χαρακτήρα.
Σημειώνεται ότι η εντολή “αντιμετάθεσε table[j-1], table[j]” ανταλλάσσει το περιεχόμενο δύο θέσεων με τη βοήθεια μίας βοηθητικής θέσης. Εναλλακτικά αυτό μπορεί να γίνει με τις εξής τρεις εντολές:
temp<--table[j-1] table[j-1]<--table[j] table[j]<--temp
Παρατήρηση: Η ταξινόμηση φυσαλίδας είναι ο πιο απλός και ταυτόχρονα ο πιο αργός αλγόριθμος ταξινόμησης.
εαν εχω 2 μονοδιαστατους πινακες και μου ζητηθει να κανω ταξινόμηση στον ενα, υποχρεούμαι να κανω ταξινόμηση και στον αλλο;
Θα ήταν χρήσιμο να μεταφέρεις ακριβώς την εκφώνηση του προβλήματος. Γενικά, σε κάθε άσκηση, προσπαθούμε να απαντήσουμε σε ότι μας ζητηθεί. Συχνά όμως, χρειάζεται να υπολογίσουμε ενδιάμεσα αποτελέσματα που θα μας βοηθήσουν κατόπιν στην επίλυση. Στη περίπτωση σου, αναρωτιέμαι αν οι 2 πίνακες που αναφέρεις είναι Παράλληλοι, δηλαδή συσχετίζονται τα δεδομένα τους, πχ. μονοδιάσταστος πίνακας χαρακτήρων ΟΝΟΜΑ[10] με το όνομα μαθητή, και μονοδιάστατος πίνακας ΒΑΡΟΣ[10] με το βάρος, που αποθηκεύουν το όνομα και το αντίστοιχο βάρος 10 μαθητών μιας τάξης. Δεν είναι δυνατή η αποθήκευση σε διδιάστατο πίνακα γιατί τα δεδομένα μας έχουν διαφορετικό τύπο (ΧΑΡΑΚΤΗΡΕΣ, ΠΡΑΓΜΑΤΙΚΟΙ). Η παράλληλη συσχέτιση προκύπτει ως εξής: η θέση 1 κάθε πίνακα αναφέρεται στον ίδιο μαθητή, δηλαδή ο μαθητής με το όνομα ΟΝΟΜΑ[1], έχει βάρος ΒΑΡΟΣ[1]. Η ίδια σχέση προκύπτει για όλες τις άλλες θέσεις του κάθε πίνακα. Στη περίπτωση αυτή, αν ταξινομήσεις μόνο τον έναν πίνακα, χάνεται η συσχέτιση (παύουν οι πίνακες να είναι παράλληλοι), κάτι που ίσως είναι χρήσιμο σε κάποιο από τα ερωτήματα της άσκησης. Θα μπορούσες να αναζητήσεις ασκήσεις με λέξη Κλειδί Παράλληλοι πίνακες για να δεις περισσότερα παραδείγματα.