Programa C++ para QuickSort – Part 2

Similar al algoritmo Merge Sort , el algoritmo Quick Sort es un algoritmo Divide and Conquer. Inicialmente selecciona un elemento como elemento pivote y divide la array dada alrededor del pivote seleccionado. Hay muchas versiones diferentes de quickSort que seleccionan el pivote de diferentes maneras. 

1. Elija siempre el primer elemento como pivote (implementado a continuación).
2. Elija siempre el último elemento como pivote.
3. Elija un elemento aleatorio como pivote.
4. Elija la mediana como un pivote.

El proceso clave en QuickSort es el proceso de partición(). El objetivo de la función de partición() es recibir una array y un elemento x de la array como un pivote, colocar x en su posición correcta en una array ordenada y luego colocar todos los elementos más pequeños (más pequeños que x) antes de x, y colocar todos los elementos mayores (mayores que x) después de x. Todo esto debe hacerse en tiempo lineal, es decir, Big O(n).
Pseudocódigo para la función QuickSort recursiva: 

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

// C++ Implementation of the Quick Sort Algorithm.
#include <iostream>
using namespace std;
 
int partition(int arr[], int start, int end)
{
 
    int pivot = arr[start];
 
    int count = 0;
    for (int i = start + 1; i <= end; i++) {
        if (arr[i] <= pivot)
            count++;
    }
 
    // Giving pivot element its correct position
    int pivotIndex = start + count;
    swap(arr[pivotIndex], arr[start]);
 
    // Sorting left and right parts of the pivot element
    int i = start, j = end;
 
    while (i < pivotIndex && j > pivotIndex) {
 
        while (arr[i] <= pivot) {
            i++;
        }
 
        while (arr[j] > pivot) {
            j--;
        }
 
        if (i < pivotIndex && j > pivotIndex) {
            swap(arr[i++], arr[j--]);
        }
    }
 
    return pivotIndex;
}
 
void quickSort(int arr[], int start, int end)
{
 
    // base case
    if (start >= end)
        return;
 
    // partitioning the array
    int p = partition(arr, start, end);
 
    // Sorting the left part
    quickSort(arr, start, p - 1);
 
    // Sorting the right part
    quickSort(arr, p + 1, end);
}
 
int main()
{
 
    int arr[] = { 9, 3, 4, 2, 1, 8 };
    int n = 6;
 
    quickSort(arr, 0, n - 1);
 
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
 
    return 0;
}

1 2 3 4 8 9 

Consulte el artículo completo sobre QuickSort para obtener más detalles.