DataStructures: SelectionSort-Theory

Η ταξινόμηση αυτή πραγματοποιείται με τα παρακάτω βήματα:

  1. επιλογή του μικρότερου στοιχείου
  2. ανταλλαγή αυτού με το i-οστό στοιχείο (το i ξεκινάει από 1 και αυξάνει κατά 1)
  3. επανάληψη των παραπάνω βημάτων για τα υπόλοιπα στοιχεία.

Στον παρακάτω πίνακα φαίνεται πως λειτουργεί ο αλγόριθμος. Με μαύρο φόντο είναι τα στοιχεία του πίνακα που αλλάζουν θέση και με γκρι είναι το ταξινομημένο τμήμα του πίνακα. Παρατηρήστε ότι για i=4, το 42 είναι το μικρότερο από όλα τα στοιχεία που βρίσκονται δεξιά του, έτσι δεν έχουμε ανταλλαγή στοιχείων. Το ίδιο ισχύει για i=6.

Κώδικας

ΔΙΑΔΙΚΑΣΙΑ ΤΑΞΙΝΟΜΗΣΗ_ΜΕ_ΕΠΙΛΟΓΗ(Α, n)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Α[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                  
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
void SelectionSort(int A[], int n) {
  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).

Page last modified on 31-01-2008 (12:15)