Αλγόριθμος QuickSort

Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί η γρήγορη ταξινόμηση. Επίσης, θα βρείτε λειτουργικά παραδείγματα γρήγορης ταξινόμησης σε C, C ++ Python και Java.

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

Πώς λειτουργεί το QuickSort;

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

Το Quicksort χρησιμοποιεί αναδρομή για ταξινόμηση των υπο-τμημάτων.

Με βάση την προσέγγιση "Διαίρεση και κατάκτηση", ο αλγόριθμος γρήγορης ταξινόμησης μπορεί να εξηγηθεί ως:

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

Μπορείτε να κατανοήσετε τη λειτουργία της γρήγορης ταξινόμησης με τη βοήθεια των παρακάτω εικόνων.

Ταξινόμηση των στοιχείων στα αριστερά του άξονα χρησιμοποιώντας αναδρομή Ταξινόμηση των στοιχείων στα δεξιά του άξονα χρησιμοποιώντας αναδρομή

Αλγόριθμος γρήγορης ταξινόμησης

 quickSort (πίνακας, leftmostIndex, rightmostIndex) εάν (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (πίνακας, pivotIndex + 1, rightmostIndex, rightInInexex ) ορίστε rightmostIndex ως pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 to rightmostIndex if element (i) <pivotElement swap element (i) and element (storeIndex) storeIndex ++ swap pivotElement and element (storeIndex + 1) returnInIndex + store 1

Παραδείγματα Python, Java και C / C ++

Python Java C C +

 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)

 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )

 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Πολυπλοκότητα Quicksort

Χρόνος πολυπλοκότητας

• Χειρότερη περίπλοκη περίπτωση (Big-O) : Εμφανίζεται όταν το στοιχείο περιστροφής που επιλέγεται είναι είτε το μεγαλύτερο είτε το μικρότερο στοιχείο. Αυτή η συνθήκη οδηγεί στην περίπτωση στην οποία το περιστρεφόμενο στοιχείο βρίσκεται στο ακραίο άκρο του ταξινομημένου πίνακα. Ένας δευτερεύων πίνακας είναι πάντα κενός και ένας άλλος δευτερεύων πίνακας περιέχει στοιχεία. Έτσι, η γρήγορη ταξινόμηση καλείται μόνο σε αυτόν τον δευτερεύοντα πίνακα. Ωστόσο, ο αλγόριθμος γρήγορης ταξινόμησης έχει καλύτερη απόδοση για διάσπαρτους άξονες.O(n2)
n - 1

• Βέλτιστη πολυπλοκότητα περιπτώσεων (Big-omega) : O(n*log n)
  Εμφανίζεται όταν το στοιχείο περιστροφής είναι πάντα το μεσαίο στοιχείο ή κοντά στο μεσαίο στοιχείο.
• Μέση περίπλοκη περίπτωση (Big-theta) : O(n*log n)
  Εμφανίζεται όταν δεν εμφανίζονται οι παραπάνω συνθήκες.

Διαστημική πολυπλοκότητα

Η πολυπλοκότητα του χώρου για γρήγορη ταξινόμηση είναι O(log n).

Εφαρμογές Quicksort

Το Quicksort εφαρμόζεται όταν

• η γλώσσα προγραμματισμού είναι καλή για επανάληψη
• έχει σημασία η πολυπλοκότητα του χρόνου
• έχει σημασία η πολυπλοκότητα του χώρου