Entendendo Insertion Sort

Programas são compostos por muitos blocos dentro de si, e estes blocos por sua vez são compostos por outros blocos. Recursivamente falando, poderíamos chegar às unidades básicas de informação que um processador trabalha com: 0's e 1's. Expliquei neste post o que seriam os números binários. Afinal, o processador trabalha sempre com informação binária, porém com uma representação de alto nível. Literalmente a informação é 0 e 1, porém contém significado diferente quanto juntamos em alguns conjuntos e de acordo com as operações.

Enfim, cada bloco atômico dessa informação é denominada bit, e o conjunto de 8 bits é denominado byte. Afinal, por quê 8? Porque inicialmente 8 = 2³!
Toda operação que envolve conjuntos ou transformação numérica no computador sempre será expressa na base 2. É convencionadamente mais fácil de calcular e verificar, visto que o computador trabalha com informação na forma binária. Por isso, 1 byte = 2³ bits, um kibibyte é 2^10 bytes, um kilobyte por sua vez é 10³ bytes (entenda a diferenciação entre um kibibyte e um kilobyte aqui).

Pois bem, o processador trabalha com um monte de informações, muitas vezes dispostas de forma sequencial. Quando juntamos uma informação e colocamos sequencialmente a mesma quanto ao endereço de memória damos a isso o nome de Array. É uma estrutura presente em grande parte das linguagens de programação e podemos acessar os índices do array de acordo com sua posição no mesmo.

int *array = new int[5]{2, 4, 5, 6, 7};
std::cout << array[2] << std::endl;

// 5

As representações de código nesse post, a menos que explicitamente indicadas, serão expressas em C++

Relembre-se que, o array começa no índice 0!
Algumas linguagens de programação oferecem a possibilidade de construir um array associativo, isto é, ao invés do índice ser numerado, o índice é nomeado, por exemplo, em PHP:

$exampleArray = array(
  'joão' => 'maria',
  'joaquim' => 'jose'
);

echo $exampleArray['joao'];

// maria

Muitas vezes podemos nos deparar com a situação dos dados estarem dispostos de forma desorganizada dentro desse array, e quando se trata de um array muito grande, então aí que temos um problema muito grande se formos usar uma busca linear nele (O(n)). Imagine que o array tenha 500 itens. Então, no pior caso, serão 500 comparações que serão necessárias para poder encontrar o item. Podemos usar uma busca binária, onde sua eficiência no pior caso é O(log(n)), então, no pior caso, as comparações serão 9!

Porém tem um outro problema: para aplicar uma busca binária em seu array, o mesmo precisa estar ordenado de maneira crescente. Se ele estiver desorganizado, ou organizado de forma diferente da crescente, então há a possibilidade da busca nunca encontrar o seu resultado.

Nesse caso temos que recorrer a um algoritmo de ordenação, ou Sorting Algorithm. O que vou abordar neste post é o Insertion Sort, um dos mais básicos e com uma das menores eficiências (O(n²) no pior caso), mas é o básico para entender outros algoritmos.

Só para ilustrar um pouco o problema de eficiência desse algoritmo, vamos supor que temos um array de 10 posições, que está em ordem decrescente. Para ordená-lo, será necessário 100 comparações. O problema só piora quanto mais itens e mais desorganizado estiver o array.

Este algoritmo ordena através de inserções, isto é, para cada novo elemento que chega ao final do array, é feito comparações com o elemento mais próximo ou antes dele e insere este elemento no seu lugar correto, de acordo com o valor do elemento que está antes dele. Confuso? Talvez...

Vamos já implementá-lo em passos.

Primeiro de tudo, vamos considerar um array com um único elemento. Nesse caso, automaticamente o array já está ordenado, a partir daí, podemos expandir nossos horizontes, de forma incremental. Para um caso que temos um array com 5 elementos, por exemplo, considerando hipoteticamente se excluíssemos os 4 últimos elementos, sobraria somente o primeiro, e ele já estaria organizado. O próximo passo seria inserir o próximo elemento, organizá-lo, depois o próximo e assim por diante. Formamos então um loop:

// Para arrays convencionais, quando passa-se os mesmos a funções
// Eles decaem para ponteiros. Não temos uma função específica 
// para saber o seu tamanho e não podemos usar o sizeof, então 
// o tamanho tem que ser passado como argumento para a função

int *insertionSort(int *arr, int arrLength){
  for(int i = 1; i < arrLength; i++){

  // ...

  }
}

Então o que estamos fazendo? Estamos pulando o primeiro elemento e iterando sobre os próximos, visto que o primeiro podemos considerar ordenado. Os próximos sim iremos inserir no array que está com 1 elemento e ele irá crescendo. O próximo passo é guardar o elemento que iremos comparar com os que já estão ordenados em um endereço de memória separado, já que teremos que mover elementos pelo array.

for(int i = 1; i < arrLength; i++){
  int cur = arr[i];
  int index2Compare = i - 1;
}

A variável index2Compare vai pegar o índice do elemento exatamente anterior ao do elemento que estamos comparando para começar a realizar as comparações.

Depois disso, vamos ter um novo loop que irá realizar as comparações com cada elemento anterior para realizar a inserção.

for(int i = 1; i < arrLength; i++){
  // ...
  int index2Compare = i - 1;

  while(index2Compare >= 0 && arr[index2Compare] > cur){
    //...
  }
}

Ok, nesse caso, estamos dizendo que o loop irá se estender sob duas condições:

• Enquanto o índice a ser comparado for maior ou igual a 0, para não chegarmos no índice -1 do array;
• Enquanto o elemento anterior ao atual for maior que o elemento atual;

Se as duas condições forem cumpridas, então iremos trocar o elemento anterior e avançar com ele um index para frente e vamos passar a comparar o próximo elemento anterior a ele:

for(int i = 1; i < arrLength; i++){
  // ...
  while(index2Compare >= 0 && arr[index2Compare] > cur){
    arr[index2Compare + 1] = arr[index2Compare];
    index2Compare--;
  }
}

Se por um acaso alguma das condições acima não forem atendidas, o que acontece? Então chegamos ao ponto ideal para podermos inserir nosso elemento, porém lembre-se que a cada sub-iteração dessa, estamos diminuindo -1 do index2Compare, então a posição para inserir nosso elemento será no index2Compare + 1:

for(int i = 1; i < arrLength; i++){
  // ...
  while(index2Compare >= 0 && arr[index2Compare] > cur){
    // ...
  }
  arr[index2Compare + 1] = cur;
}

Lembre-se que começamos a declarar que a função retorna um ponteiro para int, então, vamos retornar esse mesmo array:

int *insertionSort(int *arr, int arrLength){
  //...
  return arr;
}

O código completo dessa implementação abaixo:

int *insertionSort(int *arr, int arrLength){

  for(int i = 1; i < arrLength; i++){

    int cur = arr[i];
    int index2Compare = i - 1;

    while(index2Compare >= 0 && arr[index2Compare] > cur){
        arr[index2Compare + 1] = arr[index2Compare];
        index2Compare--;
    }

    arr[index2Compare + 1] = cur;
  }

  return arr;
}

E abaixo um programinha para teste dessa implementação:

#include <iostream>

using namespace std;

int *insertionSort(int *arr, int arrLength){

  for(int i = 1; i < arrLength; i++){

    int cur = arr[i];
    int index2Compare = i - 1;

    while(index2Compare >= 0 && arr[index2Compare] > cur){
        arr[index2Compare + 1] = arr[index2Compare];
        index2Compare--;
    }

    arr[index2Compare + 1] = cur;
  }

  return arr;
}

int main()
{
    int arrLength = 9;

    // dependendo do compilador, o mesmo pode exigir que você
    // especifique qual o tamanho do array, mesmo declarando
    // os elementos ahead of time. O gcc aceita a sintaxe 
    // abaixo. O onlineGDB exige que você especifique o tamanho 
    // do array
    int *arrExample = new int[]{6, 3, 9, 1, 0, 9, 2, 9, 5};


    int *sorted = insertionSort(arrExample, arrLength);

    for(int i = 0; i < arrLength; i++){
        cout << sorted[i] << endl;
    }

    return 0;
}

0
1
2
3
5
6
9
9
9


...Program finished with exit code 0
Press ENTER to exit console.