Αλγόριθμος

Σύγκριση αλγορίθμων

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

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

Ταξινόμηση

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

1. Μαζέψτε όλες τις κάρτες.
2. Διαλέξτε μια κάρτα από το χέρι σας και κοιτάξτε το χρώμα της κάρτας.
3. Εάν υπάρχει ήδη μια στοίβα με κάρτες αυτού του χρώματος, βάλτε αυτή την κάρτα σε αυτή τη στοίβα.
4. Αν δεν υπάρχει στοίβα με κάρτες αυτού του χρώματος, φτιάξτε μια νέα στοίβα μόνο με αυτό το χρώμα.
5. Αν υπάρχει ακόμα μια κάρτα στο χέρι σας, επιστρέψτε στο δεύτερο βήμα.
6. Εάν δεν υπάρχει ακόμη κάρτα στο χέρι σας, τότε οι κάρτες ταξινομούνται. Τελειώσατε.

Ταξινόμηση με αριθμούς

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

Οι παίκτες ξεκινούν με μια στοίβα από κάρτες που δεν έχουν ταξινομηθεί.

Πρώτος αλγόριθμος

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

1. Εάν η στοίβα των καρτών είναι άδεια ή περιέχει μόνο μία κάρτα, η στοίβα είναι ταξινομημένη- τελειώσατε.
2. Πάρτε τη στοίβα των καρτών. Κοιτάξτε το πρώτο φύλλο (το κορυφαίο) της στοίβας.
3. Το φύλλο που βλέπετε είναι το φύλλο Α. Η θέση στην οποία βρίσκεται το φύλλο Α αυτή τη στιγμή είναι στη στοίβα P.
4. Εάν δεν υπάρχουν άλλα φύλλα στη στοίβα μετά το φύλλο Α, πηγαίνετε στο βήμα 8.
5. Η επόμενη κάρτα στη στοίβα είναι η κάρτα Β.
6. Αν η κάρτα Β έχει μικρότερο αριθμό από την κάρτα Α, ανταλλάξτε τις θέσεις των καρτών Α και Β. Θυμηθείτε ότι το κάνατε αυτό. Όταν ανταλλάσσετε τις κάρτες, μην αλλάζετε τη θέση P.
7. Αν υπάρχει άλλο φύλλο στη στοίβα μετά τη θέση P, κοιτάξτε το.Επιστρέψτε στο βήμα 3.
8. Εάν δεν αλλάξατε τη θέση κανενός φύλλου στην τελευταία εκτέλεση, τελειώσατε- η στοίβα των φύλλων είναι ταξινομημένη.
9. Διαφορετικά επιστρέψτε στο βήμα 2.

Παράδειγμα βήμα προς βήμα

Ας πάρουμε μια στοίβα από κάρτες με τους αριθμούς "5 1 4 2 8" και ας την ταξινομήσουμε από τον μικρότερο αριθμό στον μεγαλύτερο χρησιμοποιώντας αυτόν τον αλγόριθμο. Σε κάθε βήμα, ο αλγόριθμος συγκρίνει τα στοιχεία που είναι γραμμένα με έντονα γράμματα. Η κορυφή της στοίβας των καρτών βρίσκεται στην αριστερή πλευρά.

Πρώτο πέρασμα:
( 5 1 4 2 8 ) → {\displaystyle \to } ( 1 5 4 2 8 ) Εδώ, ο αλγόριθμος συγκρίνει τα δύο πρώτα στοιχεία και τα ανταλλάσσει.
( 1 5 4 2 8 ) → {\displaystyle \to } ( 1 4 5 2 8 )
( 1 4 5 2 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 ) Τα στοιχεία αυτά είναι ήδη στη σειρά, οπότε ο αλγόριθμος δεν τα ανταλλάσσει.
Δεύτερο πέρασμα:
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Τώρα, η στοίβα των καρτών είναι ήδη ταξινομημένη, αλλά ο αλγόριθμός μας δεν το γνωρίζει αυτό. Ο αλγόριθμος χρειάζεται ένα ολόκληρο πέρασμα χωρίς καμία ανταλλαγή για να γνωρίζει ότι είναι ταξινομημένη.
Τρίτο πέρασμα:
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Τέλος, ο πίνακας ταξινομείται και ο αλγόριθμος μπορεί να σταματήσει.

Ιστορία

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

Δεύτερος αλγόριθμος

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

Βασική ιδέα

1. Αν η στοίβα δεν έχει καθόλου κάρτες ή έχει μόνο μία κάρτα, τότε είναι ταξινομημένη και τελειώσατε.
2. Χωρίστε τη στοίβα των καρτών σε δύο μισά, περίπου ίδιου μεγέθους. Αν υπάρχει περιττός αριθμός καρτών, η μία από τις δύο στοίβες θα έχει μία κάρτα περισσότερη από την άλλη.
3. Ταξινομήστε καθεμία από τις δύο στοίβες χρησιμοποιώντας τον αλγόριθμο (Για κάθε στοίβα, ξεκινήστε από το στοιχείο 1 αυτής της λίστας).
4. Συγχωνεύστε τις δύο ταξινομημένες στοίβες, όπως περιγράφεται παρακάτω.
5. Το αποτέλεσμα είναι μια ταξινομημένη στοίβα από κάρτες. Τελειώσατε.

Συγχώνευση δύο στοίβες μαζί

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

1. Αν είτε η στοίβα Α είτε η στοίβα Β είναι άδεια, βάλτε όλες τις κάρτες της στοίβας που δεν είναι άδεια στην κορυφή της στοίβας Γ.Τελειώσατε, η στοίβα Γ είναι το αποτέλεσμα της συγχώνευσης. (Σημείωση: πάρτε ολόκληρη τη στοίβα και βάλτε την πάνω στη στοίβα Γ- αν το κάνετε κάρτα προς κάρτα, θα αλλάξει η σειρά και δεν θα λειτουργήσει όπως θα έπρεπε).
2. Κοιτάξτε τις πάνω κάρτες της στοίβας Α και της στοίβας Β. Βάλτε αυτή με τον μικρότερο αριθμό πάνω στη στοίβα Γ. Αν η στοίβα Γ δεν είχε καθόλου κάρτες, τώρα θα έχει μία κάρτα.
3. Εάν είτε η στοίβα Α είτε η στοίβα Β έχει κάρτες, επιστρέψτε στο βήμα 1 για να τις ταξινομήσετε.

Ιστορία

Ο John von Neumann ανέπτυξε αυτόν τον αλγόριθμο το 1945. Δεν τον ονόμασε Ταξινόμηση με αριθμούς, τον ονόμασε Mergesort. Είναι ένας πολύ καλός αλγόριθμος ταξινόμησης, σε σύγκριση με άλλους.

Τρίτος αλγόριθμος

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

Αντί να συγκρίνετε δύο κάρτες που βρίσκονται η μία δίπλα στην άλλη, στην αρχή διαλέγετε μια "ειδική" κάρτα. Όλες οι άλλες κάρτες συγκρίνονται στη συνέχεια με αυτή την κάρτα.

1. Ξεκινάμε με μια στοίβα Α. Θα υπάρχουν άλλες δύο στοίβες Β και Γ, οι οποίες θα δημιουργηθούν αργότερα.
2. Εάν η στοίβα Α δεν έχει καθόλου κάρτες ή έχει μόνο μία κάρτα, η ταξινόμηση έχει ολοκληρωθεί.
3. Μια κάρτα επιλέγεται από τη στοίβα Α, αν είναι δυνατόν τυχαία. Αυτό ονομάζεται pivot.
4. Όλα τα υπόλοιπα φύλλα της στοίβας Α συγκρίνονται με αυτό το σημείο περιστροφής. Οι κάρτες με μικρότερο αριθμό πηγαίνουν στη στοίβα Β, εκείνες με ίσο ή μεγαλύτερο αριθμό πηγαίνουν στη στοίβα Γ.
5. Εάν υπάρχουν κάρτες στις στοίβες Β ή Γ, οι στοίβες αυτές πρέπει να ταξινομηθούν με τον ίδιο αλγόριθμο (Ξεκινήστε από τη θέση 1 αυτής της λίστας και για τις δύο στοίβες Β και Γ με τη σειρά).
6. Έγινε. Η ταξινομημένη στοίβα καρτών έχει πρώτα την ταξινομημένη στοίβα Β, μετά τον άξονα και μετά την ταξινομημένη στοίβα Γ.

Ιστορία

Ο αλγόριθμος αυτός αναπτύχθηκε από τον C. A. R. Hoare το 1960. Είναι ένας από τους πιο διαδεδομένους αλγορίθμους ταξινόμησης σήμερα. Ονομάζεται Quicksort.

Animation που δείχνει πώς λειτουργεί η ταξινόμηση με φυσαλίδες


Ταξινόμηση 7 αριθμών χρησιμοποιώντας τον δεύτερο αλγόριθμο ταξινόμησης με αριθμούς (Mergesort)


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

Συνδυάζοντας αλγορίθμους

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

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

Σχετικές σελίδες

• Ο ευκλείδειος αλγόριθμος βρέθηκε πριν από 2000 χρόνια. Είναι σε θέση να βρει τον μεγαλύτερο κοινό διαιρέτη δύο αριθμών.