Ταξινόμηση πίνακα

[paparovic]

Και τι στόχο θα είχε να κάνει sort σε κάθε γέμισμα τιμής

 

Να διατηρείται το array sorted, σε κάθε βήμα, αντί για όλο μαζί στο τέλος.

[solarpower]

Παίζει και αυτό που λες αν κάθε φορά μετακινούσε τα στοιχεία για να βάλει απευθείας στην θέση του το στοιχείο, κάτι με Binary Search, και μετακίνηση στοιχείων για εισαγωγή τιμής, στη χειρότερη περίπτωση θα έχουμε (Μ-1)*(Μ-2) μεταφορές, χώρια τις αναζητήσεις/ Όμως το εύρος τιμών 100 μέχρι 999 δηλώνει την χρήση του lookup table. Μιλάμε για 900 θέσεις, και Μ αυξήσεις τιμών στην πρώτη περίπτωση και Ν αυξήσεις τιμών στην δεύτερη, καθώς και σάρωση 900 θέσεων για να φτιαχτεί ο Μ πίνακας και άλλες τόσες ο Ν πίνακας.

Για μικρό αριθμό Μ και Ν στοιχείων με την λύση του Binary Search και μετακίνηση στοιχείων, κερδίζει το Lookup table.

[zafgr]

Σας ευχαριστώ όλους για τις απαντήσεις σας,

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

[solarpower]

Το lookup table έχει σαν index τα data, και σαν περιεχόμενο το πλήθος τους (ή άλλη πληροφορία, αλλά εδώ θέλουμε το πλήθος). Η rand() μέσα από μια κατάλληλη έκφραση δίνει αριθμούς από 100 έως 999, Μ φορές. Αυτό δεν το πηγαίνουμε απευθείας στο πίνακα, αλλά το πάμε στο lookup table, και αυξάνουμε πχ  για το 999 το b[999] (ή όπως θα δεις ως b[899]) το περιεχόμενό του κατά 1. Μόλις η παραγωγή από τη rand τελειώσει, θα έχουμε ένα πίνακα με ορισμένα index όπου το b[index]>0. Αν λοιπόν τα πάρουμε από την αρχή, από Index 100 (μπορούμε το πίνακα να τον βάζουμε από 0 έως 899 και να τον λογαριάζουμε ότι είναι 100 έως 999), τότε με τη χρήση μιας μεταβλητής ως δρομέας (όπως αυτό που βλέπεις στο terminal και αναβοσβήνει), που δείχνει δηλαδή που θα γράψουμε στο πίνακα Μ, θα μπορέσουμε διαβάζοντας τον Β[] να γράψουμε τελικά όλα τα νούμερα που έδωσε η rand() χωρίς να ταξινομήσουμε, και θα είναι ταξινομημένα. Αυτό γίνεται γιατί διαβάζουμε από τον Β[] από το μικρότερο index μέχρι το μεγαλύτερο, άρα κάθε φορά, μετά τη πρώτη θέση θα βάζουμε στο δρομέα, ίσο ή μεγαλύτερο από το προηγούμενο, άρα να η ταξινόμηση!

Η άσκηση που σας έβαλε είναι πονηρή γιατί το διάστημα 100 έως 999 έχει δυο παραξενιές:

1. μπορεί κάποιος να την πατήσει με το πρόβλημα του off-by-one error  δες εδώ: https://en.wikipedia.org/wiki/Off-by-one_error, (αν προσθέσεις το πλήθος Χ στο offset Y θα πας σε μια θέση Χ+Υ που είναι εκτός πίνακα Χ στοιχείων)

2. ξεκινάει από το 100 για να αφαιρέσει το 100 από το LookUp table index. (αν είχε από 0 έως 999 θα ήταν πιο εύκολο).

 

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

[k33theod]

Για να γεμίζει ο πίνακας σου ομαλά κάντα στην αρχή όλα μεγαλύτερα του επιτρεπόμενου 1000 πχ οπότε θα έχεις πάντα τα στοιχεία σου 

στην αρχή εάν έχεις δηλαδή 10 στοιχεία θα καταλαμβάνουν τις θέσεις P[0]-P[9] τα άλλα θα είναι 1000αρια

 

Επειδή ο πίνακας είναι πάντα sorted, όποτε η rand σου δίνει νέο στοιχείο δεν ξεκινάς να ψάχνεις τη θέση του από την αρχή αλλά από τη μέση των στοιχείων που έχεις ήδη η τρέχουσα δηλαδή τιμή του i/2, μετά τη μέση της μέσης κλπ binary search δηλαδή

Έστω η rand σου δίνει το 13 στοιχείο

εσύ το συγκρίνεις με το 13/2 το 6ο δηλαδή αν είναι ασ πούμε μεγαλύτερο με τη μέση του 7 εώς 13 το 10ο κλπ. Ψάξτο σαν binary search

 

 

Τον καινούργιο πίνακα τον κανεις ώς εξής: ξεκινάς από τα P1[0] P2[0] βάζεις το μικρότερο στη θέση 0 του νέου πίνακα που έχει Μ+Ν στοιχεία και μεγαλώνεις το δείκτη του, μεγαλώνεις και τον δείκτη του πίνακα που πήρες το στοιχείο, όταν κάποιος δείκτης γίνει μέγιστος Μ ή Ν (ο πίνακας άδειασε) ξεκινάς και βάζεις και τα υπόλοιπα στοιχεία του άλλου πίνακα μεγαλώνοντας τον αντίστοιχο δείκτη. Ψάξτο σαν merge sort 

[defacer]

Εγώ αυτό που καταλαβαίνω είναι ότι θέλει σταδιακό γέμισμα των πινάκων με insertion sort (binary κιόλας? ταιριάζει), και μετά merge sort τα αποτελέσματα.

 

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

[zafgr]

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

 σε μία προσπάθεια σήμερα για διευκρινήσεις μας είπε ότι είναι πολύ απλό και δε χρειάζεται κανένας αλγόριθμος , με χρήση της if ....

τώρα μπερδεύτηκα περισσότερο....

Σκεφτόμουν στην αρχή να δώσω με την rand τιμή μόνο για την a[0] και μετά ορίζοντας μια μεταβλητή την rand() και με χρήση της if να δώσω και στον υπόλοιπο πίνακα....

[paparovic]

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

 σε μία προσπάθεια σήμερα για διευκρινήσεις μας είπε ότι είναι πολύ απλό και δε χρειάζεται κανένας αλγόριθμος , με χρήση της if ....

τώρα μπερδεύτηκα περισσότερο....

Σκεφτόμουν στην αρχή να δώσω με την rand τιμή μόνο για την a[0] και μετά ορίζοντας μια μεταβλητή την rand() και με χρήση της if να δώσω και στον υπόλοιπο πίνακα....

 

Ειλικρινά λυπάμαι και εκνευρίζομαι. Υπομονή να φύγεις από το μπουρδέλο.

[defacer]

σε μία προσπάθεια σήμερα για διευκρινήσεις μας είπε ότι είναι πολύ απλό και δε χρειάζεται κανένας αλγόριθμος , με χρήση της if ....

 

Είμαστε σίγουροι ότι αυτός που βάζει την άσκηση ξέρει τι είναι insertion sort και πως αν το "με χρήση της if" σημαίνει "if μέσα σε loop ίσον insertion sort" θα το έλεγε;

 

Είναι για κλάματα και μόνο που ρωτάω ειλικρινά.

[zafgr]

Αυτό που είπε είναι να βάλουμε μία do{} while() me if ,else if μέσα και να δημιουργείτε έτσι ενας ταξινομημένος πίνακας.

Δεν έχουμε διδαχθεί ακόμα αλγόριθμους παρά μόνο τη φυσαλίδα .Από μόνος μου ψάχνοντας βρήκα και το insection sort και γενικά ψάχνομαι απο tutorials πιό πολύ.

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

Επεξ/σία 2 Νοεμβρίου 2017 από zafgr

[defacer]

Αυτό που είπε είναι να βάλουμε μία do{} while() me if ,else if μέσα και να δημιουργείτε έτσι ενας ταξινομημένος πίνακας.

Δεν έχουμε διδαχθεί ακόμα αλγόριθμους παρά μόνο τη φυσαλίδα .Από μόνος μου ψάχνοντας βρήκα και το insection sort και γενικά ψάχνομαι απο tutorials πιό πολύ.

 

Δηλαδή αντί να σας πει αυτό είναι το insertion sort γίνεται έτσι το χρησιμοποιούμε όταν ΧΥΖ και μετά να σας βάλει την άσκηση οπότε ένας νορμάλ προετοιμασμένος θα καταλάβαινε αμέσως τι να κάνει...

 

Ενώ το bubble που είναι α) τελείως άχρηστο και β) πιο περίπλοκο στην κατανόηση από το insertion το είπε.

 

Γεα μπεμπε αυτοί είναι καθηγητές πληροφορικής.

 

ΥΓ αν δεν το έχεις βρει ήδη, δες αυτό: https://www.toptal.com/developers/sorting-algorithms.

 

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

[solarpower]

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

με πρόλαβε ο Defacer

[zafgr]

Ευχαριστώ πολύ παιδιά....

[george991]

Καλησπέρα φίλε μου,

 

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

 

1. Τα Μ και Ν είναι διαφορετικοί αριθμοί! Μπορείς είτε να τους ορίσεις μέσα στο πρόγραμμά σου είτε να τους παίρνεις σαν είσοδο από το πληκτρολόγιό σου (δεν παίζει κανένα ρόλο). Αλλά στην υλοποίησή σου βλέπω μόνο το Ν και το size. Πρώτο λάθος ότι αρχικοποιείς τους πίνακες μεγέθους size και μετά ζητάς το Ν το οποίο μπορεί να είναι διαφορετικός αριθμός και να σου δημιουργήσει πρόβλημα. Ο ένας πίνακας θα είνα a[N] και ο άλλος b[M].

 

2. Μέσα στη λούπα μπορείς να αποθηκεύεις κάθε νέα τιμή σε μια temp μεταβλητή και μετά να την εισάγεις στον πίνακα (γιατί σύμφωνα με την εκφώνηση αυτό που κάνεις και την αποθηκεύεις στο a είναι λάθος αλλά όχι κάτι τρομερό). Επίσης αντί για while μπορείς να έχεις μια δεύτερη for για j από 0 εώς i-1 γιατί τόσες εγγραφές έχεις μέχρι τότε στον πινακά σου και η σύγκριση με στοιχεία μετά το i-1 δεν ξέρεις τι αποτέλεσμα θα βγάλει αφού ο πίνακας σου από εκεί και πέρα έχει σκουπίδια στη μνήμη του. Τώρα για την ταξινόμηση μπορείς να βρεις κάποια πολύ πιο αποδοτική υπολογιστικά από τη φυσαλίδα αλλά άσε αυτή αφού μόνο αυτή έχετε μάθει.

 

3. Επαναλαμβάνεις το βήμα 2 για τον b πίνακα με Μ στοιχεία.

 

4. Φτιάχνεις έναν καινούριο πίνακα c[M+N] που θα μπουν ταξινομημένα τα στοιχεία των 2 προηγούμενων πινάκων. Μέσα σε μια while φτιάχνεις μια συνθήκη του τύπου if a<b[j] -> c[k]=a else c[k]=b[j]. Τα i,j και k τα αρχικοποιείς έξω από την while σε 0. Μετά από κάθε βήμα αυξάνεις το k και όποιο από τα i, j χρησιμοποίησες κατά 1. Επίσης, μετά από κάθε βήμα ελέγχεις αν κάποιο από τα i, j έχει φτάσει στη μέγιστη τιμή του που είναι τα N και M αντίστοιχα. Αν συμβαίνει αυτό απλά γεμίζεις τις υπόλοιπες θέσεις του c με τα στοιχεία του πίνακα που έμεινε (αφού είναι ήδη ταξινομημένα). Η while τερματίζεται όταν το k φτάσει στο N+M ή με κάποια άλλη συνθήκη μέσα στη λούπα.