2η Γραπτή Εργασία: Πώς η Βαρύτητα (Gravity Sort) μου χάλασε τα Χριστούγεννα

Είναι εκείνη η εποχή του χρόνου. Τα μελομακάρονα βγαίνουν στα ράφια, τα λαμπάκια ανάβουν και το Ελληνικό Ανοικτό Πανεπιστήμιο (ΕΑΠ) αποφασίζει να στείλει το δικό του δώρο: Την 2η Γραπτή Εργασία.

Ημερομηνία παράδοσης: 4 Ιανουαρίου 2026 Με λίγα λόγια: Ρεβεγιόν με τον compiler.

Άνοιξα την εκφώνηση (12 σελίδες παρακαλώ) και το μάτι μου έπεσε στην Υποεργασία 2. Ξεχάστε τα Bubble Sort και Quick Sort. Φέτος έχουμε... φυσική.

Το Κτήνος: Bead Sort (ή Gravity Sort)

Η εκφώνηση ζητάει να υλοποιήσουμε τον αλγόριθμο Bead Sort. Η ιδέα είναι απλή αλλά ιδιοφυής: Έχεις αριθμούς που αναπαρίστανται από "χάντρες" σε οριζόντιες σειρές. Τις αφήνεις να πέσουν λόγω βαρύτητας και – ως εκ θαύματος – καταλήγουν ταξινομημένες.

Η Θεωρία (στα χαρτιά φαίνεται εύκολο)

Φανταστείτε έναν άβακα.

1. Κάθε αριθμός είναι μια σειρά από χάντρες (οριζόντια).
2. Γυρνάς τον άβακα κάθετα.
3. Οι χάντρες πέφτουν στα χαμηλότερα δυνατά σημεία.
4. Μετράς τις χάντρες από κάτω προς τα πάνω και έχεις τους αριθμούς σε αύξουσα σειρά.

Η Υλοποίηση (εδώ κλάψαμε)

Το πρόβλημα δεν είναι η ιδέα. Το πρόβλημα είναι πώς μεταφράζεις τις "χάντρες" και τα "κοντάρια" σε πίνακες της C.

Η εκφώνηση μας δίνει ένα hint: Χρειαζόμαστε έναν βοηθητικό πίνακα counts που μετράει πόσες χάντρες υπάρχουν σε κάθε κάθετο "κοντάρι".

Ουσιαστικά, ο αλγόριθμος δουλεύει σε 4 βήματα:

1. Διάβασμα: Παίρνουμε τους αριθμούς (με αμυντικό προγραμματισμό, μην ξεχνιόμαστε, τιμές 0-100).
2. Μέτρημα (counts): Αντί να μετακινούμε χάντρες μία-μία, μετράμε πόσες χάντρες έχει κάθε στήλη.
3. Ανακατασκευή (B): Φτιάχνουμε τον ταξινομημένο πίνακα B κοιτώντας τον πίνακα counts.
4. Εκτύπωση: Τα αποτελέσματα στην οθόνη.

Ιδού μια γεύση από την "λογική" της πτώσης σε ψευδο-C (χωρίς να δίνω τη λύση, κύριε Καθηγητά!):

// Φανταστικός κώδικας που προσομοιώνει τον πόνο
// N = 10 (γραμμές), M = 50 (μέγιστη τιμή)
 
int counts[M]; // Τα "κοντάρια"
 
// Βήμα 2: Γέμισμα των κονταριών
for (each number in InputArray) {
    // Για κάθε αριθμό, πρόσθεσε μια "χάντρα" στα αντίστοιχα κοντάρια
    // Εδώ είναι το σημείο που μπερδεύτηκα 3 φορές με τα indexes.
    // Θυμήσου: Στη C οι πίνακες ξεκινάνε από το 0.
}

Το παγόβουνο του Αμυντικού Προγραμματισμού

Το ΕΑΠ έχει μια εμμονή (και μεταξύ μας, καλά κάνει) με τον "αμυντικό προγραμματισμό". Στην Υποεργασία 1 με τις πυρκαγιές, αν ο χρήστης δώσει αρνητικό αριθμό φωτιάς, πρέπει να του πούμε "Μη έγκυρη τιμή. Ξαναπροσπάθησε".

Στο Bead Sort, πρέπει να ελέγχουμε αν οι αριθμοί είναι μεταξύ 0 και 100.

Εισάγετε το στοιχείο 4: -1
Η τιμή που εισάγετε πρέπει να είναι μεταξύ 0 και 100. Επαναλάβετε την είσοδο.

Αυτό το do-while loop το έχω γράψει τόσες φορές που το βλέπω στον ύπνο μου. Σε έναν ιδανικό κόσμο, θα έφτιαχνα μια Function (Συνάρτηση) και θα τελείωνα. Αλλά στο ΕΑΠ, η εκφώνηση ήταν σαφής: "Χωρίς χρήση συναρτήσεων". Οπότε, copy-paste και άγιος ο Θεός.

Συμπέρασμα

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

Τώρα, αν με συγχωρείτε, πάω να παλέψω με την Υποεργασία 3: Πίνακες δύο διαστάσεων και αποστάσεις πόλεων. Ελπίζω να μην χαθώ στη διαδρομή.