Ταξινόμηση μονοδιάστατου πίνακα

Ξεκίνησε από alkisg, 08 Μαρ 2007, 04:15:33 ΜΜ

« προηγούμενο - επόμενο »

alkisg

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

Γιώργο μου αρέσει που βρίσκουμε ευκαιρίες και αναλύουμε το μαθηματικό υπόβαθρο... Έτσι έχω κάτι για να σκέφτομαι στα αμέτρητα πηγαινέλα με το αυτοκίνητο! ;)

Συμφωνώ εν μέρει με αυτά που γράφεις με έντονα γράμματα. Η διαφωνία μου είναι ότι η ταξινόμηση δεν ορίζεται ούτε σε μονοδιάστατους πίνακες! ???
Η ταξινόμηση ορίζεται σε ένα πεπερασμένο σύνολο διατεταγμένων στοιχείων (ώστε δηλαδή να υπάρχει η έννοια του προηγούμενου και του επόμενου). Εφόσον οριστεί η έννοια του προηγούμενου και του επόμενου στοιχείου, τότε η ταξινόμηση μπορεί να οριστεί σε μονοδιάστατους πίνακες, σε πολυδιάστατους, σε λίστες, σε dictionary objects (hashes στην perl/php - στο περίπου είναι πίνακες αλλά σαν δείκτες αντί για ακεραίους παίρνουν strings) αλλά και σε απλές μεταβλητές που δεν υπάγονται σε κάποια δομή.
Γιατί όμως έχει σημασία να οριστεί το προηγούμενο και το επόμενο στοιχείο;

Ας τα πάρω από την αρχή. Ο ορισμός της ταξινόμησης του βιβλίου λέει:
Παράθεση από: Βιβλίο μαθητή, σελίδα 66Ορισμός. Δοθέντων των στοιχείων a1, a2, ..., an, η ταξινόμηση συνίσταται στη μετάθεση (permutation) της θέσης των στοιχείων, ώστε να τοποθετηθούν σε μια σειρά ak1, ak2, ..., akn έτσι ώστε, δοθείσης μιας συνάρτησης διάταξης (ordering function), f, να ισχύει:
              f(ak1) <= f(ak1) <= ... <= f(akn)

Καταρχάς, (σωστά) δεν αναφέρει πουθενά για πίνακες. Μόνο για στοιχεία, και τα έχει αριθμήσει ώστε να είναι διατεταγμένα.

Πάμε να το εφαρμόσουμε στους μονοδιάστατους πίνακες. Πανεύκολο ως αυτονόητο. a1 λέω το Α[1], a2 λέω το Α[2] κτλ. Καμία ασάφεια.

Πάμε να το εφαρμόσουμε στους δισδιάστατους πίνακες. Χμ... ποιο στοιχείο είναι το a1 και ποιο το a2; Κι εδώ εσύ (σωστά) λες ότι θα πρέπει πρώτα να βρούμε έναν τρόπο να μεταφέρουμε τις δύο διαστάσεις σε μία, ώστε το A[i, k] να γίνει Α[m], και να μπορέσουμε μετά να τα διατάξουμε με βάση το m (οι τύποι μετατροπής που έλεγα παραπάνω).
Και συμπληρώνεις (γράφω στο περίπου το νόημα όπως το κατάλαβα) ότι αφού δεν υπάρχει η έννοια της διάταξης στις δύο διαστάσεις, οποιαδήποτε αντιστοίχιση στη μία διάσταση κάνουμε είναι αυθαίρετη, άρα δεν ορίζεται η ταξινόμηση στις δύο διαστάσεις.

Στο τελευταίο είναι η κυρίως διαφωνία μας. Εγώ υποστηρίζω ότι επειδή οποιαδήποτε (αυθαίρετη) 1-1 αντιστοίχιση κι αν κάνουμε είναι το ίδιο, γι' αυτό και η έννοια της ταξινόμησης "στέκει" σε οσεσδήποτε διαστάσεις. Δεν μας ενδιαφέρει αν τα στοιχεία τα έχουμε τοποθετήσει σε ένα πίνακα 127 διαστάσεων, σε μια λίστα, σε ένα dictionary ή αν είναι απλές μεταβλητές a1, a2, ..., a127 που δεν ανήκουν σε κάποια δομή, αρκεί με οποιονδήποτε αυθαίρετο τρόπο να μπορούμε να ξεχωρίσουμε το προηγούμενο από το επόμενο.

Αλλά γιατί να είναι ισοδύναμοι οι τρόποι διάταξης;

Έστω ότι κάποιος λέει "Εγώ διατάσσω τα στοιχεία ενός δισδιάστατου όπως τα διαβάζω, δηλαδή πρώτο στοιχείο (a1) είναι το πάνω αριστερά (A[1, 1])".
Ας βαφτίσουμε τη συνάρτηση αυτή g(i, j).

Ένας άραβας όμως λέει "Εγώ διαβάζω από δεξιά προς τα αριστερά, άρα θα θεωρήσω a1 το A[1, N]".
Ας βαφτίσουμε τη συνάρτηση αυτή h(k, l).

Σε κάθε περίπτωση, οποιαδήποτε (1-προς-1) διάταξη κι αν επιλέξουν, θα καταλήξουν τελικά σε μια σειρά διατεταγμένων στοιχείων a1, a2, ..., an.
Επειδή όμως η σειρά των στοιχείων είναι πάντα διακριτή και πεπερασμένη (1 ως n), πάντα θα μπορούμε να βρούμε μία συνάρτηση μετάθεσης p (permutation) η οποία θα μετατρέπει την πρώτη συνάρτηση στη δεύτερη, δηλαδή
g(i, j) = p(h(k, l))
γι' αυτό και λέω ότι οποιεσδήποτε 1-προς-1 αντιστοιχίσεις είναι ισοδύναμες, αφού μπορούμε να φτάσουμε στην ίδια ταξινόμηση συνθέτοντας απλά την μετάθεση p με τη συνάρτηση f που χρησιμοποιούμε για τον ορισμό της ταξινόμησής μας.

Παράδειγμα. Ο πρώτος άνθρωπος θα εκτελούσε τον αλγόριθμο ταξινόμησης όπως στο βιβλίο:
Κώδικας: Ψευδογλώσσα
Αλγόριθμος φυσσαλίδα
Δεδομένα // table, n //
  Για i από 2 μέχρι n
    Για j από n μέχρι i με_βήμα -1
      Αν table[j-1] < table[j] τότε
        αντιμετάθεσε table[j-1], table[j]
      Τέλος_αν
    Τέλος_επανάληψης
  Τέλος_επανάληψης
Αποτελέσματα // table //
Τέλος φυσσαλίδα


Ο άραβας θα ξεκινούσε από το τέλος του πίνακα, όχι από την αρχή. Δηλαδή αντί για table[ι] θα χρησιμοποιούσε το table[n+1-(i)]:
Κώδικας: Ψευδογλώσσα
Αλγόριθμος φυσσαλίδα
Δεδομένα // table, n //
  Για i από 2 μέχρι n
    Για j από n μέχρι i με_βήμα -1
      Αν table[n+1-(j-1)] < table[n+1-(j)] τότε
        αντιμετάθεσε table[n+1-(j-1)], table[n-(j)]
      Τέλος_αν
    Τέλος_επανάληψης
  Τέλος_επανάληψης
Αποτελέσματα // table //
Τέλος φυσσαλίδα


Έτσι θα κατέληγε σε αντίστροφα ταξινομημένο πίνακα.
Ισχυρίστηκα ότι οι δύο τρόποι είναι ισοδύναμοι, άρα θα πρέπει να μπορούμε να βρούμε μια συνάρτηση f που να τους κάνει να έχουν το ίδιο αποτέλεσμα. Η συνάρτηση αυτή είναι η f(x) = -x. Έτσι ο κώδικας του άραβα γίνεται:
Κώδικας: Ψευδογλώσσα
Αλγόριθμος φυσσαλίδα
Δεδομένα // table, n //
  Για i από 2 μέχρι n
    Για j από n μέχρι i με_βήμα -1
      Αν -table[n+1-(j-1)] < -table[n+1-(j)] τότε   !Εδώ μπήκε το πλην
        αντιμετάθεσε table[n+1-(j-1)], table[n-(j)]
      Τέλος_αν
    Τέλος_επανάληψης
  Τέλος_επανάληψης
Αποτελέσματα // table //
Τέλος φυσσαλίδα

και πλέον έχει το ίδιο αποτέλεσμα με τον αρχικό τρόπο.

Ας συνοψίσω καλύτερα γιατί έγραψα πολλά. Πιστεύω ότι:
α) Η ταξινόμηση ορίζεται για οποιαδήποτε (πεπερασμένα) διατεταγμένα στοιχεία (όχι μόνο για μονοδιάστατους πίνακες). Έτσι, ταξινόμηση μπορεί να οριστεί για οποιαδήποτε στοιχεία μπορούν να μπουν στον υπολογιστή, αφού πάντα θα είναι πεπερασμένα και πάντα θα μπορούμε να τους ορίσουμε κάποια διάταξη (έστω κι αν αυτή είναι η διεύθυνσή τους στη RAM).
β) Δεν έχει σημασία η διάταξη που θα επιλέξουμε, αφού όλες οι 1-προς-1 διατάξεις είναι ισοδύναμες. Αρκεί να την ορίσουμε.

Με βάση τα παραπάνω, είναι δικαίωμά μου να θεωρήσω τη διάταξη που οι μονές θέσεις ενός μονοδιάστατου πίνακα είναι πριν από τα ζυγές, και έτσι η ταξινόμηση να μου βγει

Θέση:12345678910
Στοιχείο:16273849510
αρκεί βέβαια αυτό να μου είναι χρήσιμο σε κάποιο πρόβλημα που έχω. Δε θεωρώ δηλαδή αυτονόητο ότι στους μονοδιάστατους πίνακες, aι θα πρέπει πάντα να θεωρώ το A[ι].

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

alkisg

Τελικά νομίζω ότι μπορώ να το πω και πολύ πιο απλά:
Η διάταξη των στοιχείων a1, a2, ... an, δεν είναι μέρος της ταξινόμησης. Είναι στα δεδομένα του προβλήματος.

Την ορίζουμε λοιπόν αυθαίρετα με βάση το πρόβλημα που έχουμε και μετά ξεκινάμε να μιλάμε για ταξινόμηση.

Και πιο απλό παράδειγμα: ένας γυμναστής έβαλε τους μαθητές σε 3 στήλες x 8 γραμμές. Ταξινομήστε τους με βάση το ύψος γιατί θέλει να τους πάει σε παρέλαση. Οι ψηλότεροι πρέπει να είναι μπροστά και δεξιά.

Η διάταξη εδώ (και γενικά) είναι δεδομένο του προβλήματος, δεν αφορά την ταξινόμηση... Έτσι, οι τύποι μετατροπής που έδωσα παραπάνω είναι απλά μια συνάρτηση διάταξης ώστε να φτάσουμε τελικά στη ζητούμενη διάταξη a1, a2, ... an.

Όμως αυτό δε σημαίνει ότι η ταξινόμηση υφίσταται μόνο σε μονοδιάστατους πίνακες, ή ότι στους μονοδιάστατους πίνακες "είναι αυτονόητη" η συνάρτηση διάταξης g(i)=i. Η φυσσαλίδα μπορεί κάλλιστα να εφαρμοστεί και σε λίστα με pointers και records, ενώ μπορούμε σε μονοδιάστατο πίνακα να διατάξουμε τα στοιχεία από το κέντρο προς την άκρη ώστε η ταξινόμηση να έχει μορφή Gaussian κατανομής...

gpapargi

Καλημέρα

Και μένα μου αρέσει που «την ψάχνουμε» για να βρούμε ευκαιρίες για το μαθηματικό υπόβαθρο. Τελικά, μέσα από όλα αυτά αισθάνομαι ότι μαθαίνουμε πολλά. Μακάρι να ήταν πιο συχνές τέτοιες κουβέντες και μακάρι να συμμετείχαν περισσότεροι. Δεν μπορώ να ξεχάσω κάποτε που κάποιος μας ζήτησε συγνώμη που μας "διέκοψε"  :o

Καλά έκανες και τα έγραψες αναλυτικά στο πρώτο post γιατί κατάλαβα τι λες. Λοιπόν είναι σαφές το σημείο της διαφωνίας. Για μένα (έτσι όπως τα έχω στο κεφάλι μου δηλαδή) τα στοιχεία του μονοδιάστατου πίνακα είναι φυσικώς διατεταγμένα. Αυτό το λέω γιατί έχουν κάποιο δείκτη ο οποίος είναι φυσικός αριθμός στο [1,ν]. Επειδή η διάταξη στους φυσικούς είναι ορισμένη πιστεύω ότι και τα κελιά του πίνακα είναι διατεταγμένα.

Δεν είναι δηλαδή αυτό που στα μαθηματικά λέμε «σύνολα» στα οποία δεν υπάρχει διάταξη. Είναι κάτι σαν ακολουθίες, δηλαδή απεικονίσεις των φυσικών πάνω στους πραγματικούς (αν μιλάμε για πίνακες πραγματικών). Στον αριθμό 1 αντιστοιχεί το α[1], στο 2 το α[2] κλπ. Δηλάδή όπως στην ακολουθία αν αντιστοιχεί ο γενικός όρος της. Έτσι το α[1] είναι το πρώτο στοιχείο λόγω του δείκτη.

Έχει ενδιαφέρον το παράδειγμα του Έλληνα και του Άραβα. Ας πούμε ότι έχουμε τους αριθμούς 3, 5, 7 ,8 και θέλουμε να τα ταξινομήσουμε σε αύξουσα σειρά.

Ο Έλληνας (γραφή από αριστερά προς τα δεξιά) θα γράψει (πάνω γραμμή είναι η θέση και κάτω το αντίστοιχο στοιχείο):
1 2 3 4
3 5 7 8

Ο ʼραβας (γραφή από δεξιά προς τα αριστερά) θα γράψει:

4 3 2 1
8 7 5 3

Αν και φαίνονται ανάποδα στην πραγματικότητα έχουν κάνει το ίδιο πράγμα (αύξουσα ταξινόμηση). Έχουν αντιστοιχίσει το 1 με το 3 (δηλαδή το 3 στην πρώτη θέση). Απλά η πρώτη θέση για τον Έλληνα είναι αριστερά ενώ για τον ʼραβα είναι δεξιά. Η αντιστοίχισή τους όμως είναι η ίδια. . Δηλαδή η αυθαιρεσία είναι στον τρόπο ανάγνωσης/γραφής. Αυτό γιατί δεν υπάρχει διάταξη μεταξύ του αριστερά προς τα δεξιά και ο καθένας επιλέγει αυθαίρετα κάτι. Αντίθετα υπάρχει διάταξη μεταξύ των φυσικών.

Στην κλασσική αύξουσα ταξινόμηση χρησιμοποίησαν και οι 2 ordering function  την ταυτοτική συνάρτηση  f(x)=x. Ας πούμε ότι ο Έλληνας αποφασίζει να κάνει φθίνουσα ταξινόμηση, δηλαδή να χρησιμοποιήσει σαν ordering function  την f(x)=-x.

Ο Έλληνας θα γράψει:
1 2 3 4
8 7 5 3

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

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

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

alkisg

Εγώ επιμένω στη φράση του ορισμού "Δοθέντων των στοιχείων a1, a2, ..., an", οπότε θεωρώ ότι δεν μας ενδιαφέρει η μαθηματική διάταξη των στοιχείων, αλλά την ορίζουμε αυθαίρετα με βάση το πρόβλημα. Αφού την έχουμε ορίσει (=> "Δοθέντων"...) τότε ορίζουμε την ταξινόμηση.

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

10 άτομα θέλουν να ανεβούν στο βουνό με τελεφερίκ. Για ευκολία, ας πούμε ότι τα βάρη τους είναι τα πολλαπλάσια του 10, δηλαδή 10, 20, 30, ..., 100. Έτσι έχουμε τον παρακάτω αταξινόμητο πίνακα βαρών:

Θέση:12345678910
Βάρος:201090708040305010060

Το τελεφερίκ χωράει δύο άτομα, αλλά επειδή είναι παλιό δεν είναι σίγουροι για το όριο βάρους που αντέχει. Έτσι σκέφτηκαν να ταξινομηθούνε σε ζευγάρια, ώστε ο βαρύτερος να πάει με τον ελαφρύτερο, κοκ. Δηλαδή αυτοί που θα ανεβούνε μαζί στο τελεφερίκ είναι οι (1, 2), (3, 4), (5, 6), (7, 8 ), (9, 10):

Θέση: 12345678910
Βάρος:100109020803070406050

Τα ερωτήματα στην ουρά που δημιουργήθηκε (για τη συζήτησή μας, όχι για την κατασκευή του σχετικού αλγορίθμου!) είναι:

1) Αποτελεί ταξινόμηση η παραπάνω διάταξη;
Με βάση τον ορισμό της ταξινόμησης, αν και υπάρχουν συναρτήσεις (π.χ. f(x) = 0) που ικανοποιούν τον ορισμό, καμία συνάρτηση δε θα μπορούσε να μας δώσει μονοσήμαντα τη συγκεκριμένη ταξινόμηση. Το γιατί ακολουθεί.

2) Η έννοια της διάταξης των στοιχείων συμπεριλαμβάνεται ή προηγείται του προβλήματος της ταξινόμησης;
Αν θέλαμε να χρησιμοποιήσουμε μια συνάρτηση που να μπορεί να μας ταξινομήσει τα στοιχεία όπως φαίνονται στον παραπάνω πίνακα, θα έπρεπε να της περάσουμε παράμετρο και τη θέση του στοιχείου. Δηλαδή μια συνάρτηση ταξινόμησης f(x) δεν μπορεί να λύσει το παραπάνω πρόβλημα, όμως μια συνάρτηση f(x, θέση) θα μπορούσε.

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

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

gpapargi

Δε διαφωνώ ότι ο ορισμός του βιβλίο είναι γενικότερος του μονοδιάστατου πίνακα. Αλλά αυτό που λέω είναι ότι αν βάλεις τα στοιχεία σε μονοδιάστατο τότε αυτομάτως είναι διατεταγμένα.

Ουσιαστικά λέω κάτι σαν αυτό που λέει η σελίδα της wikipedia για τα array:
http://en.wikipedia.org/wiki/Array
«Arrays hold a sequence of data elements,»
Με το sequence να ορίζεται (ακουθώντας το link) ως:
«…a sequence is an ordered list of objects…»
Δηλαδή υπάρχει διάταξη των κελιών.

Είναι να έχεις 10 φυλακισμένους που μόλις ήρθαν στη φυλακή και 10 διπλανά κελιά αριθμημένα από το 1 μέχρι το 10. Όσο είναι ακόμα στην αυλή και περιμένουν συζητώντας μεταξύ τους είναι σύνολο χωρίς διάταξη. Από τη στιγμή που μπήκαν στα κελιά έγιναν ακολουθία με ορισμένη τη διάταξη.

Ουσιαστικά λέω ότι αν μπουν στον πίνακα η διάταξη είναι ορισμένη γιατί οι θέσεις είναι διατεταγμένες.
Νομίζω ότι η διαφορά είναι στο πότε ξεκινάει το πρόβλημα. Εσύ αντιμετωπίζεις τα δεδομένα πριν μπουν στον πίνακα και λες ότι δεν έχουν ορισμένη διάταξη. Σωστό μου φαίνεται. Εγώ τα αντιμετωπίζω αφού μπουν και γι αυτό μιλάω για ταξινόμηση μονοδιάστατου. Ασχολούμαι μαζί τους αφού έχουν μπει μέσα στην διατεταγμένη δομή. Κι αυτό σωστό μου φαίνεται.

Να το πω και αλλιώς. Έστω ότι έχω 4 ακεραίους. Χρησιμοποιώ τις μεταβλητές α, β , γ, δ για να τους αποθηκεύσω. Έχω λοιπόν:
α <- 4
β<- 8
γ <- 6
δ < - 7

Δεν υπάρχει διάταξη.

Ας πούμε ότι χρησιμοποιώ τις μεταβλητές χ1, χ2, χ3 χ4.

χ1 <- 4
χ2<- 8
χ3 <- 6
χ4 < - 7

Πάλι δεν έχω διάταξη γιατί το 1 δίπλα στο χ δεν είναι δείκτης (αριθμός) αλλά χαρακτήρας. Είναι χύμα ονόματα που θα μπορούσαν να είναι α, β , γ, δ. Είναι σύνολο.
Αν όμως τα βάλω σε πίνακα τότε έχω διάταξη. Δηλαδή αν έχω
χ[1] <- 4
χ[2]<- 8
χ[3] <- 6
χ[4] < - 7

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

alkisg

Δε διαφωνούμε σε αυτό:
Παράθεση από: gpapargi στις 09 Μαρ 2007, 01:48:38 ΜΜ
Αλλά αυτό που λέω είναι ότι αν βάλεις τα στοιχεία σε μονοδιάστατο τότε αυτομάτως είναι διατεταγμένα.

Διαφωνούμε σε αυτό (στα έντονα γράμματα):
Παράθεση από: gpapargi στις 09 Μαρ 2007, 01:48:38 ΜΜ
Αν όμως τα βάλω σε πίνακα τότε έχω διάταξη. Δηλαδή αν έχω
χ[1] <- 4
χ[2]<- 8
χ[3] <- 6
χ[4] < - 7
τότε έχω διάταξη και μπορώ να μιλήσω για ταξινόμηση.
Μιλώντας για ταξινόμηση μονοδιάστατου μιλώ για μετά τη στιγμή της αποθήκευσης σε μονοδιάστατο πίνακα. Πιστεύω πως έχω κάθε δικαίωμα να μιλώ για ταξινόμηση. Δεν έκανα κάποια αυθαίρετη παραδοχή εκτός αν θεωρήσω αυθαίρετη παραδοχή το ότι χρησιμοποίησα μονοδιάστατο πίνακα για να αποθηκεύσω τα δεδομένα. Αλλά μιλώντας για ταξινόμηση μονοδιάστατου αναφέρομαι στη στιγμή μετά την αποθήκευση στον μονοδιάστατο. Δε βλέπω κάτι στραβό.

Η αυθαιρεσία πιστεύω ότι είναι ότι θεωρείς ότι,
η διάταξη του μονοδιάστατου πίνακα A[1], A[2], ..., A[N] είναι και η διάταξη της ταξινόμησης, a1, a2, ..., an.

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

Διάταξη πίνακα:A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]A[10]
Διάταξη ταξινόμησης:a1a2a3a4a5a6a7a8a9a10
Βάρος:201090708040305010060

Το πρόβλημα όμως επιβάλλει διαφορετική διάταξη ταξινόμησης από τη διάταξη πίνακα:

Διάταξη πίνακα:A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]A[10]
Διάταξη ταξινόμησης:a1a10a2a9a3a8a4a7a5a6
Βάρος:201090708040305010060

Δηλαδή, σύμφωνοι, οι μονοδιάστατοι πίνακες έχουν διάταξη. Το δεύτερο στοιχείο του πίνακα είναι σίγουρα το Α[2] με βάρος 10 κιλά.
Όμως στην ταξινόμηση που ζητάμε, αν και τα δεδομένα είναι ήδη σε πίνακα, δεν μας ενδιαφέρει η διάταξη του πίνακα. Το a2 της ταξινόμησης είναι το 3ο στοιχείο του πίνακα, Α[3] με 90 κιλά. Εκεί είναι που θέλω να βάλω το δεύτερο μεγαλύτερο στοιχείο μετά την ταξινόμηση, όχι στο Α[2]...

Επομένως (πιστεύω ότι) με το που βάζουμε κάποια στοιχεία σε ένα πίνακα δε μας δίνεται αυτομάτως το δικαίωμα να μιλάμε για ταξινόμηση. Πρέπει πρώτα να ορίσουμε τη ζητούμενη διάταξη ταξινόμησης, έστω κι αν αυτή είναι η συνήθης, aί = A[ί].

gpapargi

Τα α1, α2, α3 κλπ δεν είναι διατεταγμένα γιατί τα 1,2,3 είναι απλοί αριθμοί (πχ 5, 7, 2, 8 ) όχι δείκτες (αριθμοί).

Μάλλον το μπέρδεμα γίνεται στο τι ακριβώς πρέπει να είναι διατεταγμένο. Θα εξηγήσω με βάση τη δική μου κατανόηση πως ακριβώς αντιλαμβάνομαι τον ορισμό της ταξινόμησης…  και το κουβεντιάζουμε.

Ας ξεχάσουμε για λίγο τους υπολογιστές, τους πίνακες και τις μεταβλητές. Το μόνο που έχουμε είναι μολύβι και χαρτί.
Έχουμε σκέτους αριθμούς πχ 5, 7, 2, 8 κλπ και θέλουμε να τους ταξινομήσουμε.

Σίγουρα θα χρειαστούμε κάποιο κριτήριο ταξινόμησης δηλαδή με βάση τι θα τους ταξινομήσουμε.  Αυτό το κριτήριο υλοποιείται με αυτό που το βιβλίο λέει ordering function. Πχ μπορεί να θέλουμε να τους βάλουμε σε σειρά ανάλογα με το ποιος έχει το πιο μεγάλο τετράγωνο. Τότε η ordering function είναι η f(x)=x^2. Μπορεί να θέλουμε να τα βάλουμε σε σειρά ανάλογα με το πιο δίνει την πιο μεγάλη τιμή στη συνάρτηση f(x)=(2*x^5+3)/(x-1). Τότε αυτή η f(x) είναι η ordering function.
Η κλασσική αύξουσα ταξινόμηση βάζει σε σειρά τους αριθμούς ανάλογα με την ίδια τους την τιμή. Θα έλεγε κανείς ότι δεν χρειάζεται ordering function. Ωστόσο και με αυτή δεν υπάρχει πρόβλημα. Είναι η f(x)=x δηλαδή αυτή που αφήνει τα στοιχεία αμετάβλητα. Δηλαδή η ordering function μας δίνει τη δυνατότητα να ταξινομήσουμε με βάση κάποιο κριτήριο γενικότερο από τις ίδιες τις τιμές.

Μέχρι εδώ πιστεύω ότι όλα είναι καλά και συμφωνούμε.

Αλλά δεν αρκεί το κριτήριο ταξινόμησης για να ξεκινήσει η ταξινόμηση. Θα πρέπει να ξέρουμε σε ποια φυσική θέση θα μπει το μικρότερο στοιχείο, σε ποια το δεύτερο μεγαλύτερο κλπ. Στην περίπτωσή μας που δουλεύουμε με μολύβι και χαρτί θα πρέπει να αποφασίσουμε σε ποιο σημείο του χαρτιού θα γράψουμε το μεγαλύτερο στοιχείο σε ποιο το δεύτερο μεγαλύτερο κλπ. Ό Άραβας θα βάλει το πρώτο στα δεξιά, το δεύτερο πιο αριστερά κλπ. Ο Έλληνας θα βάλει το πρώτο αριστερά το δεύτερο πιο δεξιά κλπ. Οι αρχαίοι που έγραφαν στην άμμο ενδεχομένως να έβαζαν το πρώτο πάνω, το δεύτερο αμέσως πιο κάτω κλπ.

Γενικά δηλαδή όλοι θα αποφάσιζαν σε πιο σημείο του χώρου θα φιλοξενηθεί το πρώτο, δεύτερο κλπ στοιχείο.

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

Πχ έχουμε 4 μεταβλητές. Τα ονόματά τους είναι @, $, # και &. Σκόπιμα επέλεξα τέτοια ονόματα (αν και παράνομα στην ΑΕΠΠ) για να μην έχω καμία σχέση με αριθμούς και γράμματα που θεωρούνται διατεταγμένα (αριθμητικά ή αλφαβητικά).
Οι μεταβλητές αυτές θα φιλοξενήσουν τα στοιχεία μας, αλλά πριν αρχίσει η ταξινόμηση θα πρέπει να ξεκαθαρίσω ποια θα φιλοξενήσει την πρώτη, ποια τη δεύτερη κλπ τιμή της ταξινόμησης. Πχ διαλέγω τη σειρά:
$    θα κρατήσει την πρώτη τιμή μετά την ταξινόμηση
&   θα κρατήσει τη δεύτερη τιμή μετά την ταξινόμηση
@  θα κρατήσει την τρίτη τιμή μετά την ταξινόμηση
#    θα κρατήσει την τέταρτη τιμή μετά την ταξινόμηση

Έτσι όρισα τη διάταξη μεταξύ των φυσικών χώρων που θα φιλοξενήσουν τους αριθμούς. Τώρα μπορώ να ξεκινήσω πχ με τη μέθοδο της φυσαλίδας. Θα είναι άκομψο γιατί δεν έχω τους πίνακες αλλά να πως μπορεί να γίνει:

! Αρχή πρώτης εξωτερικής επανάληψης της φυσαλίδας
Αν # < @ τότε αντιμετάθεσε #, @
Αν @ < & τότε αντιμετάθεσε @, &
Αν & < $  τότε αντιμετάθεσε &, $

! Αρχή δεύτερης εξωτερικής επανάληψης της φυσαλίδας
Αν # < @ τότε αντιμετάθεσε #, @
Αν @ < & τότε αντιμετάθεσε @, &

! Αρχή τρίτης εξωτερικής επανάληψης της φυσαλίδας
Αν # < @ τότε αντιμετάθεσε #, @

Τέλος. Τώρα με με εντολή Εμφάνισε $, &, @, # θα εμφανιστούν οι αριθμοί ταξινομημένοι σε αύξουσα σειρά.

Έγινα λίγο γραφικός  :-[ :laugh: αλλά θέλω να πω ότι πριν αρχίσουμε να μιλάμε για ταξινόμηση θα πρέπει να οριστεί η διάταξη. Η διάταξη είναι κάτι που ορίζεται μεταξύ των αποθηκευτικών χώρων που θα φιλοξενήσουν τις τιμές μας. Η ανάγκη της είναι προφανής. Πχ ας δοκιμάσει κάποιος να ταξινομήσει με φυσαλίδα 4 αριθμούς που έχουν αποθηκευτεί στις μεταβλητές α, β, γ, δ. Είναι αυτό που λέει το βιβλίο «[…] ώστε να τοποθετηθούν σε μια σειρά[…]». Εδώ δηλαδή ορίσουμε αυτή τη σειρά μεταξύ των αποθηκευτικών χώρων (ας είναι τα σημεία του χαρτιού που γράφουμε).

Η διάταξη λοιπόν εφαρμόζεται στους φυσικούς αποθηκευτικούς χώρους. Καθορίζεται έτσι που θα μπει το πρώτο στοιχείο, που θα μπει το δεύτερο κλπ. Δηλαδή είναι μια αντιστοίχηση θέσεων με το 1, το 2 το 3 κοκ.

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

Το παράδειγμα που αναφέρεις είναι κάτι άλλο. Θα προσπαθήσω να το αναλύσω.
Θέλεις να βάλεις στην πρώτη θέση το βαρύτερο, στη δεύτερη το ελαφρύτερο, στην τρίτη το δεύτερο βαρύτερο, στην τέταρτη το δεύτερο ελαφρύτερο κλπ.
Αν προσέξεις, έτσι όπως ορίζεις το τι θέλεις να κάνεις, θα πρέπει πρώτα να κάνεις μια συνηθισμένη ταξινόμηση, αλλιώς δε θα ξέρεις ποιο είναι το βαρύτερο, το ελαφρύτερο, το δεύτερο βαρύτερο κλπ. Ενδεχομένως παίζοντας με τα μαθηματικά να μπορούσες για τα συγκεκριμένα νούμερα που δίνεις να έβρισκες μια f(x) που να στα βάζει στη σειρά που θέλεις. Αλλά σίγουρα δε θα ίσχυε για άλλα νούμερα. Πρώτα θα πρέπει να γίνει συνήθης ταξινόμηση για να καταλάβεις πιο νούμερο θα μπει που.
Μετά την ταξινόμηση, θέλεις να κάνεις μια αλλαγή σειράς (μετάθεση) στη διάταξη των αποθηκευτικών χώρων για να τα φέρεις στην επιθυμητή μορφή. Αλλά δεν είναι  ταξινόμηση ως προς κάποια f. Είναι μια μετάθεση που έπεται (και δεν προηγείται) ταξινόμησης. Νομίζω δηλαδή ότι στο συγκεκριμένο παράδειγμα πρώτα ορίζεις τη διάταξη μεταξύ των αποθηκευτικών χώρων (για να μπορείς να κάνεις ταξινόμηση), μετά κάνεις ταξινόμηση και τέλος ξαναλλάζεις  τη διάταξη για να τα φέρεις στη σειρά που θέλεις. Αλλά δεν είναι πια ταξινομημένα.

Συνοψίζοντας, (κατά τη γνώμη μου) η διάταξη μεταξύ των αποθηκευτικών χώρων είναι ένα αναγκαίο κακό για να μπορείς μετά να κάνεις ταξινόμηση. Οι μονοδιάστατοι εξ’ορισμού την έχουν αυτή τη διάταξη στα κελιά τους. Τα α1, α2, α3 που λέει ο ορισμός είναι απλοί αριθμοί μη διατεταγμένοι σα να λέμε 5, 8, 3.

Δεν ξέρω αν θα συμφωνήσουμε, αλλά τουλάχιστο ας γίνει σαφής η άποψη που έχω διαμορφώσει μέχρι στιγμής.

alkisg

Δεν συμφωνούμε, αλλά νομίζω ότι καταλάβαμε και οι δύο τι λέει ο άλλος. Η διαφωνία μας είναι εδώ:
Παράθεση από: gpapargi στις 12 Μαρ 2007, 01:11:22 ΜΜ
Μετά την ταξινόμηση, θέλεις να κάνεις μια αλλαγή σειράς (μετάθεση) στη διάταξη των αποθηκευτικών χώρων για να τα φέρεις στην επιθυμητή μορφή. Αλλά δεν είναι  ταξινόμηση ως προς κάποια f. Είναι μια μετάθεση που έπεται (και δεν προηγείται) ταξινόμησης.

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

Παρόμοια θα λειτουργούσε και ο Άραβας: θα έπαιρνε τα στοιχεία του πίνακα ανάποδα, θα τα ταξινομούσε με αύξουσα σειρά, και σε μας τους Έλληνες το αποτέλεσμα θα φαινόταν ότι είναι με φθίνουσα σειρά.
Ε, δεν μπορούμε να του πούμε ότι δεν ταξινόμησε τον πίνακα, επειδή χρησιμοποίησε διαφορετική διάταξη για τα στοιχεία του. Δε μιλάω για τη συνάρτηση ταξινόμησης, κι αυτός f(x) = x χρησιμοποίησε, λέω για τη διάταξη: ότι δεν πήρε τα στοιχεία του πίνακα με την ορισμένη από τα μαθηματικά διάταξη (από αριστερά προς τα δεξιά) αλλά χρησιμοποίησε τη διάταξη ai = Α[Ν-i].

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

Υ.Γ. για το παραπάνω που είπα, ότι δεν θέλω να κάνω μετάθεση μετά την ταξινόμηση: όντως δε θα γίνει μετάθεση στο σχετικό πρόγραμμα. Απλά στην φυσσαλίδα αντί να λέω Α[ί] θα λέω Α[πίνακας_διάταξης_ταξινόμησης[ί]].

alkisg

Μιας και το σχολιάσαμε, ας ανεβάσω και το αντίστοιχο πρόγραμμα. Η εκφώνηση του προγράμματος είναι λίγο παραπάνω (το πρόβλημα με το τελεφερίκ).
Εγώ θεωρώ ότι αυτό είναι ταξινόμηση και ότι δεν περιλαμβάνει κάποιο επιπλέον στάδιο μετάθεσης. Απλά χρησιμοποιώ διαφορετική διάταξη από τη φυσική του πίνακα, δηλαδή τη συνάρτηση a που φαίνεται στο πρόγραμμα αντί για a(κ) = κ.

Κώδικας: ΓΛΩΣΣΑ
ΠΡΟΓΡΑΜΜΑ Τελεφερίκ
ΣΤΑΘΕΡΕΣ
  Ν = 10
ΜΕΤΑΒΛΗΤΕΣ
  ΠΡΑΓΜΑΤΙΚΕΣ: Βάρος[Ν]
  ΑΚΕΡΑΙΕΣ: ι, κ
ΑΡΧΗ
!Αρχικοποίηση του πίνακα, αντί για ΔΙΑΒΑΣΕ
  Βάρος[1] <- 20
  Βάρος[2] <- 10
  Βάρος[3] <- 90
  Βάρος[4] <- 70
  Βάρος[5] <- 80
  Βάρος[6] <- 40
  Βάρος[7] <- 30
  Βάρος[8] <- 50
  Βάρος[9] <- 100
  Βάρος[10] <- 60
!Ταξινόμηση φυσσαλίδας
  ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ Ν
    ΓΙΑ κ ΑΠΟ Ν ΜΕΧΡΙ ι ΜΕ_ΒΗΜΑ -1
      ΑΝ f(Βάρος[a(κ-1)]) < f(Βάρος[a(κ)]) ΤΟΤΕ
        ΚΑΛΕΣΕ Αντιμετάθεσε(Βάρος[a(κ-1)], Βάρος[a(κ)])
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΣΥΝΑΡΤΗΣΗ f(βάρος): ΠΡΑΓΜΑΤΙΚΗ
!Η f(x) από τον ορισμό της ταξινόμησης
ΜΕΤΑΒΛΗΤΕΣ
  ΠΡΑΓΜΑΤΙΚΕΣ:  βάρος
ΑΡΧΗ
  f <- βάρος
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

ΣΥΝΑΡΤΗΣΗ a(κ): ΑΚΕΡΑΙΑ
!Επιλέγει τα στοιχεία του πίνακα Βάρος με τη σειρά ταξινόμησης που θέλουμε,
!δηλαδή a1, a2, ..., an όπως φαίνονται στον ορισμό της ταξινόμησης
ΣΤΑΘΕΡΕΣ
  Ν = 10
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: κ
ΑΡΧΗ
  ΑΝ κ <= 5 ΤΟΤΕ
    a <- 2*κ - 1                 !Δηλαδή οι θέσεις 1, 3, 5, 7, 9
  ΑΛΛΙΩΣ
    a <- Ν - 2*(κ-6)            !Δηλαδή οι θέσεις 10, 8, 6, 4, 2
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

ΔΙΑΔΙΚΑΣΙΑ Αντιμετάθεσε(α, β)
ΜΕΤΑΒΛΗΤΕΣ
  ΠΡΑΓΜΑΤΙΚΕΣ: α, β, π
ΑΡΧΗ
  π <- α
  α <- β
  β <- π
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

gpapargi

#9
Καλημέρα

Το θέμα δεν είναι τόσο απλό. Χθες πριν σχολάσω (14:30) είδα το προτελευταίο σου post (το τελευταίο δεν το πρόλαβα) και επιτέλους κατάλαβα τι λες. Και αυτό χάρη στο παράδειγμά σου με τα κελιά των φυλακών και την ανακατεμένη αρίθμηση. Το παράδειγμα με τον Έλληνα και τον Άραβα έστειλε αλλού τη σκέψη μου καθώς και οι 2 θεωρούν σαν στοιχείο αποθήκευσης του μικρότερου το α[1]. Επίσης οι αναφορές στον ορισμό και τα α1, α2 κλπ με έκαναν να πιστεύω ότι θεωρείς δείκτες τα 1, 2 κλπ. Στο παράδειγμα με τις φυλακές κατάλαβα ότι θέλεις να κάνεις μια ταξινόμηση βάζοντας το πρώτο στοιχείο της ταξινόμησης στο α[3] το δεύτερο στο α[1] κλπ

Έκατσα και έφτιαξα τον ψευδοκώδικα ανεξάρτητα από εσένα και από ότι φαίνεται κάναμε ουσιαστικά το ίδιο πράγμα. Ας το κουβεντιάσουμε.

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

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

Για να το πετύχω αυτό χρησιμοποιώ ένα πίνακα β που περιέχει τη νέα διάταξη. Δηλαδή ισχύει:
β[1] = 3
β[2] = 1
β[3] = 4
β[4] = 2

Το β[1]=3 μας λέει ότι το πρώτο στοιχείο (μετά την ταξινόμηση) θα πρέπει να βρίσκεται στην τρίτη θέση του πίνακα α δηλαδή στο α[3].

Η τροποποίηση της φυσαλίδας δίνει τον αλγόριθμο
Για ι από 2 μέχρι 4
  Για j από 4 μέχρι ι με_βήμα -1
     Αν α[β[j]] < α[β[j-1]] τότε
         Αντιμετάθεσε α[β[j]], α[β[j-1]]
     Τέλος_αν
  Τέλος_επανάληψης
Τέλος_επανάληψης

Νομίζω πως λέμε το ίδιο.

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

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

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

alkisg

#10
Συνέχεια από το https://alkisg.mysch.gr/steki/index.php?topic=1237.msg8412#msg8412
επειδή λογικά η συζήτηση ταιριάζει εδώ

Παράθεση από: gpapargi στις 19 Μαρ 2008, 11:21:09 ΠΜ
Η φυσική διάταξη είναι συνυφασμένη με τη δομή του μονοδιάστατου. Αδύνατον να γίνει χρήση επαναληπτικής εντολής χωρίς αυτή.

Τυπικά, εγώ μένω στον ορισμό της διάταξης, ο οποίος δε μιλάει για μονοδιάστατους πίνακες.
Έστω ότι έχω μια συνάρτηση f(ί): pointer to integer η οποία επιστρέφει τη διεύθυνση του στοιχείου με σειρά διάταξης i που θέλουμε να ταξινομήσουμε, δηλαδή το στοιχείο ai. Χρειάζομαι μονοδιάστατο; Όχι.
Έστω ότι έχω μια script γλώσσα που υποστηρίζει hashes (javascript, php, perl...), όπου παίρνω το στοιχείο που θέλω με την κλασσική σύνταξη Α[ί], αλλά το Α δεν είναι πίνακας. Θα μπορούσα ισοδύναμα να χρησιμοποιώ Α["Αλέξης"] ή Α["ένα"]. Χρειάζομαι μονοδιάστατο; Όχι.

Ο μονοδιάστατος δηλαδή είναι μια μόνο υποπερίπτωση, δεν είναι αναγκαίος για την επαναληπτική δομή στην ταξινόμηση.

Τώρα στο αν "εννοείται" η σειρά των στοιχείων σε ένα μονοδιάστατο:
Φυσικά εννοείται, πρώτο είναι το A[1], δεύτερο το Α[2] κτλ.
Σε ένα δισδιάστατο συνήθως δεν εννοείται, δηλαδή το Α[1,2] δεν είναι σίγουρα πριν το Α[2,1].

Αυτό όμως (η φυσική σειρά των μονοδιάστατων) δε σημαίνει ότι είναι και η σειρά των στοιχείων που θέλω να ταξινομήσω.

Επομένως κάλλιστα μπορώ να πω
"δίνεται το διατεταγμένο σύνολο στοιχείων {A[2], A[1], A[4], A[3]}, ταξινομήστε το κατ' αύξουσα σειρά".
όπου Α πίνακας, και αυτός που θα το υλοποιήσει να χρησιμοποιήσει ένα hash για ευρετήριο και έτσι να μη μας νοιάζει ΚΑΘΟΛΟΥ ΜΑ ΚΑΘΟΛΟΥ η φυσική διάταξη των στοιχείων των μονοδιάστατων πινάκων σε αυτό το πρόβλημα.

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




edit: Τελικά τον ορισμό έψαχνα τόσο καιρό να πω:
Δεν ταξινομούμε πίνακες, ούτε μονοδιάστατους ούτε δισδιάστατους. Ταξινομούμε (διατεταγμένα) ΣΥΝΟΛΑ.

1) Τυχαίνει οι μονοδιάστατοι πίνακες να είναι σύνολα. Επομένως ορίζεται αυτοδίκαια η ταξινόμηση σ' αυτούς. Αλλά σ' αυτό το σημείο δεν πρέπει να ξεχνάμε ότι οι μονοδιάστατοι δεν είναι παρά ένα μικρό κομμάτι όλων των διατεταγμένων συνόλων, επομένως δεν πρέπει να τους σκεφτόμαστε σαν αλληλένδετους με την ταξινόμηση, απλά σαν ένα μικρό πεδίο εφαρμογής της.
2) Οι δισδιάστατοι δεν έχουν διάταξη, άρα δεν είναι σύνολα, άρα έτσι "σκέτοι" δεν ταξινομούνται. Αν ορίσω διάταξη, τότε γίνονται σύνολα και μπορώ να τους ταξινομήσω.
3) (το λεπτό σημείο του παρόντος topic): Αν πάρω τα στοιχεία ενός μονοδιάστατου πίνακα με διαφορετική σειρά, τότε όρισα ένα καινούργιο σύνολο που δεν έχει σχέση με τη διάταξη του αρχικού πίνακα. Φυσικά αφού είναι σύνολο μπορώ κι αυτό να το ταξινομήσω, αλλά δεν "ανακατεύεται" στη διαδικασία η φυσική διάταξη του μονοδιάστατου.
4) (η υποπερίπτωση με το ευρετήριο): Αν χρησιμοποιήσω ευρετήρια, hashes, lists, μονοδιάστατους, δισδιάστατους κι ένα σωρό άλλες δομές, πάλι αυτό που μετράει είναι το αρχικό αταξινόμητο σύνολο και το τελικό ταξινομημένο. Τι ταξινομώ τελικά; Αν τα στοιχεία μου A1, A2 κτλ είναι σε δισδιάστατο, θεωρώ ότι ταξινομώ το δισδιάστατο, ακόμα κι αν δεν τον πειράζω καθόλου και αλλάζω μόνο το ευρετήριο. Δεν θεωρώ ότι ταξινομώ το ευρετήριο. Το ευρετήριο είναι απλά ένα προγραμματιστικό βοήθημα που με βολεύει στο να εκφράσω την τελική διάταξη Ak1, Ak2 κτλ με λιγότερη υπολογιστική ισχύ.

gpapargi

Παράθεση από: alkisg στις 19 Μαρ 2008, 01:25:40 ΜΜ
edit: Τελικά τον ορισμό έψαχνα τόσο καιρό να πω:
Δεν ταξινομούμε πίνακες, ούτε μονοδιάστατους ούτε δισδιάστατους. Ταξινομούμε (διατεταγμένα) ΣΥΝΟΛΑ.

1) Τυχαίνει οι μονοδιάστατοι πίνακες να είναι σύνολα. Επομένως ορίζεται αυτοδίκαια η ταξινόμηση σ' αυτούς. Αλλά σ' αυτό το σημείο δεν πρέπει να ξεχνάμε ότι οι μονοδιάστατοι δεν είναι παρά ένα μικρό κομμάτι όλων των διατεταγμένων συνόλων, επομένως δεν πρέπει να τους σκεφτόμαστε σαν αλληλένδετους με την ταξινόμηση, απλά σαν ένα μικρό πεδίο εφαρμογής της.
2) Οι δισδιάστατοι δεν έχουν διάταξη, άρα δεν είναι σύνολα, άρα έτσι "σκέτοι" δεν ταξινομούνται. Αν ορίσω διάταξη, τότε γίνονται σύνολα και μπορώ να τους ταξινομήσω.

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

Αυτό που με απασχόλησε σα λεπτομέρεια (αν και δεν έχει και τόσο νόημα αν συμφωνούμε ότι έχω δικαίωμα να κάνω ταξινόμηση στον μονοδιάστατο χωρίς να ορίσω διάταξη) είναι αν στην περίπτωση που αλλάξω τη διάταξη κελιών με hash function κάνω κάπου (έστω και σιωπηλά) χρήση της φυσικής διάταξης κάποιου μονοδιάστατου ή αν χαλάω την απόδοση.

Το ερώτημα βέβαια είναι κάπως φιλοσοφικό. Πχ αν παίξουμε με όλα τα όπλα μπορούμε να κάνουμε απευθείας προσπέλαση στη μνήμη και να αποθηκεύσουμε σε διαδοχικές θέσεις της μνήμης τις διευθύνσεις (δείκτες) των μεταβλητών α, β, γ, δ (που μπορεί να βρίσκονται σε μη διαδοχικές θέσεις). Βηματίζοντας με τη βοήθεια των δεικτών κάνουμε ότι θέλουμε. Κάποιος θα μπορούσε να πει «Δεν χρησιμοποιήσαμε πίνακα». Και κάποιος άλλος θα μπορούσε να πει «σαρώνουμε διαδοχικές θέσεις μνήμης και άρα κάνουμε χρήση της φυσικής διάταξης τους». Και εδώ το θέμα γίνεται φιλοσοφικό.

Με αφορμή την κουβέντα, έριξα μια ματιά στις hash functions και ουσιαστικά μιλάμε για perfect hashing δηλαδή σε απεικονίζουμε το [1..Ν] στο [1..Ν] και διαφορετική είσοδος έχει διαφορετική τιμή της συνάρτησης hash (για να μην έχουμε αναζητήσεις μετά). Είδα ότι γίνεται χρήση της διαδοχικότητας (ανά ομάδες και όχι συνολικά) θέσεων μνήμης για να επιτευχθεί η άμεση προσπέλαση. Προφανώς δεν ταξινομώ το ευρετήριο. Με απασχόλησε απλά αν κάνω κάπου χρήση της φυσικής διάταξης. Η πληροφορία ταξινόμησης αφορά τα στοιχεία μου.

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

alkisg

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

Από θέμα υλοποίησης: μην κοιτάς την απόδοση. Δεν εξαρτάται ο ορισμός της ταξινόμησης από τους αλγόριθμους ταξινόμησης ή την απόδοσή τους.
Ακόμα όμως και στους αλγόριθμους ταξινόμησης, ακόμα κι αν χρειάζομαι Ο(Ν) (!!!!!) για να προσπελάσω μια hashed μεταβλητή, π.χ. η φυσαλίδα παραμένει Ο(Ν^2) και δε γίνεται Ο(Ν^3), επειδή είμαστε σε επίπεδο αλγορίθμου και θεωρούμε ότι οι προσπελάσεις των στοιχείων γίνονται σε Ο(1). Φυσικά αν θελήσουμε να υπολογίσουμε τη τάξη της συγκεκριμένης υλοποίησης με τη συγκεκριμένη γλώσσα, τις συγκεκριμένες βιβλιοθήκες, το συγκεκριμένο compiler και στη συγκεκριμένη αρχιτεκτονική υπολογιστή, τότε όντως θα μιλήσουμε για Ο(Ν^3) και θα καταλήξουμε π.χ. στο ότι δε συμφέρουν τα hashes ή ότι δε συμφέρει η φυσαλίδα.

Παράθεση από: gpapargi στις 20 Μαρ 2008, 01:38:17 ΜΜ
Και κάποιος άλλος θα μπορούσε να πει «σαρώνουμε διαδοχικές θέσεις μνήμης και άρα κάνουμε χρήση της φυσικής διάταξης τους». Και εδώ το θέμα γίνεται φιλοσοφικό.
Οι διαδοχικές θέσεις μνήμης δεν είναι αποκλειστικό προτέρημα των πινάκων! *(p+10) στη C σε πάει στη 10η θέση μετά το δείκτη p χωρίς να εμπλακούν πίνακες!
Αλλά με hash function δεν είναι απαραίτητο να χρησιμοποιούνται συνεχόμενες θέσεις μνήμης (ούτε καν στην υλοποίηση του hash), οπότε μπορεί να γίνει υλοποίηση ταξινόμησης ενός συνόλου χωρίς να χρησιμοποιηθούν πουθενά ούτε πίνακες ούτε η φυσική τους διάταξη.

Ωραία, 1 χρόνο μετά συμφωνούμε πλήρως!!! :)

mmsoft

Κατ' αρχήν (αν και λίγο καθυστερημένα) πρέπει να ευχαριστήσουμε τους συζητητές στο θέμα της ταξινόμησης,
για την έκταση και την ευκρίνεια της άποψής τους.
Η επιχειρηματολογία που παρουσιάστηκε μας έκανε όλους σοφότερους.

Παρακαλώ να μου επιτρέψετε να διατυπώσω την δική μου άποψη.

Σε ορισμένους διανυσματικούς χώρους (στοιχείων χ,ψ), μπορούμε να ορίσουμε διμελείς σχέσεις διάταξης.
Έτσι, [δ(χ,ψ) είναι αληθής] ορίζεται ταυτόσημο με [αληθεύει ότι χ>ψ].
Αν ενίοτε αληθεύει και η διμελής σχέση ισότητας των χ,ψ, μπορούμε να γράψουμε συνοπτικά [αληθεύει ότι χ>=ψ]. 

Στο σύνολο ακεραίων έχουμε ορίσει σχέση διάταξης. Παράδειγμα: [αληθεύει ότι 7>5].
Στο σύνολο μιγαδικών δεν έχουμε ορίσει σχέση διάταξης. Δεν μπορούμε να πούμε ότι ένας μιγαδικός είναι μεγαλύτερος από κάποιον άλλο.
Γι αυτό μίλησαν κάποιοι για διατεταγμένα σύνολα. Σωστά.
Δεν είναι όλα τα σύνολα διατεταγμένα.

Η τοποθέτηση των στοιχείων με μιά σειρά, ώστε να αληθεύει η σχέση διάταξης για κάθε δύο διπλανά στοιχεία, είναι ταξινόμηση.
Δεν μπορούμε να ταξινομήσουμε αν δεν έχει οριστεί διμελής σχέση διάταξης.
(Δεν έχουμε συνθήκη για το ΑΝ ΤΟΤΕ).

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

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

Και τώρα ένα πρακτικό θέμα με εντολές της ΓΛΩΣΣΑΣ.
Θέλουμε να ταξινομήσουμε κάποιους αριθμούς μέσα σε έναν μονοδιάστατο πίνακα Α[από 1 μέχρι Ν].
Δεν θα ήταν απλούστερο (και για τους μαθητές) να το κάνουμε όπως παρακάτω;

! από το πρώτο μέχρι το προτελευταίο
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν-1
! και από το επόμενο μέχρι το τελευταίο
ΓΙΑ Κ ΑΠΟ Ι+1 ΜΕΧΡΙ Ν
! συνθήκη με [> για αύξουσα], [< για φθίνουσα]
  ΑΝ Α[Ι] > Α[Κ] ΤΟΤΕ
   Τ <- Α[Ι]
   Α[Ι] <- Α[Κ]
   Α[Κ] <- Τ
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Κάποια στοιχεία ανεβαίνουν, ακριβώς όσα κατεβαίνουν.
Τι χρειάζεται το (ΜΕ_ΒΗΜΑ -1) του βιβλίου;

Ευχαριστώ και πάλι

evry

  Ο αλγόριθμος που δίνεις είναι ουσιαστικά η ταξινόμηση με επιλογή. Δηλαδή σε κάθε βήμα βρίσκεις το μέγιστο και το ανταλλάσεις με το Ι στοιχείο.
Αν αυτό που ζητάς είναι η απλότητα θα μπορούσες να γράψεις κάτι σαν το παρακάτω

Κώδικας: ΓΛΩΣΣΑ
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν-1
    μ <-- ΘέσηΜεγίστου(Ι,Α)
   Τ <- Α[Ι]
   Α[Ι] <- Α[μ]
   Α[μ] <- Τ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


όπου η συνάρτηση ΘέσηΜεγίστου(Ι, Α) επιστρέφει τη θέση του μέγιστου στοιχείου του υποπίνακα Α[Ι+1....Ν]
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr