Sorting algorithm - Quick Sort


  • administrators

    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}