Χρήστης:Botaki/πρόχειρο2

Μη συγκριτικοί αλγόριθμοι ταξινόμησης

Οι μη συγκριτικοί αλγόριθμοι ταξινόμησης είναι μία κατηγορία αλγορίθμων που δεν περιορίζονται από το θεμελιώδες κάτω φράγμα $\Omega (n\log n)$ των συγκριτικών. Σε αντίθεση όμως με τους συγκριτικούς, οι οποίοι απαιτούν απλά μία συνάρτηση σύγκρισης, ο σχεδιασμός και η απόδοση των συγκριτικών αλγορίθμων εξαρτάται άμεσα από το είδος των στοιχείων που ταξινομούν.

Ταξινόμηση με απαρίθμηση (Counting sort)

Η ταξινόμηση με απαρίθμηση αποτελεί τον πιο απλό μη συγκριτικό αλγόριθμο ταξινόμησης. Θα τον αναλύσουμε μέσα από ένα παράδειγμα. Υποθέτουμε ότι στις Πανελλαδικές εξετάσεις θέλουμε να ταξινομήσουμε τους βαθμούς που πήραν οι μαθητές από τους βαθμολογητές. Οι βαθμοί αυτοί είναι ακέραιοι με τιμές από 0 έως και 100. Ο αλγόριθμος της ταξινόμησης με απαρίθμηση κάνει το εξής απλό. Μετράει πόσα άτομα πήραν τον κάθε βαθμό σε έναν πίνακα από μετρητές και μετά αρχίζει και βάζει με τη σειρά από το 0 έως το 100 τόσους βαθμούς όσους λένε οι μετρητές. Η πολυπλοκότητα του αλγορίθμου είναι $\mathrm {O} (n+k)$, όπου n το μέγεθος της εισόδου και k ο μέγιστος σε τιμή αριθμός που περιέχει η είσοδος. Από αυτό συμπεραίνουμε ότι ο αλγόριθμος είναι αποδοτικός μόνο για μικρές τιμές του k, το οποίο στη γενική περίπτωση μπορεί να είναι εκθετικά μεγάλο ως προς το μέγεθος (σε bit) της εισόδου.

συνάρτηση countingSort(πίνακας, κ) είναι
  μετρητής ← νέος πίνακας από κ μηδενικά
  για ι = 1 μέχρι μέγεθος_του(πίνακας) κάνε
    μετρητής[πίνακας[ι]] ← μετρητής[πίνακας[ι]] + 1
  για ι = 2 μέχρι κ κάνε
    μετρητής[ι] ← μετρητής[ι] + μετρητής[ι - 1]
  για ι = μέγεθος_του(πίνακας) μειούμενο_μέχρι 1 κάνε
    έξοδος[μετρητής[πίνακας[ι]]] ← πίνακας[ι]
    μετρητής[πίνακας[ι]] ← μετρητής[πίνακας[ι]] - 1
  επέστρεψε έξοδος