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.
Top comments (0)