Τι ονομάζουμε Ταξινόμηση;

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

Παράδειγμα 1. Έστω οι αριθμοί 3,2,90,7  και 9. Μία ταξινόμηση θα μπορούσε να είναι η εξής: πρώτα οι άρτιοι αριθμοί και μετά οι περιττοί. Το τελικό αποτέλεσμα θα είναι  2,90,3,7,9.

Παράδειγμα2. Δίνονται οι μήνες Μάρτιος, Φεβρουάριος, Ιούνιος, Δεκέμβριος και Ιανουάριος και μας ζητάνε να τους ταξινομήσουμε ημερολογιακά. Οπότε η σειρά είναι  Ιανουάριος , Φεβρουάριος, Μάρτιος, Ιούνιος και Δεκέμβριος.

Παρατήρηση. Η ταξινόμηση κατά αύξουσα ή φθίνουσα σειρά έχει νόημα και για κείμενο αφού “Α”<“Β”<“Γ”< “Δ” κλπ.
Άρα η συνθήκη “ΜΙΚΡΟΣ” < “ΜΕΓΑΛΟΣ” είναι ψευδής (“Ε”<“Ι”).
Το βιβλίο δεν αναφέρει τι ισχύει στις παρακάτω περιπτώσεις:
1) “Α” > “α”
2) “Α”>5
3) “ω”<“w”

Ταξινόμηση Ευθείας Ανταλλαγής ή Ταξινόμηση Φυσαλίδας

Αν και υπάρχουν πολλοί αλγόριθμοι ταξινόμησης ο αλγόριθμος της ευθείας ανταλλαγής είναι και ο ευκολότερος.

				
					Αλγόριθμος Φυσαλίδα
Δεδομένα // table, n //
Για i από 2 μέχρι n
  Για j από n μέχρι i με_βήμα -1
    Αν table[j-1] > table[j] τότε
      temp <- table[j—1]
      table[j—1] <-table[j]
      table[j] <- temp    
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης
Αποτελέσματα // table //
Τέλος Φυσαλίδα

Η παρακάτω διαδραστική παρουσίαση δείχνει με παράδειγμα τα βήματα της Ταξινόμηση Ευθείας Ανταλλαγής (Ταξινόμηση Φυσαλίδας) . Όπου  εμφανίζεται ένα πράσινο βελάκι θα πρέπει να το πατήσετε για να προχωρήσει.

Στην παρακάτω διαδραστική εφαρμογή μπορείτε να κάνετε δυαδική αναζήτηση με οποιοδήποτε αριθμό και να δείτε τα βήματα που ακολουθούνται.

Ταξινόμηση - Bubble Sort




 
					1. Για i απο 2 μεχρι 10
					2.   Για j απο 10 μεχρι i με_βημα -1
					3.     Αν Π[j-1]>Π[j-1] τότε
					4.        αντιμετάθεσε Π[j-1], Π[j-1]
					5.     Τέλος_αν
					6.    Τέλος_επανάληψης
					7. Τέλος_επανάληψης

           

Ερωτήσεις ανάπτυξης απο Πανελλαδικές εξετάσεις

  1. Δίνεται μονοδιάστατος πίνακας Π, Ν στοιχείων, που είναι ακέραιοι αριθμοί. Να αναπτύξετε αλγόριθμο, ο οποίος να ταξινομεί με τη μέθοδο της φυσαλίδας τα στοιχεία του πίνακα Π. (2000-Θ1Δ)