2 of 21

Ταξινόμηση ευθείας γραμμής / φυσαλίδας

Η μέθοδος της ταξινόμησης (straight exchange sort) βασίζεται στην αρχή της σύγκρισης και ανταλλαγής ζευγών γειτονικών στοιχείων, μέχρις ότου διαταχθούν όλα τα στοιχεία. Σύμφωνα με τη μέθοδο αυτή, κάθε φορά γίνονται διαδοχικές προσπελάσεις στον πίνακα και μετακινείται το μικρότερο κλειδί της ακολουθίας προς το αριστερό άκρο του πίνακα. Η μέθοδος είναι γνωστή ως ταξινόμηση φυσαλίδας (bubblesort).

3 of 21

Γενική Μορφή

Για i από 2 μέχρι Ν

Για j από N μέχρι I με_βήμα -1

Αν Α[J] < A[J-1] τότε

TEMP <- A[J]

A[J] <- A [J-1]

A[J-1] <- TEMP

Τέλος_αν

Τέλος_επανάληψης

*Όπου Ν = οι θέσεις του πίνακα και Α ο πίνακας

4 of 21

Αν ο πίνακας θεωρηθεί σε κατακόρυφη θέση και το περιεχόμενό του θεωρηθεί ως φυσαλίδες σε δεξαμενή νερού, τότε κάθε προσπέλαση του πίνακα έχει ως αποτέλεσμα την άνοδο της ελαφρύτερης (μικρότερης τιμής του πίνακα) από τις φυσαλίδες που δεν έχουν ταξινομηθεί ακόμα στην κατάλληλη θέση του πίνακα

3 (1)
6 (2)
9 (3)
1 (4)
4 (5)
2 (6)

5 of 21

1η προσπέλαση

Σύγκριση 1^η

Αρχικά συγκρίνονται τα δύο στοιχεία που βρίσκονται στις 2 τελευταίες θέσεις, δηλαδή το 4 και το 2. Επειδή το στοιχείο στη μεγαλύτερη θέση (δηλαδή στην τελευταία) είναι μικρότερο από της προηγούμενής της (δηλαδή της προτελευταίας), αυτά αλλάζουν θέση (αντιματέθενται).

Σύγκριση 2^η

Στη συνέχεια έχουμε τη σύγκριση των στοιχείων που βρίσκονται στην 5η και την 4η θέση, δηλαδή του 2 και του 1 αντίστοιχα. Αυτά δεν αντιμετατίθενται, γιατί έχουν μεταξύ τους τη σωστή διάταξη.

6 of 21

Σύγκριση 3η

Η σύγκριση συνεχίζεται με τις θέσεις 4 και 3, δηλαδή με τα στοιχεία 1 και 9. Το 1 βρίσκεται χαμηλότερα από το 9, οπότε πρέπει να ανταλλάξουν θέσεις.

Σύγκριση 4^η

Με ανάλογο τρόπο συγκρίνονται τα στοιχεία των θέσεων 3 και 2, δηλαδή το 1 και το 6, οπότε και αυτά πρέπει να ανταλλάξουν θέσεις.

7 of 21

Σύγκριση 4^η

Σύγκριση 5^η

Εδώ συγκρίνονται τα στοιχεία στις θέσεις 1 και 2, δηλαδή με τις τιμές 1 και 3, όπου και αυτές πρέπει να ανταλλάξουν θέσεις.

8 of 21

Συγκρίσεις

1^η
3
6
9
1
4
2

2^η
3
6
9
1
2
4

4^η
3
6
1
9
2
4

3^η
3
6
9
1
2
4

5^η
3
1
6
9
2
4

1
3
6
9
2
4

9 of 21

2^η προσέλαση

4^η
1
3
2
6
9
4

1
2
3
6
9
4

1^η
1
3
6
9
2
4

2^η
1
3
6
9
2
4

3^η
1
3
6
2
9
4

10 of 21

3^η προσπέλαση

3^η
1
2
3
4
6
9

2^η
1
2
3
6
4
9

1^η
1
2
3
6
9
4

1
2
3
4
6
9

11 of 21

4^η προσέλαση

2^η
1
2
3
6
4
9

1^η
1
2
3
4
6
9

1
2
3
4
6
9

12 of 21

5^η προσπέλαση

1^η
1
2
3
4
6
9

1
2
3
4
6
9

13 of 21

Ταξινόμηση με επιλογή

Στη μέθοδο αυτή, οφείλουμε μα εντοπίσουμε το ελάχιστο ή το μέγιστο στοιχείο του πίνακα (ανάλογα αν ζητείται αύξουσα ή φθίνουσα διάταξη), και να το αντιμεταθέσουμε με τη θέση που βρισκόμαστε κάθε φορά.

14 of 21

Γενική Μορφή

Για θ από 1 μέχρι Ν-1

min <- A[θ]

θέση_min <- θ

Για k από θ+1 μέχρι Ν

Αν Α[k] < min τότε

min <- A[k]

θέση_min <- k

Τέλος_αν

Τέλος_επανάληψης

temp <- Α[θέση_min]

Α[θ] <- temp

Τέλος επανάληψης

(παρομοίως για φθίνουσα διάταξη)

15 of 21

ΒΗΜΑΤΑ

Έστω ο πίνακας:

ΒΗΜΑ 1^Ο: Αρχικά βρίσκουμε τη θέση του μικρότερου στοιχείου που είναι η 4^η. Τα στοιχεία της θέσης 1 και 4 θα ανταλλάξουν περιεχόμενο.

8	5	7	2	6	4
1	2	3	4	5	6

8	5	7	2	6	4
1	2	3	4	5	6

16 of 21

ΒΗΜΑ 2^ο: Πάλι βρίσκουμε το μικρότερο από τη 2η θέση και μετά. Αυτό βρίσκεται στη θέση 6, οπότε οι θέσεις 2 και 6 θα ανταλλάξουν περιεχόμενο.

2	5	7	8	9	4
1	2	3	4	5	6

17 of 21

ΒΗΜΑ 3^Ο: Το μικρότερο στοιχείο μετά την 3η θέση βρίσκεται στη θέση 6, οπότε οι θέσεις 3 και 6 θα ανταλλάξουν περιεχόμενο.

2	4	7	8	6	5
1	2	3	4	5	6

18 of 21

ΒΗΜΑ 4^Ο: Το μικρότερο στοιχείο μετά την 4η θέση βρίσκεται στη θέση 5, οπότε οι θέσεις 4 και 6 θα ανταλλάξουν περιεχόμενο.

2	4	5	8	6	7
1	2	3	4	5	6

19 of 21

ΒΗΜΑ 5^Ο: Το μικρότερο στοιχείο μετά την 5η θέση βρίσκεται στη θέση 6, οπότε οι δύο τελευταίες θέσεις θα ανταλλάξουν περιεχόμενο.

2	4	5	6	8	7
1	2	3	4	5	6

20 of 21

Ο πίνακας πλέον είναι ταξινομημένος:

2	4	5	6	7	8
1	2	3	4	5	6

1 of 21