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}