[2021-22]: Εργασία 2

[pefraimi]

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

[pefraimi]

Η ερώτηση 6 θέλει να γράψουμε τον κώδικα του partition για το quick sort; μετά από μερικές προσπάθειες, ήταν προφανές ότι το pivot δεν είναι καλά ορισμένο (κάνοντάς το print βγάζει ''0", και κάνοντας print το array δείχνει πως δεν υπάρχει κανένα στοιχείο ισο με 0). Ο κώδικας οδηγεί σε σωστό αποτέλεσμα γράφοντας την εντολή ```pivot = array.get(high)``` αλλα προφανώς δεν είναι αποδεκτή λύση.

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

Στην ερώτηση 7 πρέπει να γράψουμε έναν sorting algorithm με complexity O(nlogn), ο οποίος θα βασίζεται μόνο σε comparisons και swaps. Ένας τέτοιος αλγόριθμος είναι ο Heap Sort (Quick Sort και Merge Sort χρειάζονται reads), ωστόσο παρβιάζεται ο αριθμός των comparisons, παρά το γεγονός ότι έχει complexity O(nlogn).

Όπως έχουμε πει στο μάθημα, η Quicksort είναι κατά μέσο όρο πιο γρήγορη, και ας έχουν όλοι οι παραπάνω αλγόριθμοι ασυμπτωτική πολυπλοκότητα O(n logn). Επομένως, εάν με την Heap Sort ξεπερνάει το όριο που θέτει η άσκηση, δοκίμασε την Quick Sort. Η Ερώτηση 6 αυτό το νόημα είχε, να σας προετοιμάσει για την Quick Sort.