Βελτιωμένος αλγόριθμος ταξινόμησης ευθείας ανταλλαγής (bubble sort) - Δημιουργία τυχαίας λίστας διαφορετικών ακέραιων αριθμών (random - randint)

 

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

Όμως, στην κανονική του μορφή, κάνει συγκεκριμένα περάσματα (n-1, όπου n το μήκος της λίστας προς ταξινόμηση), ακόμα κι όταν η λίστα είναι ήδη ταξινομημένη.

Αυτό μπορεί να διορθωθεί ελέγχοντας αν στο τέλος ενός περάσματος από τα n-1, προκύψουν μηδενικές ανταλλαγές.

Στο αρχείο python που παρατίθεται, έχουμε την απλή υλοποίηση και την βελτιωμένη. Η λίστα των αριθμών παράγεται με την χρήση της βιβλιοθήκης random και της συνάρτησης randint, ώστε να έχουμε μια τυχαία και όχι προσχεδιασμένη λίστα.    

Αρχείο Python 1

 Αρχείο Python 2

Στην εικόνα που ακολουθεί φαίνεται ο κώδικας του προγράμματος και η εκτέλεση του, όπου φαίνεται ξακάθαρα ότι σε μία τυχαία αταξινόμητη λίστα στην απλή υλοποίηση του bubble sort κάνουμε δύο περάσματα επιπλέον σε σχέση με την βελτιωμένη υλοποίηση. Σε μία λίστα 10 αριθμών η διαφορά φαίνεται μικρή, αλλά σε πολύ μεγάλες λίστες υπάρχει μεγάλη εξοικονόμηση επαναλήψεων.

 

 

Παράδειγμα με παράλληλη ταξινόμηση

Διπλή παράλληλη ταξινόμηση, πρώτα σε αύξουσα σειρά και μετά σε φθίνουσα σειρά ώστε τα γράμματα που έχουν ίδιο αριθμό να είναι ταξινομημένα αλφαβητικά. Π.χ. 'b','f' που έχουν 85 και 'g', 'h' που έχουν 79

Παράδειγμα 

 Πριν την ταξινόμηση
['c', 'f', 'a', 'h', 'd', 'b', 'e', 'i', 'g']
[89, 85, 92, 79, 83, 85, 95, 82, 79]

Μετά την ταξινόμηση
['e', 'a', 'c', 'b', 'f', 'd', 'i', 'g', 'h']
[95, 92, 89, 85, 85, 83, 82, 79, 79]

Παράλληλη ταξινόμηση 2 λιστών με τον αλγόριθμο ευθείας ανταλλαγής (bubble sort)

Στην περίπτωση που έχουμε 2 λίστες που συσχετίζονται, μπορούμε με την εφαρμογή του αλγόριθμου ταξινόμησης ευθείας ανταλλαγής να τις ταξινομήσουμε ταυτόχρονα.

Έστω 2 λίστες που συσχετίζονται:

x1=[65, 90, 85, 92, 78, 80]

x2=['A', 'B', 'C', 'D', 'E', 'F']

Π.χ. αν είναι βαθμολογίες, ο 'A' έχει βαθμολογία 65, ο 'B' έχει βαθμολογία 90, ο 'C' 85 κ.ο.κ.

Παρουσιάζονται δυο υλοποιήσεις του αλγόριθμου. 

Στην πρώτη, η λίστα με τις βαθμολογίες ταξινομείται σε αύξουσα σειρά (65,78,80,85,90,92) και παράλληλα η λίστα των ονομάτων. 

Στη δεύτερη, η λίστα με τις βαθμολογίες ταξινομείται σε φθίνουσα σειρά (92,90,85,80,78,65) και παράλληλα η λίστα των ονομάτων. 

Παρατήρηση:

Όταν ταξινομούμε σε φθίνουσα σειρά η γραμμή:

if L[j]<L[j-1]:

 γίνεται:

if L[j]>L[j-1]:

Οι δύο υλοποιήσεις σε μορφή PDF

Ταξινόμηση ευθείας ανταλλαγής (bubble sort)

Δημιουργία συνάρτησης που υλοποιεί τον αλγόριθμο ευθείας ανταλλαγής (bubble sort). Στο κυρίως πρόγραμμα γεμίζουμε μια λίστα με αριθμούς χωρίς ταξινόμηση. Καλούμε τη συνάρτηση ταξινόμησης και εμφανίζεται η λίστα αταξινόμητη και ταξινομημένη.

Ο αλγόριθμος υλοποιημένος σε python

Ταξινομηση bubble sort