Το Στέκι των Πληροφορικών

Να κατασκευάσετε αλγόριθμο που θα ταξινομεί τα Ν στοιχεία ενός πίνακα Π σε αύξουσα σειρά και μετά θα επαναφέρει τα στοιχεία του πίνακα στις αρχικές τους θέσεις. 

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

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

---

---

Προτάθηκαν 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 είναι η πιό γρήγορη απ'όλες, αλλά ακόμα πιό δύσκολη στη σύλληψη και στην υλοποίηση, ιδιαίτερα στο κομμάτι που αφορά στην αλυσιδωτή επαναφορά

Άλλο "φτηνό" κόλπο επιτρέπεται να χρησιμοποιήσουμε;


Αλγόριθμος τάδε

Δεδομένα //Π, Ν//

μ ← 0

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

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

Αποτελέσματα //Π//


Τέλος τάδε



Και κάνω μια ρητορική ερώτηση : "Είναι σωστή αυτή η λύση;"

την.. δοκίμασες στο pseudoglossa.gr ;;  Είναι ένα βολικό περιβάλλον στο οποίο μπορείς να δοκιμάζεις τις λύσεις σου  ;D ;D :P

χεχε :)

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

Σέργιε η ρητορική ερώτηση αφορούσε το αν μπορούμε να χρησιμοποιήσουμε τον πίνακα Α.

Παράθεση από: sstergou στις 02 Μαρ 2011, 06:29:03 ΜΜ
Σέργιε η ρητορική ερώτηση αφορούσε το αν μπορούμε να χρησιμοποιήσουμε τον πίνακα Α.

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

Παράθεση από: sstergou στις 02 Μαρ 2011, 06:29:03 ΜΜ
Σέργιε η ρητορική ερώτηση αφορούσε το αν μπορούμε να χρησιμοποιήσουμε τον πίνακα Α.

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

Μόνο το φτηνό κόλπο δε μπορούμε να κάνουμε.. (στο πλαίσιο της εκφώνησης πάντα..) Και αυτό γιατί έτσι, ευτελίζουμε την άσκηση ;)

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

Παράθεση από: soron80 στις 02 Μαρ 2011, 09:14:28 ΜΜ
κι εγώ αυτή την απορία έχω..
π.χ. μπορούμε να χρησιμοποιήσουμε πίνακα Α με τις παλιές θέσεις των στοιχείων?

Μπορούμε να κάνουμε Ο,ΤΙ θέλουμε.. Αρκεί να μπορεί να γίνει.. (βέβαια στον A, o Στάθης κρατάει ιστορικό αντιμεταθέσεων προκειμένου να κάνει undo..)

Παράθεση από: sstergou στις 02 Μαρ 2011, 06:00:24 ΜΜ
Κρατάμε σε έναν πίνακα (που μοιάζει με στοίβα) το ιστορικό των αντιμεταθέσεων. Μετά την ταξινόμηση διασχίζουμε τον πίνακα από το τέλος προς την αρχή και κάνουμε κάτι σαν "undo" για κάθε αντιμετάθεση.

Η λύση του Στάθη είναι μια ομορφιά .. (προσωπική άποψη)..

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

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

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

---

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

Πρόγραμμα Ταξινόμηση_και_μετά_UNDO
Σταθερές
   Ν = 100
.
.

Το μέγεθος του πίνακα εξαρτάται από την πολυπλοκότητα της φυσαλίδας. Είναι ένας όμορφος τρόπος να εισάγεις αυτή την έννοια (αν ήταν μέσα στην ύλη βέβαια.)

Δημιουργούμε τον παρακάτω πίνακα Θ, κάθε στοιχείο του οποίου είναι ίσο με το δείκτη του. Πρακτικά πρόκειται για την αρχική θέση κάθε στοιχείου.


ΓΙΑ δ ΑΠΟ 1 ΜΕΧΡΙ Ν
  Θ[δ] <- δ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


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


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


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

Παράθεση από: sstergou στις 02 Μαρ 2011, 09:54:09 ΜΜ
Το μέγεθος του πίνακα εξαρτάται από την πολυπλοκότητα της φυσαλίδας. Είναι ένας όμορφος τρόπος να εισάγεις αυτή την έννοια (αν ήταν μέσα στην ύλη βέβαια.)

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

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

Οι επαναλήψεις είναι Ν-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]
.
.

Οπότε ο αλγόριθμος του Στάθη, μεταφέρεται μιααα χααααρά σε πρόγραμμα :)

Παράθεση από: odysseas στις 03 Μαρ 2011, 01:17:13 ΠΜ
Δημιουργούμε τον παρακάτω πίνακα Θ, κάθε στοιχείο του οποίου είναι ίσο με το δείκτη του. Πρακτικά πρόκειται για την αρχική θέση κάθε στοιχείου.
...
Ταξινομούμε τον πίνακα Π παράλληλα με τον πίνακα Θ. Μετά την ταξινόμηση, το στοιχείο Θ[δ] περιέχει την αρχική θέση του Π[δ].
...

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

Ένας ακόμη τρόπος επαναφοράς των στοιχείων στην αρχική τους θέση, πιό κοντά στο σκεπτικό του Οδυσσέα, είναι:
1. να δημιουργηθεί ο πίνακας των θέσεων ΠΡΙΝ την ταξινόμηση
2. να "ακολουθούν" οι δείκτες τα στοιχεία κατά την αντιμετάθεση και
3. για την επαναφορά, να γίνεται ξανά ταξινόμηση με κριτήριο, αυτή τη φορά, τους δείκτες.. και να "ακολουθούν" τα στοιχεία..  Έτσι, θα επιστρέψουν στις αρχικές τους θέσεις.

Ίδιες απαιτήσεις σε μνήμη με τον τρόπο του Οδυσσέα, αλλά πιό αργός (τάξης Ν²). Νομίζω όμως, ευκολότερος στην υλοποίηση (για τους μαθητές).

και με υποπρόγραμμα την ταξινόμηση, που καλείται δυο φορές με αλλαγή στον πίνακα που ταξινομείται και αυτόν που αντιμετατίθεται
(προϋπόθεση να είναι ο πίνακας αριθμών (όπως και ο πίνακας δεικτών) ΑΚΕΡΑΙΟΣ)

Και αν θέλαμε τα στοιχεία να είναι χαρακτήρες ;;

νομίζω με operator overloading στον τελεστή < και αντιμετάθεση μόνο των δεικτών λύνονται όλα τα προβλήματα :D

Παράθεση από: Sergio στις 03 Μαρ 2011, 12:59:45 ΜΜ
Και αν θέλαμε τα στοιχεία να είναι χαρακτήρες ;;

να μην το κάνεις με διαδικασία  :-X

Οδυσσέα μου φαίνεται ότι όταν στο τέλος προσπαθούμε να επαναφέρουμε τον πίνακα στην αρχική του μορφή υπάρχει κάποιο πρόβλημα.
Οι αντιμεταθέσεις στοιχείων στους πίνακες Θ και Π έχουν ως αποτέλεσμα να χαθεί η "παραλληλία".

Αυτό που θα μπορούσε να γίνει είναι να δημιουργηθεί ένας νέος πίνακας ως εξής :

Για ι από 1 μέχρι Ν
ΝΠ[Θ[ι]] ← Π[ι]
Τέλος_επανάληψης


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

Κώδικας [Επιλογή] Expand


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


Παράθεση από: sstergou στις 03 Μαρ 2011, 05:12:20 ΜΜ
Οι αντιμεταθέσεις στοιχείων στους πίνακες Θ και Π έχουν ως αποτέλεσμα να χαθεί η "παραλληλία".

Αφού το στοιχείο σε κάποια θέση του Π εξακολουθεί να αντιστοιχεί στο στοιχείο στην ίδια θέση του Θ, δε νομίζω πως χάνεται η παραλληλία.. Νομίζω πως το πρόβλημα είναι αλλού..

Ας δοκιμάσουμε τον κώδικα με 4 στοιχεία:

Έστω αρχικά  ο πίνακας Π με:
1. Ρ
2. Σ
3. Δ
4. Α

μετά τη δημιουργία του πίνακα δεικτών θα έχουμε (σε παρένθεση τα στοιχεία του πίνακα Θ):
1. Ρ (1)
2. Σ (2)
3. Δ (3)
4. Α (4)

μετά την ταξινόμηση θα έχουμε:
1. Α (4)
2. Δ (3)
3. Ρ (1)
4. Σ (2)

οπότε με την εκτέλεση του κώδικα επαναφοράς θα έχουμε:

1η επανάληψη: το Α πάει στη σωστή του θέση και έρχεται το Σ επάνω..
1. Σ (2)
2. Δ (3)
3. Ρ (1)
4. Α (4)

2η επανάληψη: το Δ πάει στη σωστή του θέση και έρχεται το Ρ επάνω..
1. Σ (2)
2. Ρ (1)
3. Δ (3)
4. Α (4)

3η επανάληψη: το Δ παραμένει στη σωστή του θέση..
1. Σ (2)
2. Ρ (1)
3. Δ (3)
4. Α (4)

ΤΕΛΟΣ.. χωρίς όλα τα στοιχεια να έχουν επανέρθει στην αρχική τους θέση :(

Καθ' όλη τη διάρκεια, οι δύο πίνακες παραμένουν "παράλληλοι".  Το πρόβλημα όμως δημιουργείται από την πρώτη κιόλας επανάληψη όταν, ενώ το Α πάει στη σωστή του θέση, έρχεται στη θέση του το Σ και, όταν μετά εξετάζεται το Δ και πάει στη σωστή του θέση, έρχεται στη θέση του το Ρ.  Έχοντας πλέον το δ (μεταβλητή ελέγχου της ΓΙΑ) πάρει την τιμή 3, δεν ξαναεξετάζεται ούτε το Ρ ούτε το Σ τα οποία έτσι παραμένουν σε λάθος θέσεις μέχρι το τέλος :(

Ιδέα:

Αν "επιμέναμε" μέχρι στη θέση δ να βρεθεί το σωστό στοιχείο;


δ <- 1
Αρχή_επανάληψης
  Αρχή επανάληψης
    αρχική <- Θ[δ]
    αντιμετάθεσε Π[δ], Π[αρχική]
    αντιμετάθεσε Θ[δ], Θ[αρχική]
  Μέχρις_ότου Θ[δ]=δ
  δ <- δ + 1
Μέχρι_ότου δ > Ν


θα "δούλευε";  Έχω την εντύπωση ότι, με τον παραπάνω κώδικα, όταν το αυξάνεται το δ.. ό,τι έχει αφήσει πίσω του είναι "τακτοποιημένο"

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

Οπότε, μία τροποποίηση θα μπορούσε να είναι:

δ <- 1

βρ <- Ψευδής
Όσο δ < Ν και βρ = Ψευδής επανάλαβε
  Αν Θ[δ] <> δ τότε
    βρ <- Αληθής
  αλλιώς
    δ <- δ + 1
  Τέλος_αν
Τέλος_επανάληψης

Όσο δ < Ν επανάλαβε
  Αρχή επανάληψης
    αρχική <- Θ[δ]
    αντιμετάθεσε Π[δ], Π[αρχική]
    αντιμετάθεσε Θ[δ], Θ[αρχική]
  Μέχρις_ότου Θ[δ]=δ

  βρ <- Ψευδής
  Όσο δ < Ν και βρ = Ψευδής επανάλαβε
    Αν Θ[δ] <> δ τότε
      βρ <- Αληθής
    αλλιώς
      δ <- δ + 1
    Τέλος_αν
Τέλος_επανάληψης


Τι λέτε ;

Παράθεση από: sstergou στις 03 Μαρ 2011, 05:12:20 ΜΜ
Αυτό που θα μπορούσε να γίνει είναι να δημιουργηθεί ένας νέος πίνακας [...]

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

Παράθεση από: Sergio στις 04 Μαρ 2011, 03:55:17 ΜΜ
Ιδέα: Αν "επιμέναμε" μέχρι στη θέση δ να βρεθεί το σωστό στοιχείο;

Ναι, αυτό που χαρακτηρίζεις παρακάτω και ως "αλυσίδα" είναι ένας καλός χαρακτηρισμός γι' αυτό που συμβαίνει. Οι περιττές αντιμεταθέσεις μπορούν να αποφευχθούν εύκολα αν χρησιμοποιήσει κανείς ΟΣΟ αντί για ΜΕΧΡΙΣ_ΟΤΟΥ.


ΓΙΑ δ ΑΠΟ 1 ΜΕΧΡΙ Ν-1
  ΟΣΟ Θ[δ] <> δ ΕΠΑΝΑΛΑΒΕ
    αρχική <- Θ[δ]
    αντιμετάθεσε Π[δ], Π[αρχική]
    αντιμετάθεσε Θ[δ], Θ[αρχική]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


Παράθεση από: Sergio στις 04 Μαρ 2011, 03:55:17 ΜΜ
θα "δούλευε";  Έχω την εντύπωση ότι, με τον παραπάνω κώδικα, όταν το αυξάνεται το δ.. ό,τι έχει αφήσει πίσω του είναι "τακτοποιημένο"

Αν επιμείνει κανείς να προχωρήσει μόνο όταν Θ[δ] = δ τότε είναι βέβαιο ότι κανένα στοιχείο στη συνέχεια δεν πρόκειται να διαταράξει τις υπάρχουσες τοποθετήσεις αφού τα στοιχεία που έχουν προηγηθεί είναι ήδη στις θέσεις τους.

Παράθεση από: ptsiotakis στις 03 Μαρ 2011, 12:52:37 ΜΜ
και με υποπρόγραμμα την ταξινόμηση, που καλείται δυο φορές με αλλαγή στον πίνακα που ταξινομείται και αυτόν που αντιμετατίθεται

Πάντως το να ταξινομήσουμε τον πίνακα Θ είναι λίγο "βαρύ" σε αυτή την περίπτωση -- μπορούμε να πετύχουμε αυτό που θέλουμε σε γραμμικό χρόνο και χωρίς συγκρίσεις. Σε αντίθεση με την κοινή ταξινόμηση, κάθε στοιχείο που συναντάμε στον Θ γνωρίζουμε ακριβώς που πρέπει να πάει. Μας το λέει απευθείας η τιμή του και δεν είναι ανάγκη να το συγκρίνουμε με άλλα για να το τοποθετήσουμε.