Τι είναι ο αλγόριθμος γρήγορης ταξινόμησης [Επεξήγηση με παραδείγματα]

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

Πώς λειτουργεί η γρήγορη ταξινόμηση:

1. Διαίρεση: Επιλέξτε ένα στοιχείο περιστροφής από τον πίνακα (συχνά το τελευταίο στοιχείο).

2. Διαμέριση: Αναδιάταξη του πίνακα έτσι ώστε όλα τα στοιχεία που είναι μικρότερα από τον άξονα περιστροφής να βρίσκονται στα αριστερά του άξονα περιστροφής και όλα τα στοιχεία μεγαλύτερα από τον άξονα είναι προς τα δεξιά. Το στοιχείο περιστροφής βρίσκεται στην τελική του θέση ταξινόμησης.

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

Παράδειγμα 1:

Θεωρήστε τον πίνακα [5, 3, 8, 2, 1, 4].

ένα. Διαίρεση:Επιλέξτε το τελευταίο στοιχείο, 1 ως άξονα.

σι. Χώρισμα:

- Αναδιάταξη του πίνακα:[3, 2, 1, 5, 4, 8] (το 1 βρίσκεται στη θέση ταξινόμησης).

ντο. Επανάληψη:

- Αριστερή υποσυστοιχία:[3, 2, 1] (ήδη ταξινομημένο)

- Δεξιά υποσυστοιχία:[5, 4, 8] (εφαρμόστε αναδρομικά Γρήγορη ταξινόμηση)

Μετά την εφαρμογή Γρήγορης Ταξινόμησης και στους δύο υποπίνακες, ο τελικός ταξινομημένος πίνακας είναι:[1, 2, 3, 4, 5, 8].

Παράδειγμα 2:

Ταξινόμηση μεγαλύτερου πίνακα

Θεωρήστε έναν πίνακα [7, 2, 9, 5, 3, 4, 1, 8, 6].

ένα. Διαίρεση:Επιλέξτε το τελευταίο στοιχείο, 6, ως άξονα.

σι. Χώρισμα:

- Αναδιάταξη του πίνακα:[2, 5, 3, 4, 1, 7, 9, 6] (το 6 βρίσκεται στη θέση ταξινόμησης).

ντο. Επανάληψη:

- Αριστερή υποσυστοιχία:[2, 5, 3, 4, 1] (εφαρμόστε επαναλαμβανόμενα Γρήγορη ταξινόμηση)

- Δεξιά υποσυστοιχία:[7, 9] (ήδη ταξινομημένο)

Μετά την ολοκλήρωση των αναδρομικών κλήσεων, ο ταξινομημένος πίνακας είναι:[1, 2, 3, 4, 5, 6, 7, 8, 9].

Χρονική πολυπλοκότητα:

- Καλύτερη περίπτωση:O(n log n)

- Μέση περίπτωση:O(n log n)

- Χειρότερη περίπτωση:O(n^2) (συμβαίνει όταν ο πίνακας είναι ήδη ταξινομημένος ή ανάστροφη ταξινόμηση)

Συνολικά, ο αλγόριθμος Γρήγορης Ταξινόμησης προσφέρει μια αποτελεσματική λύση ταξινόμησης με καλή πολυπλοκότητα χρόνου μέσης περίπτωσης O(n log n). Η απλότητα και η ευελιξία του τον έχουν καταστήσει δημοφιλή αλγόριθμο για την ταξινόμηση εργασιών σε διάφορες γλώσσες προγραμματισμού.