Είναι ο πίνακας ταξινομημένος;

Ας υποθέσουμε ότι μας δίνουνε έναν πίνακα, π.χ. 10 θέσεων και μας ζητάνε να βρούμε αν ο πίνακας αυτός είναι ταξινομημένος ή όχι, π.χ. σε αύξουσα διάταξη.

Για να προκύψει το συμπέρασμα, θα πρέπει να ελέγξουμε τα διαδοχικά στοιχεία του πίνακα. Δηλαδή, το 1ο με το 2ο, το 2ο με το 3ο, το 3ο με το 4ο κ.ο.κ. Για να είναι ο πίνακας ταξινομημένος σε αύξουσα διάταξη θα πρέπει κάθε προηγούμενο στοιχείο να είναι μικρότερο από κάθε επόμενο. Δηλαδή, το i στοιχείο του πίνακα να είναι μικρότερο από το i+1. Προφανώς, αν βρούμε έστω κι ένα ζεύγος διαδοχικών στοιχείων για το οποίο να μην ισχύει το παραπάνω, τότε ο πίνακας δεν είναι ταξινομημένος, οπότε δεν υπάρχει λόγος να συνεχίσουμε. Ο αριθμός των συγκρίσεων που θα κάνουμε θα είναι το πολύ όσο το μέγεθος του πίνακα μείον ένα. (π.χ για τον πίνακα 10 θέσεων που προαναφέραμε θα κάνουμε το πολύ 10 συγκρίσεις).

Θα εφαρμόσουμε σειριακή αναζήτηση για να βρούμε κάποιο στοιχείο i που να είναι μεγαλύτερο από το i+1. Αν βρούμε κάποιο τέτοιο τότε προφανως ο πίνακας ΔΕΝ είναι ταξινομημένος.
Ας δούμε τον αλγόριθμο:

Αλγόριθμος Είναι_ταξινομημένος
   Δεδομένα //Α//
   βρέθηκε <- ΨΕΥΔΗΣ
   i <- 1
   Όσο i <= 9 ΚΑΙ βρέθηκε = ΨΕΥΔΗΣ επανάλαβε !το i είναι μέχρι 9 γιατί ψάχνω μέχρι το i+1=10
      Αν Α[i] > Α[i+1] τότε
         βρέθηκε <- ΑΛΗΘΗΣ
      Αλλιώς
         i <- i + 1
      Τέλος_αν
   Τέλος_επανάληψης
 
   Αν βρέθηκε = ΑΛΗΘΗΣ τότε
      Εμφάνισε "Ο πίνακας δεν είναι ταξινομημένος σε αύξουσα σειρά"
   Αλλιώς
      Εμφάνισε "Ο πίνακας είναι ταξινομημένος σε αύξουσα σειρά"
   Τέλος_αν
Τέλος Είναι_ταξινομημένος

6 σχόλια για το άρθρο “Είναι ο πίνακας ταξινομημένος;

  • 05/01/2013 at 16:01
    Permalink

    καλή άσκηση!!!
    εγω σκεφτηκα αυτη τη λυση

    Αλγόριθμος Ασκ
    Για ι από 1 μεχρι 10
    Διαβασε Π[ι]
    Τέλος_επανάληψης
    χ← Αληθής
    Για i απο 2 μεχρι 10
    Για j απο 10 μεχρι i με_βήμα -1
    Αν Π[j-1]>Π[j] τότε
    χ← Ψευδής
    Τέλος_αν
    Τέλος_επανάληψης
    Τέλος_επανάληψης
    Αν χ=Αληθής τότε
    Εμφανισε «Ο πίνακας είναι ταξινομημένος»
    αλλιώς
    Εμφάνισε «Ο πίνακας δεν είναι ταξινομημένος»
    Τέλος_αν
    Τέλος Ασκ

  • 04/04/2013 at 22:26
    Permalink

    Αντώνη δεν νομίζω να χρειάζεται και δευτερη επανάληψη .. βασικά κοίτα μαθητής είμαι αλλά θεωρώ ότι η δεύτερη επάναληψη δεν είναι λάθος αλλά το μόνο που θα καταφέρει είναι να κου΄ρασει τον υπολόγιστή (όχι ότι θα κουράστει κάνονταςμ ια επάνααληψη αντί για 10 100 φορές αλλά πιστευω ότι δεν είναι βέλτιστη λύση .. Τέλος πάντων εμένα μου φάνηκε εύκολη μπορστά σε κάτι άλλα μεγαθήρια που έχω λύση

  • 07/04/2014 at 14:02
    Permalink

    Παιδιά εντάξει, πλέον το επίπεδο δεν έχει καμία σχέση με κάτι τέτοιες μικροασκήσεις.. Άποψη μου είναι πως αν δεν σας έβγαινε η λύση «λογικά» στον εγκέφαλο ,στο συγκεκριμένο πρόβλημα, χωρίς εντολές και ψευδογλώσσες, τότε καλύτερα να βάλετε την φαντασία σας και την λογική σας σε λειτουργία!

Αφήστε μια απάντηση

Η ηλ. διεύθυνσή σας δεν δημοσιεύεται. Τα υποχρεωτικά πεδία σημειώνονται με *