Αποστολέας Θέμα: Άσκηση Αντι-ταξινόμησης..  (Αναγνώστηκε 3855 φορές)

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Άσκηση Αντι-ταξινόμησης..
« στις: 02 Μάρ 2011, 11:00:44 πμ »
Να κατασκευάσετε αλγόριθμο που θα ταξινομεί τα Ν στοιχεία ενός πίνακα Π σε αύξουσα σειρά και μετά θα επαναφέρει τα στοιχεία του πίνακα στις αρχικές τους θέσεις. 

Ένα "φτηνό κόλπο" είναι να δημιουργείται, πριν την ταξινόμηση, ένα αντίγραφο του πίνακα Π οπότε, μετά την ταξινόμηση, το μόνο που χρειάζεται είναι να αντιγράφονται τα στοιχεία από το αντίγραφο, στον αρχικό πίνακα.

Να δώσετε λύση που ΔΕΝ θα χρησιμοποιεί αυτό το "φτηνό κόλπο" ;)


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


Προτάθηκαν 3 λύσεις:

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

Αναλυτικά:


Λύση 1
α. πριν γίνει η ταξινόμηση των στοιχείων δημιουργείται νέος παράλληλος πίνακας στον οποίο καταχωρίζονται οι αρχικές θέσεις των στοιχείων (θ[ι] <- ι)
β. ακολουθεί η ταξινόμηση των δύο παράλληλων πινάκων (Π, Θ) με κριτήριο τις τιμές του πίνακα δεδομένων (Π)
γ. γίνεται εκ νέου ταξινόμηση των δύο παράλληλων πινάκων (Π, Θ) με κριτήριο τις τιμές του πίνακα θέσεων (Π) οπότε οι τιμές του παράλληλου πίνακα επανέρχονται στις αρχικές τους θέσεις

Κώδικας: [Επιλογή]
Αλγόριθμος Ταξινόμηση_και_επαναφορά_1
Δεδομένα //Π, Ν//

! δημιουργία πίνακα θέσεων
!------------------------------
ΓΙΑ δ ΑΠΟ 1 ΜΕΧΡΙ Ν
  Θ[δ] ←  δ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

! ταξινόμηση με κριτήριο τα στοιχεία του Π
!-----------------------------------------------
Για ι από 2 μέχρι Ν
Για ξ από Ν μέχρι ι με_βήμα -1
Αν Π[ξ] < Π[ξ-1] τότε
Αντιμετάθεσε Π[ξ], Π[ξ-1]
Αντιμετάθεσε Θ[ξ], Θ[ξ-1]
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης

! επαναφορά (ταξινόμηση με κριτήριο τα στοιχεία του Θ)
!--------------------------------------------------------------
Για ι από 2 μέχρι Ν
Για ξ από Ν μέχρι ι με_βήμα -1
Αν Θ[ξ] < Θ[ξ-1] τότε
Αντιμετάθεσε Π[ξ], Π[ξ-1]
Αντιμετάθεσε Θ[ξ], Θ[ξ-1]
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης

Αποτελέσματα //Π//
Τέλος Ταξινόμηση_και_επαναφορά_1

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

Πρόκειται ουσιαστικά με υλοποίηση της λειτουργίας undo, βήμα-προς-βήμα στη διαδικασία ταξινόμησης

Κώδικας: [Επιλογή]
Αλγόριθμος Ταξινόμηση_και_επαναφορά_2
Δεδομένα //Π, Ν//

! ταξινόμηση με καταγραφή ιστορικού αντιμεταθέσεων
!--------------------------------------------------------------
μ ← 0
Για ι από 2 μέχρι Ν
Για ξ από Ν μέχρι ι με_βήμα -1
Αν Π[ξ] < Π[ξ-1] τότε
Αντιμετάθεσε Π[ξ], Π[ξ-1]
μ ← μ + 1
Α[μ] ← ξ      ! καταγράφηκε
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης

! επαναφορά (επανάληψη των αντιμεταθέσεων, με ανάποδη σειρά - UNDO)
!-----------------------------------------------------------------------------------
Για ι από μ μέχρι 1 με_βήμα -1
Αντιμετάθεσε Π[Α[ι]], Π[Α[ι]-1]
Τέλος_επανάληψης

Αποτελέσματα //Π//
Τέλος  Ταξινόμηση_και_επαναφορά_2

Λύση 3
α. πριν γίνει η ταξινόμηση των στοιχείων δημιουργείται νέος παράλληλος πίνακας στον οποίο καταχωρίζονται οι αρχικές θέσεις των στοιχείων (θ[ι] <- ι)
β. ακολουθεί η ταξινόμηση των δύο παράλληλων πινάκων (Π, Θ) με κριτήριο τις τιμές του πίνακα δεδομένων (Π)
γ. με ένα πέρασμα του πίνακα των θέσεων, εφαρμόζεται μια διαδικασία αλυσιδωτής αναδιάταξης των στοιχείων, ώστε να επανέλθουν στις αρχικές τους θέσεις, ως εξής:
  - το πρώτο στοιχείο του πίνακα αντιμετατίθεται με εκείνο που βρίσκεται στη θέση του. Έτσι, το πρώτο πηγαίνει στη σωστή του θέση και στην πρώτη θέση έρχεται εκείνο που την καταλάμβανε.
  - το στοιχείο που ήρθε στην πρώτη θέση εξετάζεται πάλι, αφού ενδέχεται να "ανήκει" σε άλλη θέση.
  - η διαδικασία επαναλαμβάνεται με την ίδια θέση μέχρι, κάποια στιγμή, να έρθει στη θέση αυτή το στοιχείο που πρέπει
  - η διαδικασία συνεχίζεται όμοια με την επόμενη θέση του πίνακα, μέχρι να εξαντληθούν όλες οι θέσεις
Επειδή η αλυσιδωτή αυτή τακτοποίηση ενδέχεται να διατάξει τα στοιχεία σωστά ΠΡΙΝ φτάσει στο τέλος του πίνακα, η εξέταση - επανατοποθέτηση του στοιχείου (αρχή της αλυσίδας) γίνεται μόνον εάν δεν είναι ήδη στη σωστή του θέση

Κώδικας: [Επιλογή]
Αλγόριθμος Ταξινόμηση_και_επαναφορά_3
Δεδομένα //Π, Ν//

! δημιουργία πίνακα θέσεων
!------------------------------
ΓΙΑ δ ΑΠΟ 1 ΜΕΧΡΙ Ν
  Θ[δ] ←  δ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

! Ταξινόμηση
!------------------------------
Για ι από 2 μέχρι Ν
Για ξ από Ν μέχρι ι με_βήμα -1
Αν Π[ξ] < Π[ξ-1] τότε
Αντιμετάθεσε Π[ξ], Π[ξ-1]
Αντιμετάθεσε Θ[ξ], Θ[ξ-1]
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης

! επαναφορά με βάση τις αρχικές θέσεις
!-------------------------------------------
ΓΙΑ δ ΑΠΟ 1 ΜΕΧΡΙ Ν-1
  ΟΣΟ Θ[δ] <> δ ΕΠΑΝΑΛΑΒΕ     ! αλυσιδωτά
    αρχική ←  Θ[δ]
    αντιμετάθεσε Π[δ], Π[αρχική]
    αντιμετάθεσε Θ[δ], Θ[αρχική]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Αποτελέσματα //Π//
Τέλος Ταξινόμηση_και_επαναφορά_3

Συμπερασματικά


Η λύση 1 φαίνεται να είναι η πιό απλή στην υλοποίηση, είναι όμως η πιό αργή απ'όλες
Η λύση 2 είναι πιό εμπνευσμένη, πιό γρήγορη, αλλά πιό δύσκολη στη σύλληψη αν και αποδεικνύεται αρκετά απλή στην υλοποίηση
Η λύση 3 είναι η πιό γρήγορη απ'όλες, αλλά ακόμα πιό δύσκολη στη σύλληψη και στην υλοποίηση, ιδιαίτερα στο κομμάτι που αφορά στην αλυσιδωτή επαναφορά
« Τελευταία τροποποίηση: 05 Μάρ 2011, 11:04:55 μμ από Sergio »
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #1 στις: 02 Μάρ 2011, 05:09:28 μμ »
Άλλο "φτηνό" κόλπο επιτρέπεται να χρησιμοποιήσουμε;

Κώδικας: Text
  1. Αλγόριθμος τάδε
  2.  
  3. Δεδομένα //Π, Ν//
  4.  
  5. μ ← 0
  6.  
  7. Για ι από 2 μέχρι Ν
  8.         Για ξ από Ν μέχρι ι με_βήμα -1
  9.                 Αν Π[ξ] < Π[ξ-1] τότε
  10.                         Αντιμετάθεσε Π[ξ], Π[ξ-1]
  11.                         μ ← μ + 1
  12.                         Α[μ] ← ξ - 1
  13.                 Τέλος_αν
  14.         Τέλος_επανάληψης
  15. Τέλος_επανάληψης
  16.  
  17. Για ι από μ μέχρι 1 με_βήμα -1
  18.         Αντιμετάθεσε Π[Α[ι]], Π[Α[ι] + 1]
  19. Τέλος_επανάληψης
  20.  
  21. Αποτελέσματα //Π//
  22.  
  23.  
  24. Τέλος τάδε
  25.  


Και κάνω μια ρητορική ερώτηση : "Είναι σωστή αυτή η λύση;"
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #2 στις: 02 Μάρ 2011, 05:29:57 μμ »
την.. δοκίμασες στο pseudoglossa.gr ;;  Είναι ένα βολικό περιβάλλον στο οποίο μπορείς να δοκιμάζεις τις λύσεις σου  ;D ;D :P
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #3 στις: 02 Μάρ 2011, 06:00:24 μμ »
χεχε :)

Όσον αφορά την λύση αυτό που γίνεται είναι το εξής (το γράφω για κάθε ενδιαφερόμενο) :
Κρατάμε σε έναν πίνακα (που μοιάζει με στοίβα) το ιστορικό των αντιμεταθέσεων. Μετά την ταξινόμηση διασχίζουμε τον πίνακα από το τέλος προς την αρχή και κάνουμε κάτι σαν "undo" για κάθε αντιμετάθεση.
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #4 στις: 02 Μάρ 2011, 06:29:03 μμ »
Σέργιε η ρητορική ερώτηση αφορούσε το αν μπορούμε να χρησιμοποιήσουμε τον πίνακα Α.
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

soron80

  • Ομάδα διαγωνισμάτων 2011
  • *
  • Μηνύματα: 116
  • Back In Black
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #5 στις: 02 Μάρ 2011, 09:14:28 μμ »
Σέργιε η ρητορική ερώτηση αφορούσε το αν μπορούμε να χρησιμοποιήσουμε τον πίνακα Α.

κι εγώ αυτή την απορία έχω..
π.χ. μπορούμε να χρησιμοποιήσουμε πίνακα Α με τις παλιές θέσεις των στοιχείων?
Τσισπαράς Βασίλης
Καθηγητής Πληροφορικής ΠΕ19

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #6 στις: 02 Μάρ 2011, 09:35:39 μμ »
Σέργιε η ρητορική ερώτηση αφορούσε το αν μπορούμε να χρησιμοποιήσουμε τον πίνακα Α.

ΑΣΦΑΛΩΣ και μπορούμε.. Μπορούμε να κάνουμε Ο,ΤΙ θέλουμε.. Αρκεί να μπορεί να γίνει..

Μόνο το φτηνό κόλπο δε μπορούμε να κάνουμε.. (στο πλαίσιο της εκφώνησης πάντα..) Και αυτό γιατί έτσι, ευτελίζουμε την άσκηση ;)
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1302
  • There are always possibilities...
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #7 στις: 02 Μάρ 2011, 09:38:24 μμ »
Ο Στάθης ανοίγει πληγές :D. Αν και δεν έχω κοιτάξει τον αλγόριθμο με λεπτομέρεια, αλλά διακινδυνεύω να πω ότι εφόσον μπορούμε να υπολογίσουμε εκ των προτέρων μία εύλογη χειρότερη περίπτωση για το πλήθος των αντιμεταθέσεων (και όχι να το διαβάσουμε από τον χρήστη) τότε ναι μπορούμε :) :-X
A man provided with paper, pencil, and rubber, and subject to strict discipline is in effect a universal machine - Alan Turing

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #8 στις: 02 Μάρ 2011, 09:38:58 μμ »
κι εγώ αυτή την απορία έχω..
π.χ. μπορούμε να χρησιμοποιήσουμε πίνακα Α με τις παλιές θέσεις των στοιχείων?

Μπορούμε να κάνουμε Ο,ΤΙ θέλουμε.. Αρκεί να μπορεί να γίνει.. (βέβαια στον A, o Στάθης κρατάει ιστορικό αντιμεταθέσεων προκειμένου να κάνει undo..)
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #9 στις: 02 Μάρ 2011, 09:43:43 μμ »
Κρατάμε σε έναν πίνακα (που μοιάζει με στοίβα) το ιστορικό των αντιμεταθέσεων. Μετά την ταξινόμηση διασχίζουμε τον πίνακα από το τέλος προς την αρχή και κάνουμε κάτι σαν "undo" για κάθε αντιμετάθεση.

Η λύση του Στάθη είναι μια ομορφιά .. (προσωπική άποψη)..
Ο Στάθης ανοίγει πληγές :D. Αν και δεν έχω κοιτάξει τον αλγόριθμο με λεπτομέρεια, αλλά διακινδυνεύω να πω ότι εφόσον μπορούμε να υπολογίσουμε εκ των προτέρων μία εύλογη χειρότερη περίπτωση για το πλήθος των αντιμεταθέσεων (και όχι να το διαβάσουμε από τον χρήστη) τότε ναι μπορούμε :) :-X

Αμάν βρε Παναγιώτη.. Όλα να τα μαρτυρήσεις και συ.. >:D :P :'(

Ότι ετοιμαζόμουν να ποστάρω το παρακάτω:



Να μεταφέρετε τον αλγόριθμο του Στάθη σε πρόγραμμα, ξεκινώντας όπως δίνεται στη συνέχεια:

Κώδικας: [Επιλογή]
Πρόγραμμα Ταξινόμηση_και_μετά_UNDO
Σταθερές
   Ν = 100
.
.

Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

sstergou

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 983
  • Program or be Programmed
    • pseudoglossa.gr
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #10 στις: 02 Μάρ 2011, 09:54:09 μμ »
Το μέγεθος του πίνακα εξαρτάται από την πολυπλοκότητα της φυσαλίδας. Είναι ένας όμορφος τρόπος να εισάγεις αυτή την έννοια (αν ήταν μέσα στην ύλη βέβαια.)
Στάθης Στέργου - sstergouATgmailDOTcom - http://www.pseudoglossa.gr

odysseas

  • Ομάδα διαγωνισμάτων 2011
  • *
  • Μηνύματα: 842
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #11 στις: 03 Μάρ 2011, 01:17:13 πμ »
Δημιουργούμε τον παρακάτω πίνακα Θ, κάθε στοιχείο του οποίου είναι ίσο με το δείκτη του. Πρακτικά πρόκειται για την αρχική θέση κάθε στοιχείου.

Κώδικας: [Επιλογή]
ΓΙΑ δ ΑΠΟ 1 ΜΕΧΡΙ Ν
  Θ[δ] <- δ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Ταξινομούμε τον πίνακα Π παράλληλα με τον πίνακα Θ. Μετά την ταξινόμηση, το στοιχείο Θ[δ] περιέχει την αρχική θέση του Π[δ].

Κώδικας: [Επιλογή]
! μεταφορά στην αρχική θέση
ΓΙΑ δ ΑΠΟ 1 ΜΕΧΡΙ Ν-1
  αρχική <- Θ[δ]
  αντιμετάθεσε Π[δ], Π[αρχική]
  αντιμετάθεσε Θ[δ], Θ[αρχική]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Συνήθης πρακτική είναι επίσης να ταξινομείται μόνο ο πίνακας Θ και όχι ο πίνακας δεδομένων.

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #12 στις: 03 Μάρ 2011, 11:56:39 πμ »
Το μέγεθος του πίνακα εξαρτάται από την πολυπλοκότητα της φυσαλίδας. Είναι ένας όμορφος τρόπος να εισάγεις αυτή την έννοια (αν ήταν μέσα στην ύλη βέβαια.)

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

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

Οι επαναλήψεις είναι Ν-1 την πρώτη φορά, Ν-2 τη δεύτερη, Ν-3 την τρίτη, κ.ο.κ. και την τελευταία φορά μόνο 1.. Οι "φορές" είναι Ν-1 (Για ι από 2 μέχρι Ν), επομένως οι επαναλήψεις είναι:
1) Ν-1
2) Ν-2
3) Ν-3
.
.
Ν-1) 1

Το άθροισμα αυτής της σειράς είναι, αν θυμάμαι καλά) Ν * (Ν - 1) / 2.. Επομένως στην περίπτωσή μας: 100*99/2 = 4500.

Συνεπώς, το πρόγραμμα θα μπορούσε να έχει τη μορφή:

Κώδικας: [Επιλογή]
Πρόγραμμα Ταξινόμηση_και_μετά_UNDO
Σταθερές
   Ν = 100
   Μ = 4500
ΜΕΤΑΒΛΗΤΕΣ
   ΑΚΕΡΑΙΕΣ: Π[100], Α[4500]
.
.

Οπότε ο αλγόριθμος του Στάθη, μεταφέρεται μιααα χααααρά σε πρόγραμμα :)
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #13 στις: 03 Μάρ 2011, 12:00:55 μμ »
Δημιουργούμε τον παρακάτω πίνακα Θ, κάθε στοιχείο του οποίου είναι ίσο με το δείκτη του. Πρακτικά πρόκειται για την αρχική θέση κάθε στοιχείου.
...
Ταξινομούμε τον πίνακα Π παράλληλα με τον πίνακα Θ. Μετά την ταξινόμηση, το στοιχείο Θ[δ] περιέχει την αρχική θέση του Π[δ].
...

Επίσης πολύ κομψή λύση, με μικρότερες απαιτήσεις σε μνήμη και .. ταχύτερη "επαναφορά" των στοιχείων στις αρχικές τους θέσεις αφού αυτή γίνεται με μονή επανάληψη (τάξης Ν) και όχι διπλή (τάξης Ν2)
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 797
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Άσκηση Αντι-ταξινόμησης..
« Απάντηση #14 στις: 03 Μάρ 2011, 12:04:53 μμ »
Ένας ακόμη τρόπος επαναφοράς των στοιχείων στην αρχική τους θέση, πιό κοντά στο σκεπτικό του Οδυσσέα, είναι:
1. να δημιουργηθεί ο πίνακας των θέσεων ΠΡΙΝ την ταξινόμηση
2. να "ακολουθούν" οι δείκτες τα στοιχεία κατά την αντιμετάθεση και
3. για την επαναφορά, να γίνεται ξανά ταξινόμηση με κριτήριο, αυτή τη φορά, τους δείκτες.. και να "ακολουθούν" τα στοιχεία..  Έτσι, θα επιστρέψουν στις αρχικές τους θέσεις.

Ίδιες απαιτήσεις σε μνήμη με τον τρόπο του Οδυσσέα, αλλά πιό αργός (τάξης Ν2). Νομίζω όμως, ευκολότερος στην υλοποίηση (για τους μαθητές).
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)