Ταξινόμηση σε C

[mike2012]

Να υπολογίσετε τον ελάχιστο αριθμό από συγκρίσεις που μπορεί να γίνουν για την ταξι-

νόμηση με την qsort ενός πίνακα με N στοιχεία, ως συνάρτηση του N

[migf1]

Μήπως την έχεις δει καθηγητής που εκφωνεί ασκήσεις στην τάξη του;

 

http://www.insomnia.gr/topic/428148-ta3inomisi-se-c/

[orotoi]

(απο wikipedia)

 

Worst case performance: O(n2)

Best case performance: O(n log n)

Average case performance: O(n log n)

Worst case space complexity: O(n)

 

 

Κατα τ' αλλα.. οτι λέει και ο μιγκ

[Dexterpap]

Φιλε συμφωνω με τα παιδια αλλα τελοσπαντον,

στο εφτιαξα το προγραμμα.Δες το στις παρακατω

εικονες.Αμα θες το εκτελεσιμο αρχειο απο το

visual sudio πες μου.

[gallaki]

Φιλε συμφωνω με τα παιδια αλλα τελοσπαντον,

στο εφτιαξα το προγραμμα.Δες το στις παρακατω

εικονες.Αμα θες το εκτελεσιμο αρχειο απο το

visual sudio πες μου.

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

 

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

[ntellos]

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

Συμφωνώ απολύτως, αλλά

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

Διακρίνω ένα μικρό κόμπλεξ;

Προφανώς και δεν θα του δώσει η Άσκηση τον βαθμό (έστω και το 5) στο μάθημα, αλλά η εμπειρία που θα αποκτήσει κάνοντας την! Οπότε fucking yeah καλά έκανες που κωλοχτυπιώσουν και τις έκανες και δεν πρόκειται ποτέ να έχεις τον ίδιο βαθμό. Όπως λέει και ο λαός "Στο τέλος ξυρίζουν τον γαμπρό"

 

ΥΓ: no offence!

[Timonkaipumpa]

Συμφωνώ απολύτως, αλλά

 

Διακρίνω ένα μικρό κόμπλεξ;

Προφανώς και δεν θα του δώσει η Άσκηση τον βαθμό (έστω και το 5) στο μάθημα, αλλά η εμπειρία που θα αποκτήσει κάνοντας την! Οπότε fucking yeah καλά έκανες που κωλοχτυπιώσουν και τις έκανες και δεν πρόκειται ποτέ να έχεις τον ίδιο βαθμό. Όπως λέει και ο λαός "Στο τέλος ξυρίζουν τον γαμπρό"

 

ΥΓ: no offence!

 

 

Κανένα κόμπλεξ.

 

 

ΝΑ ΜΗΝ πάρουν πτυχίο τέτοια άτομα. Να μην γίνουν ποτέ συνάδελφοι. Φτάνει με τους άσχετους που απλά θέλουν ένα χαρτί. Εάν θέλουν ένα χαρτί, να πάνε να πάρουν χαρτομάντιλα.

[gallaki]

Συμφωνώ απολύτως, αλλά

 

Διακρίνω ένα μικρό κόμπλεξ;

Προφανώς και δεν θα του δώσει η Άσκηση τον βαθμό (έστω και το 5) στο μάθημα, αλλά η εμπειρία που θα αποκτήσει κάνοντας την! Οπότε fucking yeah καλά έκανες που κωλοχτυπιώσουν και τις έκανες και δεν πρόκειται ποτέ να έχεις τον ίδιο βαθμό. Όπως λέει και ο λαός "Στο τέλος ξυρίζουν τον γαμπρό"

 

ΥΓ: no offence!

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

 

Και ποια εμπειρία? Νομίζεις οτι θα κάτσει να δεί την άσκηση? Το πολύ πολύ να την κάνει copy - paste και να την τρέξει μια φορά για να βεβαιωθεί οτι δουλεύει και μετά στον καθηγητή για να πάρει τον βαθμό.

 

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

 

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

 

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

Προσωπική άποψη πάντα.

[παπι]

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

 

 

Το καλεσμα της qsort ειναι "ακηση" ;;;;;

[gallaki]

Το καλεσμα της qsort ειναι "ακηση" ;;;;;

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

 

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

[Dexterpap]

Εχεις δικιο gallaki σε αυτα που λες αλλα να σου πω

σιγα το προγραμμα τωρα που ζητησε, ετσι και αλλιως ναι μεν

δεν το βοηθαω ουσιαστικα αλλα ειναι και επιλογη του το αν θελει

να μαθει η οχι δεν θα τον κρινω εγω. Και τελοσπαντον δεν μου ηταν

κοπος και το εφτιαξα.

[nik324]

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

 

 

Λοιπον,ο ελάχιστος αριθμός συγκρίσεων είναι διαφορετικός από τον μέσω αριθμό συγκρίσεων, σωστά;

Αν ο πίνακας είναι ταξινομιμένος από πρίν η ένα μονάχα στοιχείο βρίσκεται σε λάθος θέση τότε οι έλάχιστες συγκρίσεις δεν θα είναι 0 και 1 αντίστοιχα;;

 

Που είναι το λάθος στην σκέψη μου;

Δεν ξέρω ούτε εγώ και μια που ανοίχτηκε αυτό τι θέμα καλό θα ήταν να μάθω!! :P

[Timonkaipumpa]

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

 

 

Λοιπον,ο ελάχιστος αριθμός συγκρίσεων είναι διαφορετικός από τον μέσω αριθμό συγκρίσεων, σωστά;

Αν ο πίνακας είναι ταξινομιμένος από πρίν η ένα μονάχα στοιχείο βρίσκεται σε λάθος θέση τότε οι έλάχιστες συγκρίσεις δεν θα είναι 0 και 1 αντίστοιχα;;

 

Που είναι το λάθος στην σκέψη μου;

Δεν ξέρω ούτε εγώ και μια που ανοίχτηκε αυτό τι θέμα καλό θα ήταν να μάθω!! :P

 

 

Το να έχεις 0 αριθμό συγκρίσεων είναι ένα extreme που, φυσικά, είναι το καλύτερο που θα μπορούσες να έχεις.

 

Όμως, που θα παρουσιαστεί το πρόβλημα; Στην καλύτερη ή στην χειρότερη περίπτωση;

 

 

Για αυτό αφενός το big O notation δεν θα πρέπει να είναι το μόνο μετρικό για την πολυπλοκότητα (υπάρχει και το Θ π.χ.) και αφετέρου, επειδή στην χειρότερη θα έχεις το χειρότερο πρόβλημα, το να βελτιώσεις την χειρότερη περίπτωση είναι ένα σημαντικό κέρδος.

[nik324]

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

 

Οπως είπες και εσύ το να έχουμε 0 συγκρίσεις είμαι μια extreme κατάσταση που όμως σε θεωρητικό επίπεδο μπορεί να υπάρξει...Επομένος γιατί οι ελάχιστες συγκρίσεις που μπορεί να γίνουν δεν είναι 0;;

[Timonkaipumpa]

Γιατί πρέπει να τσεκάρεις εάν είναι ΟΚ ο πίνακάς σου. Πού θα ξέρεις εάν είναι ΟΚ; Πρέπει να τον ελέγξεις όλο.

 

(Τώρα κατάλαβα τι ρωτάς, και το προηγούμενο μήνυμα μου ίσως σε μπερδέψει πιο πολύ).