flo1 Δημοσ. 7 Σεπτεμβρίου 2009 Δημοσ. 7 Σεπτεμβρίου 2009 Με μπερδεψε. Το ταξινομημενο τμημα πρεπει να ειναι δεξια ή αριστερα? Η δεν εχει σημασια? Το αποτελεσμα θα ειναι το ιδιο, ειτε αρχισω τις συγκρισεις απο δεξια προς τα αριστερα, ειτε απο δεξια προς τα αριστερα?
macabre_sunsets Δημοσ. 7 Σεπτεμβρίου 2009 Δημοσ. 7 Σεπτεμβρίου 2009 Αναλόγως το πώς θες να κάνεις την ταξινόμηση. Με τον ένα τρόπο γίνεται κατά αύξοντα αριθμό, με τον άλλο κατά φθίνοντα. Εκτός και αν δεν κατάλαβα καλά και εννοείς αν θα έχει διαφορά να αρχίσεις κανονικά ή ανάποδα... Που λογικά θα είναι το ίδιο πράμα.
flo1 Δημοσ. 7 Σεπτεμβρίου 2009 Μέλος Δημοσ. 7 Σεπτεμβρίου 2009 Nαι ειναι το ιδιο πραγμα τωρα το καταλαβα!! Ειτε ειναι φθνινουσα ειτε αυξουσα σειρα, αναλογα κανεις τις αντικαταστασεις. Ευχαριστω. ---------- Το μήνυμα προστέθηκε στις 18:11 ---------- ------------------------------------------------------------------------------------------------------ QUICK SORT ψαχνω ενα καλο παραδειγμα. βρηκα καποια με μπερδεψαν πολυ ομως!
Wise_One Δημοσ. 7 Σεπτεμβρίου 2009 Δημοσ. 7 Σεπτεμβρίου 2009 "Καλό" παράδειγμα δε νομίζω να υπάρχει. Είναι ούτως ή άλλος μπελαλίδικος αλγόριθμος γιατί αν δεν κάνω λάθος είναι αναδρομικός. Δες αυτά: wikipedia, princeton, roseindia. Πάντως αυτό που πρέπει να προσέξεις: μη το χρησιμοποιήσεις σε μικρό πίνακα γιατί κάνει ολόκληρη φασαρία για το τίποτα, θέλει μεγάλο αριθμό εγγραφών.
Technology fan Δημοσ. 7 Σεπτεμβρίου 2009 Δημοσ. 7 Σεπτεμβρίου 2009 "Καλό" παράδειγμα δε νομίζω να υπάρχει. Είναι ούτως ή άλλος μπελαλίδικος αλγόριθμος γιατί αν δεν κάνω λάθος είναι αναδρομικός. Δες αυτά: wikipedia, princeton, roseindia. Πάντως αυτό που πρέπει να προσέξεις: μη το χρησιμοποιήσεις σε μικρό πίνακα γιατί κάνει ολόκληρη φασαρία για το τίποτα, θέλει μεγάλο αριθμό εγγραφών. Κάνεις λάθος... δεν είναι αναδρομικός ουτε χρειάζεται μεγάλο αριθμό εγγραφών, απλά δεν είναι καθόλου αποδοτικός απο πλευράς υπολογιστικής ισχύς, κάνει συνεχείς μετατοπίσεις στοιχείων και η μέση και η χειρότερη περίπτωση είναι Ο( n^2 ). Επίσης είναι γεγονός οτι αν δεν είχε τόσο τραβηχτικό όνομα ουτε καν θα υπήρχε αναφορά, Θα ήταν καλό να έβλεπες την quicksort
flo1 Δημοσ. 7 Σεπτεμβρίου 2009 Μέλος Δημοσ. 7 Σεπτεμβρίου 2009 "Καλό" παράδειγμα δε νομίζω να υπάρχει. Είναι ούτως ή άλλος μπελαλίδικος αλγόριθμος γιατί αν δεν κάνω λάθος είναι αναδρομικός. Δες αυτά: wikipedia, princeton, roseindia. Πάντως αυτό που πρέπει να προσέξεις: μη το χρησιμοποιήσεις σε μικρό πίνακα γιατί κάνει ολόκληρη φασαρία για το τίποτα, θέλει μεγάλο αριθμό εγγραφών. Κάνεις λάθος... δεν είναι αναδρομικός ουτε χρειάζεται μεγάλο αριθμό εγγραφών, απλά δεν είναι καθόλου αποδοτικός απο πλευράς υπολογιστικής ισχύς, κάνει συνεχείς μετατοπίσεις στοιχείων και η μέση και η χειρότερη περίπτωση είναι Ο( n^2 ). Επίσης είναι γεγονός οτι αν δεν είχε τόσο τραβηχτικό όνομα ουτε καν θα υπήρχε αναφορά, Θα ήταν καλό να έβλεπες την quicksort Ευχαριστω για τη βοηθεια!
kagelos Δημοσ. 7 Σεπτεμβρίου 2009 Δημοσ. 7 Σεπτεμβρίου 2009 Technology fan νομίζω τα μπέρδεψες λίγο. Αν δεις τα link που δίνει ο Wise_One είναι για Quicksort, οπότε σε αυτό αναφέρεται και όχι στο bubble sort. Παρά τον τίτλο του thread, ο flo1 ρώτησε και Quicksort - σε αυτό του απαντά ο Wise_One μιλώντας για αναδρομικό αλγόριθμο.
Technology fan Δημοσ. 8 Σεπτεμβρίου 2009 Δημοσ. 8 Σεπτεμβρίου 2009 Technology fan νομίζω τα μπέρδεψες λίγο. Αν δεις τα link που δίνει ο Wise_One είναι για Quicksort, οπότε σε αυτό αναφέρεται και όχι στο bubble sort. Παρά τον τίτλο του thread, ο flo1 ρώτησε και Quicksort - σε αυτό του απαντά ο Wise_One μιλώντας για αναδρομικό αλγόριθμο. :fear: Απολογούμαι... αυτό πάντως με το μικρό αριθμό εγραφών δε στέκει και πάλι, γενικώς όταν βγάζουν έναν αλγόριθμο ταξινόμησης δεν έχει να κάνει με το πόσα στοιχεία θα ταξινομήσεις πάντα θα δουλεύει ακόμα και ένα στοιχείο να χει... Εκτός αν τα μπέρδεψα πάλι :lol:
Wise_One Δημοσ. 8 Σεπτεμβρίου 2009 Δημοσ. 8 Σεπτεμβρίου 2009 Προσωπικά δεν το έχω δοκιμάσει για να πώ την αλήθεια. Απλά θυμάμαι ότι μας το είπε ο καθηγητής στη σχολή. Επειδή διαλέγει pivots και κάνει συνεχείς μετατοπίσεις, σε μικρό πίνακα δεν "αξίζει", κάνει ολόκληρη φασαρία. Μια bubble sort ας πούμε θα είναι πιο αποδοτική. Βέβαια το "μικρός" πίνακας είναι σχετικό, τα παραδείγματα που κάναμε είχαν το πολύ 15 στοιχεία άρα για εκεί γύρω μιλάμε...
C6WGMN Δημοσ. 8 Σεπτεμβρίου 2009 Δημοσ. 8 Σεπτεμβρίου 2009 Δεν χρειάζεται να ανησυχείς για την δουλειά που κάνει η συνάρτηση quicksort σε μικρές εισόδους. Γενικά το κόστος είναι πολύ μικρό σε σχέση με τι διαφορα κόστους bubblesort και quicksort σε μεγάλες εισόδους. Επίσης να προσθέσω ότι ο κώδικας στο princeton είναι μια ειδική περίπτωση quicksort για πραγματικούς αριθμούς. Στην γενική περίπτωση, η quicksort γίνετε μια συνάρτηση υψηλότερης σειράς.
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.