Sorting algorithm - Quick Sort

[vudduu]

Este algoritmo es muy comun, por que es facil de implementar y ademas este puede ser utilizado con grandes cantidades de datos. Les dejo la implementación en C++.

vector<int> quickSort(vector<int> data) {
    int n = data.size(), i;
    if (n <= 1) return data;
    int middle = data[n/2];
    vector<int> left;
    vector<int> right;
    for (i = 0; i < n; i++) {
        if (i != n/2) {
            if (data[i] <= middle)
                left.PB(data[i]);
            else
                right.PB(data[i]);
        }
    }
    i = 0;
    left = quickSort(left);
    for (int j=0; j < left.size() ;j++)
        data[i++] = left[j];
    data[i++] = middle;
    right = quickSort(right);
    for (int j=0; j < right.size() ;j++)
        data[i++] = right[j];
    return data;
}

A continuación un ejemplo de como es la ejecución de este algoritmo.

{18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11} // input, Array desordenado
{6, 9, 1, 4, 12, 5, 6, 7, 11} {15} {18} // middle = {15}
{6, 9, 1, 4, 5, 6, 7, 11} {12} {15} {18} // middle = {12}
{1, 4} {5} {6, 9, 6, 7, 11} {12} {15} {18} // middle = {5}
{1} {4} {5} {6} {6} {9, 7, 11} {12} {15} {18} // middle = {1} y {6}
{1} {4} {5} {6} {6} {7} {9, 11} {12} {15} {18} // middle = {7}
{1} {4} {5} {6} {6} {7} {9} {11} {12} {15} {18} // middle = {9}