Ταξινόμηση Φυσαλίδας

Ξεκίνησε από xristina, 19 Ιαν 2006, 10:31:33 ΠΜ

« προηγούμενο - επόμενο »

xristina

μήπως θα μπορούσατε να μου εξηγήσετε στη μέθοδο ταξινόμησης φυσαλίδας τι είναι το i και τι το j ??
αφου ο πίνακας είναι μονοδιάστατος ?


ευχαριστώ

P.Tsiotakis


Όταν χρησιμοποιούνται δυο δομές επανάληψης Για για την επεξεργασία ενός πίνακα δεν σημαίνει απαραίτητα πως ο πίνακας αυτός είναι δισδιάστατος. Το είδος του πίνακα καθορίζεται αν θέλεις από το πλήθος των δεικτών που χρησιμοποιούνται εντός των αγκύλων !!

Κατ' αρχάς να ξεκαθαρίσουμε οτι ταξινόμηση μπορεί να γίνει μόνο σε μονοδιάστατο πίνακα (ή σε κάποια στήλη/γραμμή δισδιάστατου που όμως αποτελεί μονοδιάστατο πίνακα) !!

Στον αλγόριθμο ταξινόμησης της φυσσαλίδας χρησιμοποιούνται δυο δομές επανάληψης Για (δυο δείκτες) με το εξής σκεπτικό:

Ο δείκτης i σαρώνει τον πίνακα από πάνω προς τα κάτω και ο j από κάτω προς τα πάνω. Ο δείκτης j εξασφαλίζει την ανά δυο σύγκριση των στοιχείων του πίνακα με στόχο το μικρότερο σε κάθε σύγκριση στοιχείο να "ανεβαίνει" προς τα πάνω (όπως η φυσαλίδα στο νερό).

Ο δείκτης i δείχνει "μέχρι ποιο σημείο του πίνακα έχει ταξινομηθεί".

Εκτέλεσε τον αλγόριθμο με είσοδο τον πίνακα της παραγράφου 3.7 του σχολικού βιβλίου και μελέτησε βήμα-βήμα τις αλλαγές που πραγματοποιούνται, έχοντας στο μυαλό σου όσα περιέγραψα.

Ελπίζω να βοήθησα, με εκτίμηση,

evry

Απλά σκέψου ότι έχεις ένα δυο διατάσεων πίνακα όπου η i-οστή στήλη είναι ο μονοδιάστατος πίνακας στο i-οστό βήμα της ταξινόμησης
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

kyramas

Σε ότι αφαρά την ταξινόμηση πινάκων θέλω να παρατηρήσω τα εξής:
1)Οι πίνακες 2-διαστάσεων "κάθονται" στη μνήμη (που είναι μονοδιάστατη) σαν μονοδιάστατοι πίνακες δηλ. σε μια σειρά συνεχόμενων θέσεων μνήμης.
2) Οι πίνακες 2-διαστάσεων αποθηκεύονται κατά γραμμή στη μνήμη δηλ. Η 1η γραμμή στις πρώτες θέσεις μνήμης, ακολουθόύν τα στοιχεία της 2ης γραμμής κ.ο.κ
3) Ο συνηθισμένος τρόπος προσπέλασης των στοιχείων πίνακα 2-διαστάσεων είναι κατά γραμμή όπως και η "φυσική" του αποθήκευση και συνεπώς η εμφάνιση των στοιχείων με αυτό τον τρόπο σε ένα "συνολικά" ταξινομημένο πίνακα εμφανίζει όλα τα στοιχεία του πίνακα σε μια αύξουσα ή φθίνουσα σειρά.
3) Έχει λοιπόν νόημα να δούμε την ταξινόμηση πίνακα 2-διαστάσεων συνολικά και όχι μόνο κατά γραμμή ή στήλη.
έστω λοιπόν πίνακας Α[Ν,Μ]

ΠΛΗΘΟΣ<--Ν*Μ
ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ ΠΛΗΘΟΣ
    ΓΙΑ Κ ΑΠΟ ΠΛΗΘΟΣ ΜΕΧΡΙ Ι ΜΕ ΒΗΜΑ -1
       ΤΡ_ΓΡ<-- Κ div Μ + 1
       ΤΡ_ΣΤ<-- Κ mod Μ
       ΑΝ ΤΡ_ΣΤ=0 ΤΟΤΕ
         ΤΡ_ΣΤ<--Μ
         ΤΡ_ΓΡ<-- ΤΡ_ΓΡ-1
       ΤΕΛΟΣ_ΑΝ
       ΠΡ_ΓΡ<-- ΤΡ_ΓΡ
       ΠΡ_ΣΤ<-- ΤΡ_ΣΤ - 1
       ΑΝ ΠΡ_ΣΤ=0 ΤΟΤΕ
           ΠΡ_ΣΤ<--Μ
           ΠΡ_ΓΡ<--ΤΡ_ΓΡ - 1
       ΤΕΛΟΣ_ΑΝ
       ΑΝ Α[ΤΡ_ΓΡ, ΤΡ_ΣΤ] < Α[ΠΡ_ΓΡ,ΠΡ_ΣΤ] ΤΟΤΕ
          Τ<-- Α [ΠΡ_ΓΡ, ΠΡ_ΣΤ]
          Α[ΠΡ_ΓΡ, ΠΡ_ΣΤ]<-- Α[ΤΡ_ΓΡ, ΤΡ_ΣΤ]
          Α[ΤΡ_ΓΡ, ΤΡ_ΣΤ]<-- Τ
       ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

P.Tsiotakis


Αγαπητέ φίλε/η (μάλλον φίλε), είναι μεγάλη χαρά να βλέπουμε να συμμετέχουν νέα μέλη στο στέκι.

Ωστόσο, με όλο το σεβασμό προσωπικά θεωρώ οτι αυτά που αναφέρεις στις 3 πρώτες παρατηρήσεις είναι εκτός της φιλοσοφίας του μαθήματος ΑΕΠΠ. Είναι σωστά, αλλά όχι για το μαθημά μας

Ο αλγόριθμος ίσως να έχει κάποια πρακτική αξία σαν "σπαζοκεφαλιά" για ψαγμένους μαθητές, αλλά ... δεν μπορώ (προσωπικά) να αντιληφθώ τι μπορεί να προσφέρει...

Η άποψη αυτή δεν αναιρεί το σεβασμό που επιδεικνύω σε όλους τους συναδέλφους και τις διαφορετικές απόψεις...

Με εκτίμηση,

peterpan

ΜΙΑ ΑΛΛΗ ΑΝΤΙΜΕΤΩΠΙΣΗ (ΜΟΥ ΤΗΝ ΠΡΟΤΕΙΝΕ Ο ΓΙΟΣ ΜΟΥ) ΘΑ ΗΤΑΝ:
1.      Η ΜΕΤΑΤΡΟΠΗ ΤΟΥ ΔΙΣΔΙΑΣΤΑΤΟΥ ΠΙΝΑΚΑ ΜxΝ ΣΕ ΜΟΝΟΔΙΑΣΤΑΤΟ ΜΝ (ΣΧΕΔΟΝ ΟΛΑ ΤΑ ΕΞΩΣΧΟΛΙΚΑ ΒΙΒΛΙΑ ΑΝΑΦΕΡΟΥΝ ΤΕΤΟΙΑ ΠΕΡΙΠΤΩΣΗ)
2.      Η ΤΑΞΙΝΟΜΗΣΗ ΚΑΤΑ ΤΑ ΓΝΩΣΤΑ ΤΟΥ ΜΟΝΟΔΙΑΣΤΑΤΟΥ ΠΙΝΑΚΑ ΠΟΥ ΠΡΟΕΚΥΨΕ
3.      Η ΜΕΤΑΤΡΟΠΗ ΤΟΥ ΤΑΞΙΝΟΜΗΜΕΝΟΥ ΜΟΝΟΔΙΑΣΤΑΤΟΥ ΠΙΝΑΚΑ ΣΕ ΔΙΣΔΙΑΣΤΑΤΟ ΞΑΝΑ.
ΕΤΣΙ ΜΠΡΟΥΜΕ ΝΑ ΔΙΔΑΞΟΥΜΕ ΤΡΕΙΣ ΕΝΕΡΓΕΙΕΣ ΣΕ ΜΙΑ!!!

gpapargi

Ο Παναγιώτης κυρίως (και τα άλλα παιδιά) εξήγησαν το τι ακριβώς συμβαίνει με τους δείκτες. Δίνω και εγώ μια οπτική γωνία λίγο διαφορετική γιατί  βλέποντας περισσότερες από μια οπτικές γωνίες βοηθάει να καταλάβεις καλύτερα τα πράγματα. Τα ίδια λέω με άλλα λόγια.

Πες πως συγκρίνεις το τελευταίο στοιχείο με το προτελευταίο και αν το μικρότερο είναι από κάτω, τότε κάνεις αλλαγή και το βάζεις από πάνω. Στη συνέχεια συγκρίνεις το προτελευταίο (που ενδεχομένως να είναι αυτό που ανέβηκε από την προηγούμενη σύγκριση) με το αντί-προτελευταίο και βάζεις το μικρό από πάνω.

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

Αν επαναλάβεις τη διαδικασία (από κάτω κάτω μέχρι πάνω πάνω) θα δεις ότι το αποτέλεσμα είναι να έρθει το δεύτερο μικρότερο στοιχείο στη δεύτερη θέση. Παρατήρησε ότι η τελευταία σύγκριση (του δεύτερου με το πρώτο στοιχείο είναι περιττή).  Δεν πρόκειται να οδηγήσει σε ανταλλαγή γιατί το πρώτο στοιχείο είναι το μικρότερο όλου του πίνακα.

Πες πως επαναλαμβάνεις τη διαδικασία τόσες φορές όσα είναι τα στοιχεία του πίνακα. Θα καταλήξεις σε ένα πίνακα ταξινομημένο σε αύξουσα σειρά. Όμως θα έχεις κάνει πολλές περιττές συγκρίσεις. Ξέρεις ότι στην πρώτη σάρωση το μικρότερο στοιχείο θα βρεθεί στην πρώτη θέση. Στην δεύτερη σάρωση το δεύτερο μικρότερο στοιχείο θα βρεθεί στη δεύτερη θέση. . . στην ι σάρωση το ι μικρότερο στοιχείο θα βρεθεί στη ι θέση κλπ. Γιατί λοιπόν να κάνεις τη σάρωση μέχρι πάνω αφού ξέρεις ότι από τη ι θέση και πάνω οι συγκρίσεις είναι άσκοπες;

Βάζεις λοιπόν ένα δείκτη να σου δείχνει από πιο σημείο και πάνω οι συγκρίσεις είναι περιττές και κάνεις τις συγκρίσεις από εκεί και κάτω. Ο δείκτης i παίζει αυτό το ρόλο. Ο δείκτης j κάνει τη σάρωση. Σταματάει λοιπόν εκεί που είναι ο i.

Το λάθος που κάνεις στην ερώτηση σου είναι το εξής: Όταν έχεις πίνακα 2 διαστάσεων χρησιμοποιούμε 2 δείκτες (αφού θέλεις 2 αριθμούς για να γνωρίζουμε τη θέση κάποιου στοιχείου). Το αντίστροφο δεν ισχύει. Δηλαδή όταν έχεις 2 δείκτες, αυτό δε σημαίνει ότι σώνει και καλά έχεις πίνακα 2 διαστάσεων. Τα πάντα εξαρτώνται από τη δουλειά που θέλεις να κάνεις.

Είναι απαραίτητο να πάρεις συγκεκριμένα νούμερα και να ακολουθήσεις τον αλγόριθμο γραμμή γραμμή και θα δεις τι ακριβώς κάνει.

Δημήτρης Δαλαγιώργος

Γιατί δε διδάσκουμε αυτή την εκδοχή του αλγορίθμου;

Κώδικας: ψευδογλώσσα
   
ΓΙΑ κ ΑΠΟ 1 ΜΕΧΡΙ Ν - 1
  ΓΙΑ λ ΑΠΟ 1 ΜΕΧΡΙ Ν - κ
    ΑΝ Π[λ] > Π[λ + 1] ΤΟΤΕ
        αντιμετάθεσε Π[λ], Π[λ+1]
     ΤΕΛΟΣ_ΑΝ
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 


η οποία προκύπτει πολύ φυσικά από αυτή την εκδοχή του αλγορίθμου:

Κώδικας: ψευδογλώσσα
Για κ από 1 μέχρι Ν-1
  Για λ από 1 μέχρι Ν-1
    Αν Π[λ]>Π[λ+1] τότε
      αντιμετάθεσε Π[λ], Π[λ+1]
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης


Το κ προφανώς αναφέρεται στα περάσματα του πίνακα, ενώ το λ στις ανά δύο συγκρίσεις που πρέπει να γίνουν σε κάθε πέρασμα.
Ενάντια στην ηλιθιότητα, ακόμα και οι θεοί, μάταια αγωνίζονται.
Friedrich Schiller

nikolasmer

Γειά σε όλους.
1. Στο προηγούμενο μήνυμα του κυρίου Δημήτρη Δαλαγιώργου δεν βλέπω τίποτα ή μάλλον τα "βλέπω" ακαταλαβίστικα. Είμαι μόνο εγώ ή είναι και άλλοι;
2. Επίσης το παρακάτω τμήμα αλγορίθμου τί ακριβώς κάνει (Πίνακας Ν στοιχείων); Ταξινόμηση ή αναδιάταξη των στοιχείων;
Για ι απο 1 μέχρι Ν-1
  Για ξ απο 1 μέχρι Ν-1
      Αν Π[ξ+1] < Π[ξ] τότε
           Αντιμετάθεσε Π[ξ+1], Π[ξ]
      Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης
Μερεντίτης Νικόλαος
Πληροφορικός

Σπύρος Δουκάκης

Ταξινόμηση κάνει...

Τι εννοείς με τον όρο αναδιάταξη στοιχείων;

Αν θες, δες και αυτό: http://wp.me/pykbG-c9

nikolasmer

Νόμισα οτι απλά κάνει μια αλλαγή στα στοιχεία του πίνακα.
Δηλαδή τα αλλάζει γενικά θέση. Αυτός ο τρόπος ταξινόμησης λοιπόν έχει ενα συγκεκριμένο όνομα;
Επίσης κάτι άλλο που θα ήθελα να ρωτήσω. Κάνει περιττές επαναλήψεις και αν ναι μπορώ να κάνω τον αλγόριθμο αυτό πιο "έξυπνο" έτσι ώστε να σταματάει όταν καταλάβει οτι τα στοιχεία έχουν ταξινομηθεί;
Και τέλος θα πώ μια χαζαμάρα. Σαν τρόπος είναι πιο εύκολος από τη φυσαλλίδα ή η φυσαλλίδα είναι ο πιο απλός και ταυτόχρονα ο λιγότερα αποδοτικός από αυτόν.

P.s: Σχετικά με το μήνυμα του Δαλαγιώργου εγώ έχω πρόβλημα;
Μερεντίτης Νικόλαος
Πληροφορικός

Σπύρος Δουκάκης

Δες αν θέλεις το άρθρο που σου πρότεινα στο προηγούμενο μνμ.

Θα σε καλύψει....

ΥΓ: Ούτε εγώ μπορώ να διαβάσω τον κώδικα του συναδέλφου...

nikolasmer

Τώρα είδα το link. Κύριε Δουκάκη ευχαριστώ πολύ. Θα το κοιτάξω.  :)
Μερεντίτης Νικόλαος
Πληροφορικός

tryfonos

Παράθεση από: nikolasmer στις 25 Ιαν 2014, 07:47:05 ΜΜ
Γειά σε όλους.
1. Στο προηγούμενο μήνυμα του κυρίου Δημήτρη Δαλαγιώργου δεν βλέπω τίποτα ή μάλλον τα "βλέπω" ακαταλαβίστικα. Είμαι μόνο εγώ ή είναι και άλλοι;
2. Επίσης το παρακάτω τμήμα αλγορίθμου τί ακριβώς κάνει (Πίνακας Ν στοιχείων); Ταξινόμηση ή αναδιάταξη των στοιχείων;
Για ι απο 1 μέχρι Ν-1
  Για ξ απο 1 μέχρι Ν-1
      Αν Π[ξ+1] < Π[ξ] τότε
           Αντιμετάθεσε Π[ξ+1], Π[ξ]
      Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης


Το κομμάτι του αλγορίθμου που έχεις γράψει δε δίνει το επιθυμητό αποτέλεσμα.
Προσπάθησε να κάνεις ένα μικρό παραδειγματάκι και θα καταλάβεις το λάθος σου.

Για ι απο 2 μέχρι Ν
  Για ξ απο Ν μέχρι ι με βήμα -1
      Αν Π[ξ] < Π[ξ-1] τότε
           Αντιμετάθεσε Π[ξ], Π[ξ-1]
      Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης [/code]
[/quote]

!ΑΥΞΟΥΣΑ ΤΑΞΙΝΟΜΗΣΗ

nikolasmer

Από μικροί παίζουν με τις φυσαλίδες. Πολύ καλό.

https://www.youtube.com/watch?v=Wv9m0WVCUbQ

Υπάρχουν και άλλα βίντεο στο διαδίκτυο αλλά το να βλέπεις και τις πρόβες των μικρών παιδιών  ;D  είναι τέλειο.

https://www.youtube.com/watch?v=W53N2NHwbCM

Μπράβο στη συνάδελφο.
Μερεντίτης Νικόλαος
Πληροφορικός

marvic

Καλησπέρα,
Μου τέθηκε ένα πολύ ωραίο ερώτημα όσον αφορά την ταξινόμηση ή μάλλον την σειρά θα έλεγα των ερωτημάτων..
Τί εννοώ..
Εάν για παράδειγμα σε μία άσκηση διαβάζω και δημιουργώ έναν μονοδιάστατο πίνακα πχ ονομάτων και έναν δισδιάστατο(παράλληλο ως προς τον μονοδιάστατο). Στο τελευταίο ερώτημα τις υποτιθέμενης άσκησης πρέπει να ταξινομήσω τον μονοδιάστατο με συσχέτιση τον δισδιάστατο(ή έστω τμήμα αυτού). το ερώτημα λοιπόν είναι:
Μπορώ να ταξινομήσω τον μονοδιάστατο με το που δοθεί(διαβαστεί) και έπειτα να διαβάσω τον δισδιάστατο και να εννοείταιι η συσχέτιση?

itt

Παράθεση από: marvic στις 09 Φεβ 2016, 06:43:42 ΜΜ
Καλησπέρα,
Μου τέθηκε ένα πολύ ωραίο ερώτημα όσον αφορά την ταξινόμηση ή μάλλον την σειρά θα έλεγα των ερωτημάτων..
Τί εννοώ..
Εάν για παράδειγμα σε μία άσκηση διαβάζω και δημιουργώ έναν μονοδιάστατο πίνακα πχ ονομάτων και έναν δισδιάστατο(παράλληλο ως προς τον μονοδιάστατο). Στο τελευταίο ερώτημα τις υποτιθέμενης άσκησης πρέπει να ταξινομήσω τον μονοδιάστατο με συσχέτιση τον δισδιάστατο(ή έστω τμήμα αυτού). το ερώτημα λοιπόν είναι:
Μπορώ να ταξινομήσω τον μονοδιάστατο με το που δοθεί(διαβαστεί) και έπειτα να διαβάσω τον δισδιάστατο και να εννοείταιι η συσχέτιση?

Ο δισδιάστατος πίνακας που σου δίνεται ως input είναι παράλληλος ως προς το μονοδιάστατο πίνακα που σου δίνεται ως input. Άμα ταξινομήσεις τον μονοδιάστατο πριν διαβάσεις τον δισδιάστατο θα πρέπει να σου δοθεί ως input ο δισδιάστατος ταξινομήμενος (ως προς τον μονοδιάστατο) , το οποίο δεν έχει νόημα. Είναι ισοδύναμο με το να πεις "έστω ότι το input μου είναι ταξινομήμενο" σε άσκηση που σου ζητάει να διαβάσεις στοιχεία, να τα βάλεις σε πίνακα και να τα ταξινομήσεις.

alkisg

Παράθεση από: marvic στις 09 Φεβ 2016, 06:43:42 ΜΜ
Μπορώ να ταξινομήσω τον μονοδιάστατο με το που δοθεί(διαβαστεί) και έπειτα να διαβάσω τον δισδιάστατο και να εννοείται η συσχέτιση?

Μπορεί να γίνει κάτι αντίστοιχο, αλλά μου ακούγεται πολύ προχωρημένο για να διδαχτεί σε Λύκειο...
Έστω ότι διαβάζεις τον πίνακα ονομάτων με τα εξής 5 στοιχεία: Ε Α Δ Γ Β
Και τον ταξινομείς σε: Α Β Γ Δ Ε
Αν την ώρα της ταξινόμησης έφτιαχνες και έναν παράλληλο πίνακα θέσεων: 5 1 4 3 2
...ο οποίος αντιστοιχεί τον αταξινόμητο πίνακα Ε Α Δ Γ Β στον ταξινομημένο Α Β Γ Δ Ε
τότε στη συνέχεια θα μπορούσες να διαβάσεις κι άλλους "παράλληλους" πίνακες κατευθείαν στις ταξινομημένες θέσεις τους, δίνοντας
Κώδικας: ΓΛΩΣΣΑ
Για ι από 1 μέχρι 5
    Διάβασε Επώνυμα[Ταξινομημένες_θέσεις[ι]]
Τέλος_επανάληψης

και έτσι αν τα Επώνυμα ήταν π.χ. e a d c b
τότε θα έμπαιναν άμεσα στον πίνακα Επώνυμα ως a b c d e χωρίς να ξαναχρειαστεί ταξινόμηση.

itt

Παράθεση από: alkisg στις 10 Φεβ 2016, 08:57:58 ΠΜ
Μπορεί να γίνει κάτι αντίστοιχο, αλλά μου ακούγεται πολύ προχωρημένο για να διδαχτεί σε Λύκειο...
Έστω ότι διαβάζεις τον πίνακα ονομάτων με τα εξής 5 στοιχεία: Ε Α Δ Γ Β
Και τον ταξινομείς σε: Α Β Γ Δ Ε
Αν την ώρα της ταξινόμησης έφτιαχνες και έναν παράλληλο πίνακα θέσεων: 5 1 4 3 2
...ο οποίος αντιστοιχεί τον αταξινόμητο πίνακα Ε Α Δ Γ Β στον ταξινομημένο Α Β Γ Δ Ε
τότε στη συνέχεια θα μπορούσες να διαβάσεις κι άλλους "παράλληλους" πίνακες κατευθείαν στις ταξινομημένες θέσεις τους, δίνοντας
Κώδικας: ΓΛΩΣΣΑ
Για ι από 1 μέχρι 5
    Διάβασε Επώνυμα[Ταξινομημένες_θέσεις[ι]]
Τέλος_επανάληψης

και έτσι αν τα Επώνυμα ήταν π.χ. e a d c b
τότε θα έμπαιναν άμεσα στον πίνακα Επώνυμα ως a b c d e χωρίς να ξαναχρειαστεί ταξινόμηση.

Στο οποίο και πάλι βέβαια δεν "εννοείται" η συσχέτιση, την καταγράφεις explicitly στον ενδιάμεσο πίνακα με τις συνδέσεις.

marvic

Σας ευχαριστώ πολύ για τις απαντήσεις σας! Ήταν βοηθητικές!!
:)