Αρχική ΑΕΠΠ - Δομές Δεδομένων Λειτουργικά Συστήματα Δίκτυα Υπολογιστών ΙΙ Βάσεις Δεδομένων Παιδαγωγικά - Διδακτική

Βασικές Έννοιες

Μεταβλητή - Έκφραση Δομή Ακολουθίας Δομή Επιλογής Δομή Επανάληψης

Αναπαράσταση Αλγορίθμων

Διάγραμμα Ροής

Πίνακας Τιμών

Πίνακες

Μονοδιάστατοι Δισδιάστατοι Πολυδιάστατοι Αναζήτηση Ταξινόμηση Στοίβα Ουρά

Υποπρογράμματα

Συναρτήσεις Διαδικασίες Σχετικά με τις παράμετρους

Δυναμικές Δομές

Λίστες Δέντρα Γράφοι

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

  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).

Τελευταία ενημέρωση: 31-01-2008 (10:15)

Copyright 2008 - Άρης Φεργάδης