Θέμα: Quicksort-Selection Sort

[ge0_]

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


ευχαριστώ προκαταβολικά...

[gthal]

Δες εδώ  http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
έχει όλες τις μεθόδους και ένα μικρό demo για το πώς και πόσο γρήγορα δουλεύει καθεμιά
Αν κάνεις κλικ στον τίτλο κάθε μεθόδου, σου δείχνει τον κώδικα
Δεν είναι βέβαια ψευδογλώσσα αλλά ίσως είναι εύκολο να τα "μεταφράσεις".
Αν χρειαστείς κάποια βοήθεια, σφύριξε πάλι.

[Sergio]

Ίσως θα ήταν σκόπιμο να δοκιμάσεις να τους υλοποιήσεις και μόνος σου ξεκινόντας από τον αλγόριθμο για ταξινόμηση με επιλογή.

Είναι ίσως ο πιό φυσικός αλγόριθμος ταξινόμησης, αυτός που θα ακολουθούσε κανείς ενστικτωδώς για να ταξινομήσει "με το χέρι"

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

Τι λες, δεν το προσπαθείς;


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

και συνεχίζουμε με τον quicksort

[ge0_]

..........

[gthal]

χμμ υπάρχουν αρκετά λαθάκια.
το έτρεξες εδώ www.pseudoglossa.gr ;
δώσε έναν πίνακα με 10 στοιχεία να δεις, τον ταξινομεί; χρησιμοποίησε και τη βηματική εκτέλεση να δεις τι συμβαίνει.
πρόσεξε κυρίως την αρχικοποίηση του max

Γενικά, αυτό που θες να κάνεις είναι:
βρες το μεγαλύτερο στοιχείο του πίνακα και αντάλλαξέ το με το πρώτο στοιχείο (ξέρεις να βρίσκεις max, υποθέτω)
κάνε το ίδιο (βρες πάλι το max), τώρα στο τμήμα του πίνακα από τη 2η θέση και κάτω (αφού στην 1η έχεις βάλει το μεγαλύτερο στοιχείο) και αντάλλαξέ το με το 2ο στοιχείο του πίνακα
μετά κάνε το ίδιο στο τμήμα του πίνακα από την 3η θέση και κάτω και και αντάλλαξέ το με το 3ο στοιχείο του πίνακα
κοκ μέχρι να φτάσεις να κάνεις το ίδιο στο τμήμα του πίνακα από την προτελευταία θέση και κάτω.

[ge0_]

.............

[Sergio]

Μπράβο..

Καλή προσπάθεια!!

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

Όπως σωστά σου είπε και ο Γιώργος:

το έτρεξες εδώ www.pseudoglossa.gr ;
δώσε έναν πίνακα με 10 στοιχεία να δεις, τον ταξινομεί; χρησιμοποίησε και τη βηματική εκτέλεση να δεις τι συμβαίνει.

Έτσι θα εντοπίσεις εύκολα τα σημεία του αλγόριθμού σου που παρουσιάζουν πρόβλημα..

Επειδή η εισαγωγή στοιχείων πίνακα είναι λίγο δύσκολη στο pseudoglossa.gr, μπορείς να το δοκιμάσεις και στο διερμηνευτή του Άλκη και να χρησιμοποιήσεις την καρτέλα αρχείο εισόδου ώστε να μη χρειάζεται να περνάς την ταλαιπωρία της εισαγωγής των δεδομένων εισόδου ξανά και ξανά όσο ελέγχεις - διορθώνεις τον αλγόριθμό σου..

Στο θέμα μας τώρα .. αν προσπαθείς να υλοποιήσεις τη λογική που περιέγραψα παραπάνω, δεν τα πας και άσχημα..  Όμως υπάρχουν λαθάκια λογικής..

Για παράδειγμα..
Η εύρεση του ΜΑΧ δε γίνεται με το σωστό τρόπο.. Η συνθήκη
     Αν ΠΙΝ[j]>ΠΙΝ[j-1] τότε μαχ [ i ]<---ΠΙΝ[j]
δεν είναι σωστή.. Σκέψου τι θα βρει ως ΜΑΧ αν τα στοιχεία είναι τα :  2, 15, 7, 8, 10
Όλοι περιμένουμε να βρει το 15.  Όμως, ενώ με την πρώτη σύγκριση (15 > 2) θα δείξει να το καταφέρνει, και η δεύτερη (7 > 15) δε θα το .. χαλάσει, Η ΤΡΙΤΗ (8>7) θα «θεωρήσει» ως ΜΑΧ το 8 και η τελευταία (10>8 ), θα βγάλει τελικά «νικητή» το 10 Έπειτα, το γεγονός ότι ο εσωτερικός βρόχος (αυτός που εξετάζει τα στοιχεία του αρχικού πίνακα) ξεκινάει κάθε φορά από μία θέση "παρακάτω", σημαίνει ότι κάθε φορά εξαιρεί από την εξέταση ένα επιπλέον στοιχείο του αρχικού πίνακα.  Φαντάζομαι προσπαθείς να εξαιρέσεις τo στοιχείo που έχει ήδη μπει στο νέο.. Δεν κάνεις αυτό όμως.. Εξαιρείς το πρώτο στοιχείο που εξετάστηκε στο προηγούμενο πέρασμα.  Αυτό όμως δεν είναι σίγουρα το στοιχείο που επιλέγηκε τελικά ως μέγιστο σε αυτό το «πέρασμα»!.  Επομένως, συμβαίνουν δύο λάθη: α. εξαιρείς ένα στοιχείο που (ίσως) δεν πρέπει β. ξαναεξετάζεις (ίσως) το στοιχείο που τελικά επιλέγηκε.

Για παράδειγμα.. Αν ο πίνακάς σου αρχικά είχε τα: 7, 15, 2, 3, 4
και θεωρήσουμε ότι η εύρεση του ΜΑΧ είχε γίνε σωστά.. το πρώτο που θα είχες βρει (εξετάζοντας όλα τα στοιχεία) θα ήταν το 15..  Στο επόμενο πέρασμα όμως, ΔΕΝ θα εξετάσεις το 7 (που είναι και το ..νέο μέγιστο) ενώ θα ΞΑΝΑεξετάσεις το 15 (που ήθελες να εξαιρέσεις).. και άλλα μικρά διάφορα τα οποία πιθανόν να εντόπιζες και να διόρθωνες αν «έτρεχες» τον αλγόριθμο με το χέρι ή με τη βοήθεια του pseudoglossa ή του Διερμηνευτή..

Απ' ότι καταλαβαίνω, προσπαθείς να δημιουργήσεις, από τον πίνακα ΠΙΝ, τον πίνακα ΜΑΧ που θα έχει τα ίδια στοιχεία (με τον ΠΙΝ), όμως με τη σωστή σειρά..  Κάτι σαν:

Κώδικας: [Επιλογή]

Αλγόριθμος Ταξινόμηση_Επιλογής
Δεδομένα // ΠΙΝ, Ν//

ΓΙΑ κάθε θέση του ΜΑΧ
   Βρες το μεγαλύτερο στοιχείο του ΠΙΝ που ΔΕΝ έχει εισαχθεί στον ΜΑΧ
   Βάλε το στον ΜΑΧ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Αποτελέσματα //ΜΑΧ//
Τέλος Ταξινόμηση_Επιλογής
Η δυσκολία βρίσκεται στο βήμα: «..Βρες το μεγαλύτερο στοιχείο του ΠΙΝ που ΔΕΝ έχει εισαχθεί στον ΜΑΧ..»

Ένας τρόπος θα ήταν να ελέγξεις αν υπάρχει ήδη στον ΜΑΧ.. Αυτό μπορείς να το κάνεις με μία σειριακή αναζήτηση (του στοιχείου που εξετάζεις) στον πίνακα ΜΑΧ.. Σκέψου όμως ότι η ίδια τιμή μπορεί να υπάρχει περισσότερες από μία φορές στον ΠΙΝ.. Σε αυτή την περίπτωση, θα την έβρισκες στον ΜΑΧ οπότε ΔΕΝ θα την έβαζες !!  Αυτό θα ήταν χρήσιμο εάν το προσπαθούσες να βάλεις όλες τις τιμές από μία φορά.. όμως δεν είναι αυτό το ζητούμενο εδώ.. ΟΛΕΣ οι τιμές πρέπει να περιέχονται στον ΜΑΧ.. Και αν μία τιμή υπάρχει 2 ή και περισσότερες φορές, θα πρέπει να μπει στον ΜΑΧ όλες τις φορές.  Απλά θα είναι όλες οι τιμές δίπλα-δίπλα στο νέο, ταξινομημένο, πίνακα.  Επομένως θα πρέπει να σκεφτείς άλλο τρόπο για να ελέγξεις αν η τιμή (του ΠΙΝ) που εξετάζεις έχει ήδη μπει στον ΜΑΧ..

Θα μπορούσες λοιπόν να «σημειώνεις» για κάθε τιμή του ΠΙΝ εάν έχει μπει στον ΜΑΧ.  Αυτό μπορεί να γίνει με έναν «παράλληλο» πίνακα με σημαίες (πίνακα λογικών τιμών), για παράδειγμα Μπήκε[Ν]!!

Για κάθε τιμή του ΠΙΝ που επιλέγεται να μπει στον ΜΑΧ, σημειώνεται μπήκε της ως ΑΛΗΘΗΣ.  Έτσι θα μπορούσες να αποφύγεις να την ξαναεξετάσεις.. (Αν μπήκε[ αυτό ] = ΨΕΥΔΗΣ ΚΑΙ ΠΙΝ[ αυτό ] > μέγιστο ΤΟΤΕ μέγιστο <- ΠΙΝ[ αυτό ])

Όταν τελικά βρεθεί το μέγιστο, αφού το βάλεις στο νέο πίνακα.. σηκώνεις και τη σημαία του ώστε την ..επόμενη φορά να μην το ξαναεξετάσεις (μπήκε[το_μέγιστο] <- ΑΛΗΘΗΣ).. Φαντάζομαι καταλαβαίνεις πως για να γίνει αυτό θα πρέπει να «θυμάσαι» τη θέση του

Μία ακόμα δυσκολία είναι το πώς θα κάνεις την αρχικοκοποίηση στο μηχανισμό εύρεσης του μέγιστου.. Συνήθως ως αρχική τιμή δίνουμε το πρώτο στοιχείο του πίνακα και στη συνέχεια εξετάζουμε τα υπόλοιπα.  Όπως έχει όμως εδώ η κατάσταση, το πρώτο στοιχείο του πίνακα μπορεί να έχει ήδη εισαχθεί.. Θα πρέπει λοιπόν να εντοπίσεις το πρώτο στοιχείο που ΔΕΝ έχει εισαχθεί και με αυτό να κάνεις την αρχικοποίηση !!  Αυτό γίνεται αρκετά εύκολα αφού έχεις τις «σημαίες»

Τι λες.. δεν το ξαναπροσπαθείς;  Τη λύση που σου περιγράφω την έχω ήδη κωδικοποιήσει και ελέγξει με το pseudoglossa.gr οπότε μπορώ να την αναρτήσω εδώ εάν χρειαστεί, όμως πραγματικά πιστεύω πως αν το καταφέρεις μόνος σου θα κερδίσεις πολλλλλλλλαπλά !!

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

Έτσι το κέρδος σου θα είναι ΔΙΠΛΟ

Εξάλλου, μόλις καταφέρεις να κάνεις την ιδέα σου αλγόριθμο, θα διαπιστώσεις ότι:
1. έχεις κάνει αλγόριθμο, ΑΚΡΙΒΩΣ αυτό που θα έκανες στην πράξη και με .. το χέρι και
2. έχεις αφήσει τον αρχικό πίνακα στην κατάσταση που ήταν


Αντε.. give it a go !!

[sstergou]

Επειδή η εισαγωγή στοιχείων πίνακα είναι λίγο δύσκολη στο pseudoglossa.gr...

Καρτέλα με το αρχείο εισόδου υπάρχει και στο pseudoglossa.gr ( και μάλιστα δουλεύει και με την εντολή "Δεδομένα")/

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

Σχετικές επιλογές υπάρχουν στο παράθυρο των ρυθμίσεων.

Υ.Γ.
Λείπει η τεκμηρίωση, το ξέρω

[gthal]

Απ' ότι καταλαβαίνω, προσπαθείς να δημιουργήσεις, από τον πίνακα ΠΙΝ, τον πίνακα ΜΑΧ που θα έχει τα ίδια στοιχεία (με τον ΠΙΝ), όμως με τη σωστή σειρά.. 

Α, σωστά! Προσπαθεί να φτιάξει πίνακα ΜΑΧ !!!
Αυτό δεν το φαντάστηκα καθόλου 

[ge0_]

Λοιπόν νομίζω το βρήκα (τουλάχιστον για διαφορετικά στοιχεία)...

x<---1
Για i από 1 μέχρι Ν
max(i)<---ΠΙΝ(i)
  Για j από χ μέχρι Ν
     Αν ΠΙΝ(j) > max(i) τότε
      max(i)<---ΠΙΝ(j)
      pos<---j
    Τέλος_αν
 Τέλος_επανάληψης
ΠΙΝ(pos)<---ΠΙΝ(x)
ΠΙΝ(x)<---max(i)
x<---x+1
Tέλος_επανάληψης


πήρα έναν υποθετικό πίνακα με στοιχεία 2,9,7,6 και δούλεψε! από κει και πέρα δεν ξέρω....έκανα την προσπάθειά μου

[petrosp13]

To max γιατί να είναι πίνακας;
Την μεταβλητή χ γιατί δεν την αντικαθιστάς με το i;

Είσαι σχεδόν τέλειος, συγχαρητήρια!

[Sergio]

Πολύ καλή δουλειά ge0_

Συγχαρητήρια

Βρήκες μόνος σου τον τρόπο να "βγάζεις απ' τη μέση" αυτά που "τακτοποιείς"..  Απλά τα ανεβάζεις στην κορυφή του πίνακά σου και δεν ξανα-ασχολείσαι !!

Και όπως σου είπε και ο Πέτρος, με τον τρόπο που το έλυσες, δεν έχεις λόγο να χρησιμοποιείς το χ, αφού έχει πάντα την ίδια τιμή με το ι.. οπότε ο κώδικας "ελαφραίνει" κάπως..

Για i από 1 μέχρι Ν
    max(i)<---ΠΙΝ(i)
    Για j από i μέχρι Ν
       Αν ΠΙΝ(j) > max(i) τότε
         max(i)<---ΠΙΝ(j)
         pos<---j
      Τέλος_αν
    Τέλος_επανάληψης
    ΠΙΝ(pos)<---ΠΙΝ(i)
    ΠΙΝ(i)<---max(i)
Tέλος_επανάληψης

Επίσης, η ..τελευταία.. εντολή του βρόχου (ΠΙΝ(i)<---max(i)) αποκαλύπτει πως .. τελικά, οι δύο πίνακες (ο αρχικός ΠΙΝ και ο νέος ΜΑΧ) καταλήγουν να έχουν τα .. ίδια στοιχεία   Οπότε, έχει δίκαιο και στο δεύτερο ο Πέτρος.. Ο ΜΑΧ δεν έχει λόγο να είναι πίνακας.. Χρησιμεύει μόνο για την αντιμετάθεση του ΠΙΝ(pos) με το ΠΙΝ(i)   Θα μπορούσε να είναι απλή μεταβλητή !!  Υπάρχει βέβαια ένα μικρό λαθάκι.. Αν τελικά το ΠΙΝ(i) τύχει και είναι το μεγαλύτερο;; Θα έχεις "ακαθόριστο" pos.. οπότε πρέπει να προσθέσεις και μία αρχικοποίηση στο Pos

Οπότε:

Για i από 1 μέχρι Ν
    max<---ΠΙΝ(i)
    pos <- i
    Για j από i μέχρι Ν
       Αν ΠΙΝ(j) > max τότε
         max<---ΠΙΝ(j)
         pos<---j
      Τέλος_αν
    Τέλος_επανάληψης
    ΠΙΝ(pos)<---ΠΙΝ(i)
    ΠΙΝ(i)<---max
Tέλος_επανάληψης

Και, δεν έχεις δίκαιο, ο αλγόριθμός σου θα δουλέψει σωστά ΚΑΙ για ίσες τιμές.. ΓΙΑΤΙ ΟΧΙ ;;  Μιααα χαααρά είναι!!

Μάλλον κάπου σε έμπλεξα εγώ τελικά μιλώντας για νέο πίνακα.. Εσύ υλοποίησες άριστα τον αλγόριθμο όπως ακριβώς τον περιέγραψε και ο Γιώργος

Γενικά, αυτό που θες να κάνεις είναι:
βρες το μεγαλύτερο στοιχείο του πίνακα και αντάλλαξέ το με το πρώτο στοιχείο (ξέρεις να βρίσκεις max, υποθέτω)
κάνε το ίδιο (βρες πάλι το max), τώρα στο τμήμα του πίνακα από τη 2η θέση και κάτω (αφού στην 1η έχεις βάλει το μεγαλύτερο στοιχείο) και αντάλλαξέ το με το 2ο στοιχείο του πίνακα
μετά κάνε το ίδιο στο τμήμα του πίνακα από την 3η θέση και κάτω και και αντάλλαξέ το με το 3ο στοιχείο του πίνακα
κοκ μέχρι να φτάσεις να κάνεις το ίδιο στο τμήμα του πίνακα από την προτελευταία θέση και κάτω.

Με μικροβελτιώσεις θα μπορούσε απλά να είναι:

Για i από 1 μέχρι Ν-1
    pos <- i
    Για j από i+1 μέχρι Ν
       Αν ΠΙΝ(j) > ΠΙΝ(pos) τότε
         pos<---j
      Τέλος_αν
    Τέλος_επανάληψης
    Αντιμετάθεσε ΠΙΝ(ι), ΠΙΝ(pos)
Tέλος_επανάληψης

Η λύση που σου "πρότεινα" σε προηγούμενο post έξυπηρετούσε μόνο ένα σκοπό: να μιμηθεί αυτό που θα έκανες "με το χέρι", δηλαδή να δημιουργήσεις νέο πίνακα στον οποίο να βάλεις τα στοιχεία με τη σωστή σειρά, χωρίς να πειράξεις τον αρχικό.  Για την ιστορία, παραθέτω τη λύση στη συνέχεια:

Κώδικας: [Επιλογή]

Αλγόριθμος Ταξινόμηση_Επιλογής
Δεδομένα //Ν, ΠΙΝ//

!Κανένα δεν έχει μπει ακόμα .. ΑΡΧΗ είναι :)
ΓΙΑ i από 1 μέχρι Ν
  μπήκε[ i ] ←  ΨΕΥΔΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΓΙΑ i από 1 ΜΕΧΡΙ Ν

! Βρές το πρώτο που δεν έχει μπεί στο νέο πίνακα
   j ←  1
   ΌΣΟ j ≤ Ν και μπήκε[j] = ΑΛΗΘΗΣ ΕΠΑΝΑΛΑΒΕ
      j ←  j + 1
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

! Αρχικοποίησε με αυτό το MAX σου
   ΜΑΧ[ i ] ←  ΠΙΝ[j]
   θέση ←  j

! Βρες το μέγιστο από όσα έχουν μείνει
   ΓΙΑ j ΑΠΟ θέση + 1 ΜΕΧΡΙ Ν
      ΑΝ ΠΙΝ[j] > ΜΑΧ[ i ] ΚΑΙ μπήκε[ j ]=ΨΕΥΔΗΣ ΤΟΤΕ
         ΜΑΧ[ i ] ←  ΠΙΝ[j]
         θέση ←  j
      ΤΕΛΟΣ_ΑΝ
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

! αυτό .. ΜΠΗΚΕ
   μπήκε[θέση] ← ΑΛΗΘΗΣ

! πάμε για τα υπόλοιπα..
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Αποτελέσματα //ΜΑΧ//
Τέλος Ταξινόμηση_Επιλογής

Συνέχισε την καλή δουλειά !