Star_Light Δημοσ. 3 Μαΐου 2012 Δημοσ. 3 Μαΐου 2012 Στην Σελ. 206 του King έχει ενα καλο παράδειγμα σχετικα με το 1ο μονο ομως βήμα του αλγοριθμου. Το καταλαβα αυτο , ηταν πολυ ευκολο μετα μπερδευτηκα ομως. Έψαξα και άλλες πηγες http://www.piperies.gr/posts/o-xoros-quicksort και http://www.mycstutorials.com/articles/sorting/quicksort στο 2ο δεν καταλαβαινω οταν φτανει στο σημειο -> > 3 1 2 5 9 4 8 7 Οπου ο ένας δείκτης (ο χαμηλος) βρισκεται στο 5 και ο αλλος στο 4 γιατι δεν κάνει την αντιμετάθεση? 4 5 και το αφηνει ως έχει? Αφου γινεται αντιμεταθεση κανονικα εκτος και αν το αριστερο ειναι μικροτερο απο το δεξι οπως εγινε στην περιπτωση της συγκρισης με το 4 και το 7 (αμα καποιος τον κανει trace στο χαρτι) και συνεχιζει μετα να διατρέχει μέχρι να βρει καποιο μικροτερο απο το pivot και σταματα τελικα στο 1 . Στο μεταξυ αυτο εδω στην αρχη -> 3 1 4 5 9 2 6 8 7 The search for the first large element continues rightwards. The value of i gets incremented as the search moves to the right. 3 1 4 5 9 2 6 8 7 Since 4 is greater than the pivot, the rightwards search stops here. Thus the value of i remains 2. δεν το γραφει στο αλλο βιβλιο του King πρωτη φορα το βλεπω... με λιγα λογια θελω να βρω πως δουλευει ο αλγοριθμος απο την αρχη ως το τελος.
Star_Light Δημοσ. 3 Μαΐου 2012 Μέλος Δημοσ. 3 Μαΐου 2012 Για δες κι αυτο που ανεβασα quicksort.pdf Θα το τσεκάρω. Αλλα ψαχνω κανενα απλο παραδειγματακι με 7-8 στοιχεια το πολυ. Ευχαριστω παντως Υ.Γ Ο King το εξηγει πολυ καλα αλλα δεν το συνεχιζει
ChRis6 Δημοσ. 4 Μαΐου 2012 Δημοσ. 4 Μαΐου 2012 Ο αλγοριθμος ειναι αναδρομικος και "γρηγορος¨ .Το ποσο γρηγορος βεβαια ειναι σχετικο,γιατι αν του δωσεις εναν πινακα που ειναι "αναποδα" ταξινομημενος, τοτε γινεται ΠΟΛΥ αργος. Σε καθε βημα του ενα στοιχειο "καθεται" στη σωστη ταξιμομημενη θεση. Αυτο το στοιχειο ονομαζεται στοιχειο διαχωρισμου. Σε καθε αναδρομικη κληση,ο πινακας σπαει σε 2 μερη ( αριστερο/δεξι) και επιλεγεται το στοιχειο διαχωρισμου(συνηθως ειναι το δεξιοτερο του υποπινακα , αλλα δεν ειναι δεσμευτικο) Αρχικα επιλεγεται ως στοιχειο διαχωρισμου το δεξιοτερο στοιχειο του πινακα. Εχοντας 2 δεικτες , τον i και j , ξεκινας τον i απο τα αριστερα μεχρι να βρεις ενα στοιχειο μεγαλυτερο του στοιχειου διαχωρισμου και τον j μεχρι να βρεις ενα μικροτερο . Οταν συμβει αυτο κανεις swap τα στοιχεια του πινακα i,j και συνεχιζεις το ιδιο μεχρι ο j να ξεπερασει τον i . Οταν ο j ξεπερασει τον i , τοτε κανεις swap το στοιχειο διαχωρισμου με το στοιχειο που δειχνει ο i.Επειτα "μαρκαρεις" τη θεση i ως "ταξινομημενη" και αναδρομικα κανεις το ιδιο πρωτα για το κομματι που βρισκεται στα αριστερα του i και μετα για το δεξι. Για το παραδειγμα που λες : Αν αρχικα εχεις : 3 1 2 5 9 4 8 7 το στοιχειο διαχωρισμου ειναι το 7. Ο i ξεκιναει απο το 3 και ο j απο το 8. O i σταματαει στο 9 και ο j στο 4 και γινεται swap και εχεις : 3 1 2 5 4 9 8 7 και συνεχιζεις το ιδιο. Ο i σταματαει παλι στο 9 και ο j στο 4 .Τωρα επειδη ο j "περασε" τον i κανεις swap το 7 με το 9 και συνεχιζεις αναδρομικα για το αριστερο κομματι. 3 1 2 5 4|7 8 9 δηλαδη το 3 1 2 5 4 . Αφοτου τελειωσεις με αυτο , τοτε κανεις τα ιδια παλι για το 7 8 9 ! Με παρομοιο τροπο μπορεις να βρεις ποιο ειναι π.χ το 5ο μεγαλυτερο στοιχειο του πινακα , αδιαφοροντας για τα υπολοιπα.Αυτο που αλλαζει στο παραπανω ειναι οτι "διαλεγεις" ποιο κομματι του πινακα σε βολευει σε καθε αναδρομικη κληση ( αριστερο / δεξι ). Σαν τη δυαδικη αναζητηση ας πουμε Ελπιζω να μην εχω γραψει καμια ΠΑΤΑΤΙΑ λογω της περασμενης ωρας και με παρουν με τις πετρες οι υπολοιποι
Star_Light Δημοσ. 4 Μαΐου 2012 Μέλος Δημοσ. 4 Μαΐου 2012 Λοιπον βρήκα ένα καλό στο youtube http://http://www.youtube.com/watch?v=Z5nSXTnD1I4 Δεν ξέρω γιατι αλλα δεν μ αρεσει ετσι οπως υλοποιει τον αλγοριθμο εδω -> http://www.mycstutorials.com/articles/sorting/quicksort εγω το έκανα "αλλιως" Αρχικά > 3 1 4 5 9 2 6 8 7 Σε αυτη την αταξινόμητη λίστα το 1ο στοιχείο ειναι το 3 στο οποίο μπαίνει ο δείκτης low ενω το τελευταίο ειναι το 7 στο οποίο μπαίνει ο δείκτης high (καμια σχέση με δεικτες στην C! ) Η λογικη έχει ως εξής . Το high θα κινείται ωσπου βρει κάποιο μικρότερο απο το pivot , το pivot ή patitioning element στο βιβλίο του King επιλέγεται στις νεότερες εκδόσεις του αλγοριθμου ως το 1ο στοιχείο (εδω το 3 ) σαφως η επιλογη αυτη δεν ειναι η καλυτερη δυνατη ως προς την επιδοση απο οσο διάβασα αλλα ειναι απλή και κατανοήσιμη. Το low κινείται επισης ωσπου βρει κάτι το οποιο ειναι μεγαλυτερο απο το pivot - ένα στοιχειο - . Αρχικα θα ξεκινήσουμε απομονώνοντας το στοιχείο pivot αφηνοντας του στο χαρτι την θέση του κενή. Στην συνέχεια θα ξεκινήσουμε απο τον high και θα κάνουμε την διαδικασία που μολις περιγράφτηκε. Στην περιπτωση που ο high βρει αυτο που πρέπει να βρεί ωστε να σταματήσει (το μικρότερο του pivot) βάζει αυτο που βρήκε εκει που δείχνει ο άλλος ο low και μετα αυτος αρχίζει να προχωρά. Όταν σταματά ο ένας προχωρά ο άλλος. Αρχικά > 3 1 4 5 9 2 6 8 7 low high - Θα βγάλω - απομονώσω το pivot > ___ 1 4 5 9 2 6 8 7 | 3 -> p low high - Ξεκινάμε απο τα δεξιά (κίνηση του high απο δεξια -> αριστερά ) > ___ 1 4 5 9 2 6 8 7 | 3 low high - Δεν βρίσκουμε κάποιο στοιχείο μικρότερο του pivot ? συνεχίζουμε > ___ 1 4 5 9 2 6 8 7 | 3 low high - Keep Walking ή καλύτερα Keep scaning > ___ 1 4 5 9 2 6 8 7 | 3 low high -Επειδή βρέθηκε στοιχείο μικρότερο του pivot 2 < 3 αυτο μπαίνει στην θέση που θα δείχνει ο low ενω το high μένει κενό. Επίσης σταματάει ο ένας (high) ξεκινάει ο άλλος (low). > 2 1 4 5 9 ____ 6 8 7 | 3 low high - Εφοσον δεν βρίσκει κάτι μεγαλύτερο απο το pivot συνεχίζει > 2 1 4 5 9 ____ 6 8 7 | 3 low high - Επειδή 4 > 3 το 4 μπαίνει εκει που δείχνει ο high ενω αυτο που δείχνει ο low μένει κενό. Στην συνέχεια ο high μετακινείται προς τα αριστερά. > 2 1 ___ 5 9 4 6 8 7 | 3 low high - O high τωρα προχωρά (κλασσικά μέχρι να βρεί μικρότερο απο το pivot ) > 2 1 ___ 5 9 4 6 8 7 | 3 low high - Keep scaning ... εφοσον 5 > 3 ... > 2 1 ______ 5 9 4 6 8 7 | 3 low high - Σε αυτο το σημείο παρατηρούμε οτι ο high δείχνει ακριβως στο στοιχείο οπου δείχνει και ο low , χωρις να έχει βρει κάποιο μικρότερο απο το pivot , σε αυτη τη περίπτωση σταματάμε και βάζουμε σε αυτή τη θέση το pivot το οποίο και φυλάγαμε σαν κρατούμενο τοση ώρα. H Λίστα ειναι λοιπον : > 2 1 3 5 9 4 6 8 7 Και το 1ο βήμα του αλγοριθμου έχει τελειώσει. Γιατι τα μικρότερα στοιχεία βρισκονται αριστερά του pivot ενω τα μεγαλύτερα δεξιά. P.S Ελπιζω να μην έχω κανει καμια πατατά.
imitheos Δημοσ. 4 Μαΐου 2012 Δημοσ. 4 Μαΐου 2012 http://www.piperies.gr/posts/o-xoros-quicksort Τα βιντεάκια με τους χορούς τα σπάνε Επίσης και εδώ οπτικοποιεί την λειτουργία διάφορων αλγορίθμων ταξινόμησης.
migf1 Δημοσ. 4 Μαΐου 2012 Δημοσ. 4 Μαΐου 2012 Το σχετικό άρθρο της Βικπίντια θεωρώ πως είναι πλήρες & κατατοπιστικό για την Quick Sort: http://en.wikipedia.org/wiki/Quicksort. Για οπτικοποίηση, βρίσκω πολύ καλό αυτό εδώ: http://pages.stern.nyu.edu/~panos/java/Quicksort/index.html (δικός μας, Έλληνας )
Star_Light Δημοσ. 5 Μαΐου 2012 Μέλος Δημοσ. 5 Μαΐου 2012 Ευχαριστω παιδια βασικα το βιβλιο του King και το βιντεάκι που έδωσα και πιο πάνω με βοήθησαν στο να τον καταλάβω 100% ωστοσο εχω 2 ερωτησεις καταρχην στο βιντεο οταν τελειώσει το βημα 1 και ο πινακας ειναι πλεον διχοτομημένος ως προς το pivot 2 3 1 4 6 7 8 5 τοτε μετά ξεκινά να ταξινομεί τον δεξί υποπίνακα αντι για τον αριστερό οπως γραφει στο βιβλιο του KIng φανταζομαι αυτο δεν έχει ιδιαιτερη σημασία έτσι? Επειδη ο τυπος στο βιντεο μιλάει σιγανα και δεν βγάζω τα αγγλικα του 100% επισης αυτο το αναδρομικο δεν εχω καταλαβει... την εννοια την ξέρω αλλα εδω δεν καταλαβαινω που παιζει αυτο το διαιρει και βασιλευε ειναι μετα την διχοτομηση που εχει πλεον 2 υποπινακες να ταξινομησει ξεχωριστά. @Chris6 Βασικα αν μιλάμε για την αρχικη έκδοση του αλγοριθμου (Οπου το pivot επιλέγεται σαν το αριστερότερο) τοτε εγω θα έπαιρνα το 3 σε αυτο που λες και θα το εκανα οπως παρουσιασα πιο πανω... Η αληθεια ειναι πως δεν θελω να μείνω πολυ στον αλγοριθμο περα απο τα βασικα του και να μπλέξω για αυτο και έψαχνα κατι πολυ βατο απο το youtube σαν παρουσιαση και αρα θα περιοριστώ στην αρχικη του εκδοση χωρις να κατσω να ψάξω πιο pivot θα τον βελτιστοποιεί κτλπ.... αυτα ισως στο μελλον προς το παρον θελω κάτι basic p.s Μηπως οταν κανει λογο για αναδρομικοτητα εννοει πως σπάει το προβλημα σε υποπροβλήματα και σε αυτά χρησιμοποιεί τον ίδιο αλγόριθμο και άρα προγραμματιστικά αυτο θα σημαίνει πως η συνάρτηση που υλοποιεί τον Quicksort καλεί τον εαυτό της ξανα και ξανά????? Aυτο το ρωταω επειδη αρχικα οταν μπαινει στον αλγοριθμο ο King λεει (αν καταλαβα καλα τα αγγλικα) οτι ξερεις ... η δυναμη και το παραγοντικο δεν ειναι ακριβεις αναδρομικες συναρτησεις και δεν χρειαζονται αναδρομη. Επειδη καλουν τον εαυτο τους μονο μια φορα.
ChRis6 Δημοσ. 5 Μαΐου 2012 Δημοσ. 5 Μαΐου 2012 Ναι , η εκδοση που βλεπεις ειναι αναδρομικη. Μπορεις βεβαια να το φτιαξεις και χωρις αναδρομη ! Το προβλημα ειναι απο τα all time classic "διαιρει και βασιλευε" ( divide / conquer/ combine ). Το ποια "πλευρα" του υποπινακα θα αποφασισεις να ταξινομησεις αναδρομικα δεν εχει καμια λογικη εξαρτηση,δηλαδη διαλεγεις οποια θελεις. Για βελτιστοποιηση τετοιων προβληματων μπαινουν στο παιχνιδι και αλλες τεχνικες , οπως αυτη του δυναμικου προγραμματισμου ή της απληστιας .
imitheos Δημοσ. 5 Μαΐου 2012 Δημοσ. 5 Μαΐου 2012 Δεν ξέρω γιατι αλλα δεν μ αρεσει ετσι οπως υλοποιει τον αλγοριθμο εδω -> http://www.mycstutorials.com/articles/sorting/quicksort εγω το έκανα "αλλιως" Υπάρχουν πολλοί τρόποι που μπορείς να υλοποιήσεις τον quicksort και πολλές παραλλαγές όπως ποιο στοιχείο επιλέγεις για pivot, κτλ. Άλλοι τρόποι πιο αποδοτικοί άλλοι λιγότερο. Αν και ο king με το παραπάνω link είναι σχεδόν ίδια, εμένα μου φάνηκε πιο κατανοητή η περιγραφή του link (και του chris6) από αυτήν του king που περιέγραψες καταρχην στο βιντεο οταν τελειώσει το βημα 1 και ο πινακας ειναι πλεον διχοτομημένος ως προς το pivot 2 3 1 4 6 7 8 5 επισης αυτο το αναδρομικο δεν εχω καταλαβει... την εννοια την ξέρω αλλα εδω δεν καταλαβαινω που παιζει αυτο το διαιρει και βασιλευε ειναι μετα την διχοτομηση που εχει πλεον 2 υποπινακες να ταξινομησει ξεχωριστά. p.s Μηπως οταν κανει λογο για αναδρομικοτητα εννοει πως σπάει το προβλημα σε υποπροβλήματα και σε αυτά χρησιμοποιεί τον ίδιο αλγόριθμο και άρα προγραμματιστικά αυτο θα σημαίνει πως η συνάρτηση που υλοποιεί τον Quicksort καλεί τον εαυτό της ξανα και ξανά????? Ο αλγόριθμος στο κύριο βήμα του απλά φέρνει τον πίνακα σε τέτοια κατάσταση ώστε αριστερά από το pivot να υπάρχουν μικρότερα στοιχεία και δεξιά μεγαλύτερα. Για αυτό όπως βλέπεις το 1 είναι δεξιά από το 3. Το αναδρομικό κολάει στο ότι μετά από αυτό ξανακαλείς τον αλγόριθμο αλλά για τους πίνακες "2 3 1" και "6 7 8 5". Aυτο το ρωταω επειδη αρχικα οταν μπαινει στον αλγοριθμο ο King λεει (αν καταλαβα καλα τα αγγλικα) οτι ξερεις ... η δυναμη και το παραγοντικο δεν ειναι ακριβεις αναδρομικες συναρτησεις και δεν χρειαζονται αναδρομη. Επειδη καλουν τον εαυτο τους μονο μια φορα. Δεν λέει ότι δεν είναι αναδρομικές συναρτήσεις αλλά ότι δεν εκμεταλλεύονται / δεν χρειάζονται την αναδρομή ("neither function makes much of a case for recursion, because each calls itself just once"). Και το παραγοντικό και την δύναμη (και τη σειρά fibonacci, κτλ) μπορείς να τις υλοποιήσεις πολύ εύκολα με μια απλή ανακύκλωση.
anterovgaltis2015 Δημοσ. 4 Σεπτεμβρίου 2015 Δημοσ. 4 Σεπτεμβρίου 2015 καλησπερα παιδια! Για να μην ανοιξω κι αλλο θεμα αφου υπαρχει εδω,Εχω θεμα με την quicksort γιατι δεν ειμαι σιγουρος αν κανω σωστα τα βηματα, και θελω να μου πειτε αν τα κανω σωστα!!Η ασκηση μου δινει τους αριθμους 11,11,12,32,22,23,24,84,14,54,15,25,26 ωραια;;Βρισκω τον ενδιαμεσο αριθμο (pivot αν το λεω σωστα) που ειναι το 23! Μετα αρχιζω και ψαχνω απο τα αριστερα προς τα δεξια (δηλαδη το 11) για καποιον αριθμο μεγαλυτερο του 23 οταν βρω (στην περιπτωση μου το 32) αρχιζω και ψαχνω απο τα δεξια προς τα αριστερα για καποιον μικροτερο του 23 (στην περιπτωση αυτη το 15);; οποτε τους αλλαζω και γινεται 11,11,12,15,22,23,24,84,14,54,32,25,26;;αυτο το εκανα μεχρι να βγαλω το αποτελεσμα 11,11,12,15,22,14,23,84,24,54,35,25,26 (θα παρακαλουσα οποιον εχει χρονο και μπορει να το δει μην εχω κανει καποιο λαθος!! Απο δω και περα τωρα επιλεγω πχ απο την αριστερη παλι τον μεσαιο αριθμο, τον τελευταιο ή τον πρωτο;;Edit:Τους αριθμους που ειπα αλλα μεχρι να βγαλω το αποτελεσμα που σας ειπα ειναι οι εξις: Αρχικη σειρα: 1) 11,11,12,32,22,23,24,84,14,54,15,25,26 ->το 15 με το 32 2) 11,11,12,15,22,23,24,84,14,54,32,25,26 ->το 23 με το 14 3) 11,11,12,15,22,14,24,84,23,54,32,25,26 ->το 24 με το 23 4) 11,11,12,15,22,14,23,84,24,54,32,25,26 ->τελικο αποτελεσμα
Προτεινόμενες αναρτήσεις
Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε
Πρέπει να είστε μέλος για να αφήσετε σχόλιο
Δημιουργία λογαριασμού
Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!
Δημιουργία νέου λογαριασμούΣύνδεση
Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.
Συνδεθείτε τώρα