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

[xristina]

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


ευχαριστώ

[P.Tsiotakis]

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

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

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

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

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

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

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

[evry]

Απλά σκέψου ότι έχεις ένα δυο διατάσεων πίνακα όπου η i-οστή στήλη είναι ο μονοδιάστατος πίνακας στο i-οστό βήμα της ταξινόμησης

[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]
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης

Το κ προφανώς αναφέρεται στα περάσματα του πίνακα, ενώ το λ στις ανά δύο συγκρίσεις που πρέπει να γίνουν σε κάθε πέρασμα.

[nikolasmer]

Γειά σε όλους.
1. Στο προηγούμενο μήνυμα του κυρίου Δημήτρη Δαλαγιώργου δεν βλέπω τίποτα ή μάλλον τα "βλέπω" ακαταλαβίστικα. Είμαι μόνο εγώ ή είναι και άλλοι;
2. Επίσης το παρακάτω τμήμα αλγορίθμου τί ακριβώς κάνει (Πίνακας Ν στοιχείων); Ταξινόμηση ή αναδιάταξη των στοιχείων;

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

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

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

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

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

[nikolasmer]

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

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

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

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

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

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

[nikolasmer]

Τώρα είδα το link. Κύριε Δουκάκη ευχαριστώ πολύ. Θα το κοιτάξω. 

[tryfonos]

Γειά σε όλους.
1. Στο προηγούμενο μήνυμα του κυρίου Δημήτρη Δαλαγιώργου δεν βλέπω τίποτα ή μάλλον τα "βλέπω" ακαταλαβίστικα. Είμαι μόνο εγώ ή είναι και άλλοι;
2. Επίσης το παρακάτω τμήμα αλγορίθμου τί ακριβώς κάνει (Πίνακας Ν στοιχείων); Ταξινόμηση ή αναδιάταξη των στοιχείων;

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

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

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

[nikolasmer]

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

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

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

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

Μπράβο στη συνάδελφο.