Περιγραφή:C-ταξινόμηση

[xorxia]

Καλησπέρα σας..καινούρια στο forum και άσχετη με τη γλώσσα προγραμματισμου C....Παρακάτω αναφέρω το πρόβλημα που έχω στην υλοποίηση ενός προγράμματος και ελπίζω κάποιος απο εσάς να καταφέρει να με βοηθήσει...Θέλω να υλοποιήσω τον αλγόριθμο bin sort με τον εξής τρόπο :Η μέθοδος αυτή ξεκινά με μια μονοδιάστατη διάταξη data N στοιχείων που περιέχει τους προς ταξινόμηση αριθμούς και μία δισδιάστατη διάταξη ακεραίων bucket που αποτελείται από 10 γραμμές και N στήλες.H δέσμευση του αντίστοιχου χώρου στις διατάξεις γίνεται

δυναμικά. Κάθε γραμμή στη διασδιάστατη διάταξη είναι ένα κάδος στον οποίο κάθε φορά αποθηκεύονται κάποιοι από τους αριθμούς εισόδου. Ο i-στος κάδος είναι η γραμμή i της διάταξης bucket (i=0,1,2,...,9). Η ταξινόμηση επιτυγχάνεται με την ακόλουθη μέθοδο:

1. Διατρέχουμε τις θέσεις της διάταξης data και τοποθετούμε καθέναν από τους αριθμούς που περιέχονται σε αυτήν σε εκείνο τον κάδο d0 όπου d0 είναι το τελευταίο ψηφίο στη δεκαδική αναπαράσταση του τρέχοντος αριθμού (δηλαδή το ψηφίο των μονάδων). Για παράδειγμα, το 97 θα μπει στη γραμμή 7, το 3 στην γραμμή

3, το 100 στην γραμμή 0 και το 67 στην γραμμή 7 (μετά το 97).

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

Για παράδειγμα η νέα διάταξη των τεσσάρων αριθμών στο μονοδιάστατο array θα είναι 100, 3, 97 και 67.

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

ταξινομηθεί σωστά μετά και την επεξεργασία του αριστερότερου ψηφίου του μεγαλύτερου αριθμού. Με το δεύτερο πέρασμα της μονοδιάστατης διάταξης data, το 100 τοποθετείται στη γραμμή 0 του bucket, το 3 στη γραμμή 0 αμέσως μετά το 100 (αφού έχει μόνο ένα ψηφίο), το 97 στη γραμμή 9 και το 67 στη γραμμή 6.

Τοποθετώντας τους αριθμούς πίσω στη μονοδιάστατη διάταξη data, η διάταξή τους είναι τώρα 100, 3, 67 και 97. Με το τρίτο και τελευταίο πέρασμα, το 100 τοποθετείται στη γραμμή 1, το 3 στη γραμμή 0, το 67 στη γραμμή 0 (μετά

το 3) και το 97 στη γραμμή 0 (μετά το 67). Τοποθετώντας τους αριθμούς πίσω στη μονοδιάστατη διάταξη data παίρνουμε τελικά την διάταξη 3, 67, 97 και 100.

 

Αρχικά κατάφερα να υλοποιήσω μονο το πρώτο στάδιο.Και έχω κολλήσει στο δευτερο...

Αν κάποιος έχει να προτείνει μια λύση....

 

 

-----Προστέθηκε 19/1/2009 στις 05 : 24 : 49-----

 

 

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