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

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

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

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

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

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

Πίνακες

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

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

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

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

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

Η μέθοδος αυτή εισάγει ένα-ένα τα στοιχεία του συνόλου που εξετάζεται στη σωστή τους θέση. Στη φάση i:

  • υποθέτουμε ότι ο πίνακας Α[1..(i-1)] είναι ταξινομημένος,
  • εισάγουμε το στοιχείο A[i] στην ακολουθία Α[1..(i-1)] στη σωστή θέση. Αυτό επιτυγχάνεται μετακινώντας όλα τα στοιχεία που είναι μεγαλύτερα του A[i] μία θέση δεξιά.

Κώδικας

Ο κώδικας που υλοποιεί τον αλγόριθμο δίνεται με μορφή διαδικασίας για τη ΓΛΩΣΣΑ και την C. Παράμετρος είναι ο πίνακας που θα ταξινομηθεί και το πλήθος των στοιχείων του.

ΔΙΑΔΙΚΑΣΙΑ ΤΑΞΙΝΟΜΗΣΗ_ΜΕ_ΠΑΡΕΜΒΟΛΗ(Α, n)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Α[n], Ι, J. KEY
ΑΡΧΗ
  ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ n
    KEY=A[I]  ! στοιχείο εισαγωγής
    J  = I-1  ! δεξί άκρο ταξινομημένης ακολουθίας

    ΟΣΟ J>0 ΚΑΙ KEY<A[J] ΕΠΑΝΑΛΑΒΕ
      Α[J+1] = A[J]  ! μετακίνηση στοιχείου δεξιά
      J <- J-1       ! μετακίνηση στο αμέσως αριστερά στοιχείο
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    Α[J+1] = KEY;
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

Οι πίνακες στην C ξεκινούν από το στοιχεί 0 και φτάνουν στο n-1. Αυτό επιβάλει μερικές μικρές αλλαγές στον αλγόριθμο τόσο στο for όσο και στο while.

void InsertionSort(int A[], int n) {
  for (i=1; i<n; i++) {
    key = A[i]; /* στοιχείο εισαγωγής */
    j   = i-1;  /* δεξί άκρο ταξινομημένης ακολουθίας */

    while (j >= 0) and (key < A[j]) {
      A[j+1] = A[j]; /* μετακίνηση στοιχείου δεξιά */
      j--;           /* μετακίνηση στο αμέσως αριστερά στοιχείο */
    }
    A[j+1] = key;
  }
  return;
}

Ορθότητα

Τα στοιχεία του πίνακα Α[1..(i-1)] είναι ταξινομημένα. Το πρώτο στοιχείο της μη ταξινομημένης ακολουθίας Α[i..n], δηλαδή το Α[i] ελέγχεται με όλα τα στοιχεία του πίνακα Α[1..(i-1)] ξεκινώντας από το i-1 μέχρι να βρεθεί κάποιο μικρότερό του. Κάθε φορά που βρίσκεται ένα στοιχείο μεγαλύτερο του A[i] αυτό μετακινείται στην αμέσως μεγαλύτερη θέση.

Έστω ότι το A[k] (1<k<i-1) είναι μικρότερο του A[i]. Όταν βρεθεί ήδη όλα τα στοιχεία A[k+1..i-1] έχουν μετακινηθεί στην αμέσως μεγαλύτερη θέση τους, και το Α[i] τοποθετείται στη θέση A[k+1], οπότε τα στοιχεία Α[1..i] του πίνακα είναι ταξινομημένα.

Στην περίπτωση που δε βρεθεί στοιχείο μικρότερο του Α[i] τότε έχουμε φτάσει στην αρχή του πίνακα και το Α[i] τοποθετείται στη θέση A[1], ήδη όμως όλα τα στοιχεία Α[2..(i-1)] έχουν μετακινηθεί στην αμέσως μεγαλύτερη θέση τους, οπότε τα στοιχεία Α[1..i] του πίνακα είναι ταξινομημένα.

Μέσω του βρόχου while γίνεται η σύγκριση του Α[i] με τα στοιχεία Α[1..(i-1)]. Ο βρόχος τερματίζει πάντα όπως περιγράφηκε παραπάνω. Ο βρόχος for εξασφαλίζει ότι ελέγχονται όλα τα στοιχεία του πίνακα και τερματίζει όταν το i=n, οπότε όλα τα στοιχεία του πίνακα Α[1..n] είναι ταξινομημένα.

Χρονική Πολυπλοκότητα

Ο αλγόριθμος έχει δύο βρόχους εμφολιασμένους. Ο εσωτερικός βρόχος while, θεωρούμε ότι εκτελείται για κάθε i, άρα εκτελείται για i=2 μία φορά, για i=3 δύο φορές και για i=n, n-1 φορές, συνολικά n(n-1)/2 φορές.

Ο βρόχος for εκτελείται n φορές.

Ο συνολικός χρόνος για τον αλγόριθμο είναι:

Ο μεγαλύτερος όρος είναι ο n2, άρα ο αλγόριθμος είναι τετραγωνικής πολυπλοκότητας Ο(n2).

Περίπτωση αρχικού ταξινομημένου πίνακα

Σε περίπτωση που ο πίνακας Α είναι ήδη ταξινομημένος η εντολή while δεν εκτελείται ποτέ γιατί πάντα key > A[j] (ή αλλιώς Α[i] > A[i-1] αφού key=A[i] και j=i-1) και η συνθήκη στο while είναι πάντα ψευδής. Σ' αυτή την περίπτωση η συνεισφορά της while είναι σταθερής πολυπλοκότητας. Τελικά έχουμε έναν εξωτερικό βρόχο ο οποίος εκτελείται n φορές και ο συνολικός χρόνος είναι T(n)=n. Οπότε, σ' αυτή την περίπτωση ο αλγόριθμος είναι γραμμικής πολυπλοκότητας O(n).

Χωρική Πολυπλοκότητα

Ο αλγόριθμος χρησιμοποιεί έναν πίνακα με n στοιχεία και τρεις μεταβλητές, την i, την j και την key. Αυτές οι μεταβλητές καταλαμβάνουν από μία θέση μνήμης η κάθε μία. Οπότε, συνολικά η θέσεις μνήμης που χρησιμοποιεί ο αλγόριθμος είναι:

S(n)=n+3

Η χωρική πολυπλοκότητα καθορίζεται από τον μεγαλύτερο όρο της εξίσωσης ο οποίος είναι ο n, δηλαδή, ο αλγόριθμος έχει γραμμική χωρική πολυπλοκότητα O(n).

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

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