Μάθημα : Introduction to Algorithms and Programming

Introduction to Algorithms and Programming

DEMO-A1894 - Γιώργος Μεράκος, Παναγιώτης Θεοδωρόπουλος

Άσκηση 1: Αναδρομή

Περιγραφή

Απαντήστε στις παρακάτω ερωτήσεις

Ερώτηση 1 / 5 (Αντιστοίχιση — 5 βαθμοί) 

Ερώτηση 1.

Αντιστοιχείστε τους αλγόριθμους ανάλογα με την περιγραφή τους.

Στήλη Α Κάντε την αντιστοιχία Στήλη B
1. Ο αλγόριθμος προσπελάσει επανειλημμένα τη λίστα, συγκρίνει παρακείμενα στοιχεία και τα ανταλλάσσει αν είναι σε λάθος σειρά. Το πέρασμα μέσω της λίστας επαναλαμβάνεται έως ότου ταξινομηθεί η λίστα.
A. Selection Sort
2. Ο αλγόριθμος χωρίζει τη μη ταξινομημένη λίστα σε n δευτερεύουσες λίστες,όπου κάθε μία περιέχει ένα στοιχείο (μια λίστα ενός στοιχείου θεωρείται ταξινομημένη). Συγχωνεύει επανειλημμένα τις λίστες για να δημιουργήσει νέες ταξινομημένες λίστες έως ότου απομένει μόνο μία δευτερεύουσα λίστα. Αυτή θα είναι η ταξινομημένη λίστα.
B. BubbleSort
3. Λειτουργεί επιλέγοντας ένα στοιχείο άξονα από τη συστοιχία και χωρίζοντας τα άλλα στοιχεία σε δύο δευτερεύουσες συστοιχίες, ανάλογα με το αν είναι μικρότερα ή μεγαλύτερα από τον άξονα. Στη συνέχεια, οι υπο-σειρές ταξινομούνται με τον ίδιο τρόπο.
C. QuickSort
4. Ο αλγόριθμος διαιρεί τη λίστα εισόδου σε δύο μέρη: μια ταξινομημένη δευτερεύουσα λίστα αντικειμένων που είναι χτισμένη από αριστερά προς τα δεξιά στο μπροστινό μέρος (αριστερά) της λίστας και μια δευτερεύουσα λίστα των υπόλοιπων μη ταξινομημένων στοιχείων που καταλαμβάνουν την υπόλοιπη λίστα. Αρχικά, η ταξινομημένη δευτερεύουσα λίστα είναι κενή και η μη ταξινομημένη δευτερεύουσα λίστα είναι ολόκληρη η λίστα εισαγωγής. Ο αλγόριθμος προχωράει εντοπίζοντας το μικρότερο στοιχείο στο μη ταξινομημένο δευτερεύον κατάλογο, ανταλλάσσοντας με το αριστερότερο μη ταξινομημένο στοιχείο (βάζοντάς το σε ταξινομημένη σειρά) και μετακινώντας τα όρια της υποκατηγορίας ένα στοιχείο προς τα δεξιά .
D. MergeSort