forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 19 Νοέμ 2017, 18:06

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 6 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Ορθότητα BubleSort
ΔημοσίευσηΔημοσιεύτηκε: 25 Ιούλ 2006, 15:01 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 01 Μαρ 2006, 21:16
Δημοσ.: 459
Τοποθεσια: Νέος Κόσμος
Αποδείξτε ότι ο αλγόριθμος ταξινόμησης Φυσσαλίδας (BubbleSort) είναι ορθός, δηλαδή:

1. Τερματίζει για κάθε στιγμιότυπο εισόδου

2. Στην έξοδο παίρνουμε την είσοδο ταξινομημένη(δηλαδή τερματίζει σωστά)


Τι πολυπλοκότητα έχει ο αλγόριθμος αυτός ;


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Ορθότητα BubleSort
ΔημοσίευσηΔημοσιεύτηκε: 16 Ιαν 2010, 18:29 
Χωρίς σύνδεση

Εγγραφή: 10 Ιαν 2010, 19:14
Δημοσ.: 51
Το πρώτο φαίνεται να θέλει λίγη σκέψη και είναι έξω απο τις ικανότητες μου.Όσο για το δεύτερο ασ θεωρήσουμε την περίπτωση της άυξουσας ταξινόμησης.Ο bubble sort,απ'ότι έχω καταλάβει,υλοποιεί την εξής διαδικασία:Υπολιγίζει σε κάθε επανάληψη το min ενός συνόλου.Και αφού αυτο το Min εξ'ορισμού πρέπει να είναι μικρότερο απ'όλα τα στοιχεία του συνόλου,θα πρέπει λόγω των διαδοχικών συγκρίσεων και αντιμεταθέσεων στον εσωτερικό βρόγχου,να φτάσει τελικά ώς την πρώτη θέση(η την τελευταία,ανάλογα με το πώς ορίζει ο καθένας την αύξουσα ταξινόμηση).Στην δεύτερη εκτέλεση του εσωτεριού βρόγχου υπ/ζει το ελάχιστο όλων των στοιχείων εκτός του ελαχίστου του υπερσυνόλου του.Έτσι επαγωγικά φτάνουμε,μέσω του διαδοχικού υπ/μου ελαχίστων σε μια διάταξη.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Ορθότητα BubleSort
ΔημοσίευσηΔημοσιεύτηκε: 16 Ιαν 2010, 22:11 
Χωρίς σύνδεση
Regular Forumer

Εγγραφή: 09 Μαρ 2006, 14:43
Δημοσ.: 2767
Τοποθεσια: White Hart Lane
Βασικά το αντίθετο κάνει! Σε κάθε επανάληψη αυτό που κάνει σίγουρα είναι να πάει το i-οστό μεγαλύτερο στοιχείο στην n-i+1 θέση του πίνακα. Και το πόσες επαναλήψεις θα κάνει εξαρτάται από το πόσο μη ταξινομημένη είναι η είσοδος. Δες εδώ πιο αναλυτικά.

_________________
Lab Radio


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Ορθότητα BubleSort
ΔημοσίευσηΔημοσιεύτηκε: 17 Ιαν 2010, 01:55 
Χωρίς σύνδεση

Εγγραφή: 10 Ιαν 2010, 19:14
Δημοσ.: 51
Ως αύξουσα ταξινόμηση στο παραπάνω επιχείρημα όρισα αυτήν κατα την οποία τα αλγεβρικά μικρότερα στοιχεία του πίνακα στέλνονται τελικά στις θέσεις με τον μικρότερο δείκτη.Ακόμη και αν μιλάμε για διαφορετικούς αλγορίθμους για κάθε αλγόριθμο που ταξινομεί μέσω διαδοχικών ευρέσεων μεγίστου φαίνεται πως υπάρχει ένας που ταξινομεί με διαδοχικές ευρέσεις ελαχίστου.Άρα μιλάμε για διαφορετικούς αλγορίθμους που υλοπιούν την ίδια ιδέα(στηρίζονται στους ορισμούς των min,max αντίστοιχα) και φαίνεται να έχουν την ίδια πολυπλοκότητα.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Ορθότητα BubleSort
ΔημοσίευσηΔημοσιεύτηκε: 17 Ιαν 2010, 19:51 
Χωρίς σύνδεση
Regular Forumer

Εγγραφή: 09 Μαρ 2006, 14:43
Δημοσ.: 2767
Τοποθεσια: White Hart Lane
Ναι ok. Ίδια λογική είναι και ίδια πολυπλυκότητα όντως, O(n^2), αλλά υπάρχουν καλύτεροι αλγόριθμοι που κάνουν O(n\log n) οπότε δεν έχει και πολύ νόημα να το αναλύουμε.

_________________
Lab Radio


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Ορθότητα BubleSort
ΔημοσίευσηΔημοσιεύτηκε: 17 Ιαν 2010, 20:10 
Χωρίς σύνδεση
Regular Forumer
Άβαταρ μέλους

Εγγραφή: 23 Νοέμ 2006, 10:32
Δημοσ.: 1888
Sorting algorithm

_________________
"Πριν ξεκινήσουμε να συζητάμε, πρέπει πρώτα να ορίζουμε τις έννοιες για να μπορέσουμε να συνεννοηθούμε" - Σωκράτης


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 6 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group