Τρίτη, 15 Ιουνίου 2010

Άσκηση : Πόσες αντιμεταθέσεις γίνονται;

Δίνεται ακέραιος ταξινομημένος πίνακας Ρ[79]. Αν
εφαρμόσουμε σε αυτόν τη μέθοδο ευθείας ανταλλαγής
(φυσσαλίδα) πόσες αντιμεταθέσεις γειτονικών στοιχείων
θα πραγματοποιηθούν;

Λύση
Υπάρχουν δύο δυνατά σενάρια και απαιτείται περαιτέρω
διερεύνηση.
1η περίπτωση
Αν ο πίνακας είναι ταξινομημένος κατά αύξουσα σειρά
και η φυσσαλίδα προσπαθεί να επιτύχει ταξινόμηση κατά
αύξουσα σειρά, το συνολικό πλήθος των αντιμεταθέσεων
γειτονικών στοιχείων που θα πραγματοποιηθούν είναι 0. Το
ίδιο ισχύει και στην περίπτωση που ο πίνακας είναι ταξινο-
μημένος κατά φθίνουσα σειρά και η φυσσαλίδα προσπαθεί
να επιτύχει ταξινόμηση κατά φθίνουσα σειρά.
2η περίπτωση
Αν ο πίνακας είναι ταξινομημένος κατά αύξουσα σειρά
και η φυσσαλίδα προσπαθεί να επιτύχει ταξινόμηση κατά
φθίνουσα σειρά, το συνολικό πλήθος των αντιμεταθέσεων
γειτονικών στοιχείων που θα πραγματοποιηθούν είναι:
    78+77+76+....+1 = (78*79)/2 = 3081
Το ίδιο ισχύει και στην περίπτωση που ο πίνακας είναι ταξινο-
μημένος κατά φθίνουσα σειρά και η φυσσαλίδα προσπαθεί
να επιτύχει ταξινόμηση κατά αύξουσα σειρά.

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου