Επιλογή Σελίδας

ΕΚΦΩΝΗΣΗ:

Ο αλγόριθμος της φυσαλίδας όπως διατυπώθηκε στην παράγραφο 3.7 έχει το μειονέκτημα ότι δεν είναι αρκετά “έξυπνος” ώστε να διαπιστώνει στην αρχή ή στο μέσο της διαδικασίας αν ο πίνακας είναι ταξινομημένος. Να σχεδιασθεί μία παραλλαγή του αλγορίθμου αυτού που να σταματά όταν διαπιστωθεί ότι τα στοιχεία του πίνακα είναι ήδη ταξινομημένα. Υπόδειξη: Να χρησιμοποιήσετε μία βοηθητική μεταβλητή που να ελέγχει το τέλος κάθε επανάληψης του εξωτερικού βρόχου (“Για i από 2 μέχρι n”) αν για την τρέχουσα τιμή του i έγιναν αντιμεταθέσεις στοιχείων.

ΛΥΣΗ:

Η εκφώνηση ουσιαστικά αναφέρεται στην παραλλαγή της ταξινόµησης φυσαλίδας που αντιλαµβάνεται πότε ο πίνακας έχει ουσιαστικά ταξινοµηθεί και αποφεύγει τα περιττά περάσµατα (που σε συνολικό αριθµό είναι n-1). Αυτό επιτυγχάνεται µε τη βοήθεια µίας λογικής µεταβλητής, (µίας σηµαίας flag), που πριν κάθε πέρασµα αρχικοποιείται ως ψευδής και αλλάζει ως αληθής αν σε κάποιο πέρασµα γίνει έστω και µία ανταλλαγή. Έτσι, αν σε κάποιο πέρασµα δεν εκτελεσθεί καµία ανταλλαγή, τότε η σηµαία παραµένει ψευδής και αυτοµάτως τελειώνει ο αλγόριθµος.


ΠΡΟΓΡΑΜΜΑ Έξυπνη_Φυσαλίδα
ΣΤΑΘΕΡΕΣ
  n = 5
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: i, j, table[n], temp
  ΛΟΓΙΚΕΣ: flag
ΑΡΧΗ
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n
    ΔΙΑΒΑΣΕ table[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  flag <- ΑΛΗΘΗΣ
  i <- 2
  ΟΣΟ i <= n ΚΑΙ flag = ΑΛΗΘΗΣ ΕΠΑΝΑΛΑΒΕ
    flag <- ΨΕΥΔΗΣ
    
    ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ i ΜΕ ΒΗΜΑ -1
      ΑΝ table[j] < table[j - 1] ΤΟΤΕ
        temp <- table[j - 1] 
        table[j - 1] <- table[j] 
        table[j] <- temp

        flag <- ΑΛΗΘΗΣ      
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    i <- i + 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n
      ΓΡΑΨΕ table[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
 
Share This