Αρχική ΑΕΠΠ - Δομές Δεδομένων Λειτουργικά Συστήματα Δίκτυα Υπολογιστών ΙΙ Βάσεις Δεδομένων Παιδαγωγικά - Διδακτική
Βασικές Έννοιες
Μεταβλητή - Έκφραση Δομή Ακολουθίας Δομή Επιλογής Δομή Επανάληψης
Αναπαράσταση Αλγορίθμων
Πίνακες
Μονοδιάστατοι Δισδιάστατοι Πολυδιάστατοι Αναζήτηση Ταξινόμηση Στοίβα Ουρά
Υποπρογράμματα
Συναρτήσεις Διαδικασίες Σχετικά με τις παράμετρους
Δυναμικές Δομές
Η ταξινόμηση αυτή πραγματοποιείται με τα παρακάτω βήματα:
- επιλογή του μικρότερου στοιχείου
- ανταλλαγή αυτού με το i-οστό στοιχείο (το i ξεκινάει από 1 και αυξάνει κατά 1)
- επανάληψη των παραπάνω βημάτων για τα υπόλοιπα στοιχεία.
Στον παρακάτω πίνακα φαίνεται πως λειτουργεί ο αλγόριθμος. Με μαύρο φόντο είναι τα στοιχεία του πίνακα που αλλάζουν θέση και με γκρι είναι το ταξινομημένο τμήμα του πίνακα. Παρατηρήστε ότι για i=4, το 42 είναι το μικρότερο από όλα τα στοιχεία που βρίσκονται δεξιά του, έτσι δεν έχουμε ανταλλαγή στοιχείων. Το ίδιο ισχύει για i=6.
Κώδικας
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[n], I, J, POS, MIN
ΑΡΧΗ
ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ n
POS <- I ! η θέση στον πίνακα που έχουμε την ελάχιστη τιμή
MIN <- A[I] ! τιμή του τρέχοντος κλειδιού θεωρείται η ελάχιστη
! αναζητούμε την ύπαρξη μικρότερου κλειδιού σε σχέση με
! το παραπάνω στο τμήμα του πίνακα από i+1 μέχρι n
ΓΙΑ J ΑΠΟ Ι+1 ΜΕΧΡΙ n
ΑΝ Α[J] < MIN ΤΟΤΕ ! αν βρέθηκε μικρότερο από το min
POS <- J ! κρατάμε τη θέση του
MIN <- A[J] ! και την τιμή του στη min
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! Ανταλλάσσουμε τα κλειδιά των θέσεων i και pos
A[POS] <- A[I]; ! στη θέση που είναι το μικρότερο κλειδί βάζουμε το Α[i]
A[i] <- MIN; ! και στη Α[i] την μικρότερη τιμή min
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
for (i=0; i<n; i++) {
pos=i; /* η θέση στον πίνακα που έχουμε την ελάχιστη τιμή */
min=A[i]; /* η τιμή του τρέχοντος κλειδιού θεωρείται η ελάχιστη */
/* αναζητούμε την ύπαρξη μικρότερου κλειδιού σε σχέση με */
/* το παραπάνω στο τμήμα του πίνακα από i+1 μέχρι n */
for (j=i+1; j<n; j++) {
if (A[j] < min) { /* αν βρέθηκε μικρότερο από το min */
pos=j; /* κρατάμε τη θέση του */
min=A[j]; /* και την τιμή του στη min */
}
}
/* ανταλλάσσουμε τα κλειδιά των θέσεων i και pos */
A[pos]=A[i]; /* στη θέση που είναι το μικρότερο κλειδί βάζουμε το Α[i]*/
A[i] =min; /* και στη Α[i] την μικρότερη τιμή min */
}
return;
}
Ορθότητα
Για κάθε i θεωρούμε την τιμή Α[i] ως την μικρότερη. Ο εσωτερικός βρόχος ελέγχει αν πράγματι η τιμή αυτή είναι μικρότερη, εξετάζοντας τα στοιχεία Α[(i+1)..n]. Ο βρόχος αυτός τερματίζει πάντα γιατί φτάνει στο n. Αν βρέθηκε μικρότερο στοιχείο, έστω Α[k] τότε αυτό μεταφέρεται στη θέση Α[i], έτσι ο πίνακας Α[1..i] είναι ταξινομημένος.
Ο εξωτερικός βρόχος τερματίζει όταν i=n-1 οπότε και ελέγχονται τα δύο τελευταία στοιχεία του πίνακα Α[n-1] και A[n], και τοποθετείται το μικρότερο στη θέση Α[n-1] και το μεγαλύτερο στην A[n].
Άρα, όταν τελειώσει και ο εξωτερικός βρόχος, όλα τα στοιχεία του πίνακα είναι ταξινομημένα σε αύξουσα σειρά.
Χρονική Πολυπλοκότητα
Ο αλγόριθμος έχει δύο βρόχους εμφολιασμένους. Ο εσωτερικός βρόχος for εκτελείται κάθε για κάθε i και συγκεκριμένα n-1 φορές για i=1, n-2 για i=2 και μία φορά για i=n-1, συνολικά n(n-1)/2 φορές.
Ο βρόχος for εκτελείται n φορές.
Ο συνολικός χρόνος για τον αλγόριθμο είναι:
Ο μεγαλύτερος όρος είναι ο n2, άρα ο αλγόριθμος είναι τετραγωνικής πολυπλοκότητας Ο(n2).
Σύγκριση με τον αλγόριθμο ευθείας παρεμβολής
Ο αλγόριθμος ευθείας παρεμβολής, όταν τα στοιχεία του πίνακα είναι ήδη ταξινομημένα, ο εσωτερικός βρόχος while δεν εκτελείται με αποτέλεσμα η χρονική πολυπλοκότητά του να είναι γραμμική Ο(n).
Στον αλγόριθμος ευθείας επιλογής, όταν τα στοιχεία του πίνακα είναι ήδη ταξινομημένα, ο εσωτερικός βρόχος for εκτελείται πάντα, με αποτέλεσμα η χρονική πολυπλοκότητά του να είναι πάντα τετραγωνική Ο(n2).
Χωρική Πολυπλοκότητα
Ο αλγόριθμος χρησιμοποιεί έναν πίνακα με n στοιχεία και τέσσερις μεταβλητές, την i, την j, την pos και την min. Αυτές οι μεταβλητές καταλαμβάνουν από μία θέση μνήμης η κάθε μία. Οπότε, συνολικά η θέσεις μνήμης που χρησιμοποιεί ο αλγόριθμος είναι:
S(n)=n+4
Η χωρική πολυπλοκότητα καθορίζεται από τον μεγαλύτερο όρο της εξίσωσης ο οποίος είναι ο n, δηλαδή, ο αλγόριθμος έχει γραμμική χωρική πολυπλοκότητα O(n).
Copyright 2008 - Άρης Φεργάδης