Sorting algorithm - Insertion Sort


  • administrators

    Este es mi implementación del algoritmo de inserción.

    vector<int> insertionSort(vector<int>data){
        int n = data.size(), j, tmp;
        for (int i = 0; i < n; i++) {
            j = i;
            while (j > 0 && data[i] < data[j - 1])
                j--;
            tmp = data[i];
            for (int k = i; k > j; k--)
                data[k] = data[k - 1];
            data[j] = tmp;
        }
        return data;
    }
    

    Como pueden ver este algoritmo no es muy diferente del Bubble Sort y es muy facil de implementar a continuación esta un ejemplo de la ejecución de este algoritmo:

    {18,  6,  9,  1,  4, 15, 12,  5,  6,  7, 11}
    { 6, 18,  9,  1,  4, 15, 12,  5,  6,  7, 11}
    { 6,  9, 18,  1,  4, 15, 12,  5,  6,  7, 11}
    { 1,  6,  9, 18,  4, 15, 12,  5,  6,  7, 11}
    { 1,  4,  6,  9, 18, 15, 12,  5,  6,  7, 11}
    { 1,  4,  6,  9, 15, 18, 12,  5,  6,  7, 11}
    { 1,  4,  6,  9, 12, 15, 18,  5,  6,  7, 11}
    { 1,  4,  5,  6,  9, 12, 15, 18,  6,  7, 11}
    { 1,  4,  5,  6,  6,  9, 12, 15, 18,  7, 11}
    { 1,  4,  5,  6,  6,  7,  9, 12, 15, 18, 11}
    { 1,  4,  5,  6,  6,  7,  9, 11, 12, 15, 18}