Περιεχόμενο

• Συγκριτικό διάγραμμα
• Ορισμός ταξινόμησης φούσκας
• Ορισμός της ταξινόμησης επιλογής
• συμπέρασμα

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

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

1. Συγκριτικό διάγραμμα
2. Ορισμός
3. Βασικές διαφορές
4. συμπέρασμα

Συγκριτικό διάγραμμα

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

Ορισμός ταξινόμησης φούσκας

Τύπος φούσκα είναι ο απλούστερος επαναληπτικός αλγόριθμος που λειτουργεί με τη σύγκριση κάθε στοιχείου ή στοιχείου με το στοιχείο δίπλα σε αυτό και την εναλλαγή, αν χρειαστεί. Με απλά λόγια, συγκρίνει το πρώτο και το δεύτερο στοιχείο της λίστας και τις ανταλλάσσει, εκτός εάν δεν βρίσκονται σε συγκεκριμένη σειρά. Παρομοίως, το δεύτερο και το τρίτο στοιχείο συγκρίνονται και ανταλλάσσονται, και αυτή η σύγκριση και η ανταλλαγή συνεχίζονται στο τέλος της λίστας. Ο αριθμός των συγκρίσεων στην πρώτη επανάληψη είναι n-1 όπου n είναι τα αριθμητικά στοιχεία ενός πίνακα. Το μεγαλύτερο στοιχείο θα ήταν στην nη θέση μετά την πρώτη επανάληψη. Και μετά από κάθε επανάληψη, ο αριθμός των συγκρίσεων μειώνεται και στην τελευταία επανάληψη λαμβάνει χώρα μόνο μία σύγκριση.

Αυτός ο αλγόριθμος είναι ο πιο αργός αλγόριθμος ταξινόμησης. Η πολυπλοκότητα της καλύτερης περίπτωσης (όταν η λίστα είναι σωστή) του τύπου Bubble είναι της τάξης n (Επί)), και η πολυπλοκότητα της χειρότερης περίπτωσης είναι Επί²). Στην καλύτερη περίπτωση, είναι της τάξης n επειδή συγκρίνει μόνο τα στοιχεία και δεν τα ανταλλάσσει. Αυτή η τεχνική απαιτεί επιπλέον χώρο για την αποθήκευση της προσωρινής μεταβλητής.

Ορισμός της ταξινόμησης επιλογής

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

Κατά την ταξινόμηση των επιλογών, ο ταξινομημένος και μη διατεταγμένος πίνακας δεν έχει καμία διαφορά και καταναλώνει μια σειρά n² (Επί²)) τόσο στην καλύτερη όσο και στη χειρότερη περίπλοκη περίπτωση. Ο τύπος επιλογής είναι ταχύτερος από την επιλογή φυσαλίδων.

1. Στο είδος των φυσαλίδων, κάθε στοιχείο και το παρακείμενο του στοιχείο συγκρίνονται και αντικαθίστανται εάν απαιτείται. Από την άλλη πλευρά, η επιλογή επιλογής λειτουργεί επιλέγοντας το στοιχείο και αντικαθιστώντας το συγκεκριμένο στοιχείο με το τελευταίο στοιχείο. Το επιλεγμένο στοιχείο θα μπορούσε να είναι μεγαλύτερο ή μικρότερο ανάλογα με τη σειρά, δηλ. Ανύψωση ή φθίνουσα σειρά.
2. Η πολυπλοκότητα της χειρότερης περίπτωσης είναι η ίδια και στους δύο αλγορίθμους, δηλ. Το O (n²), αλλά η καλύτερη πολυπλοκότητα είναι διαφορετική. Η ταξινόμηση των φυσαλίδων παίρνει μια σειρά n, ενώ η επιλογή sort καταναλώνει μια σειρά n² χρόνος.
3. Το είδος φυσαλίδων είναι ένας σταθερός αλγόριθμος, αντίθετα, το είδος επιλογής είναι ασταθές.
4. Ο αλγόριθμος επιλογής επιλογής είναι γρήγορος και αποτελεσματικός σε σύγκριση με τον τύπο φυσαλίδων, ο οποίος είναι πολύ αργός και αναποτελεσματικός.

συμπέρασμα

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