Este é repositório de estudos sobre estrutura de dados utilizando a linguagem C#.
- Introdução e Referências
- Big-O
- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort
- Merge Sort
- Arrays, Listas e Vetores
Para estudar estrutura de dados, sugiro o seguinte roteiro de estudos:
Fundamentos de programação: Antes de começar a estudar estrutura de dados, é importante ter uma sólida compreensão dos conceitos fundamentais de programação,
como variáveis, funções, loops, condicionais, etc. Se você não tem experiência com programação, comece com cursos básicos de programação em uma linguagem popular,
como Python, Java ou C++. Há muitos cursos online gratuitos e pagos disponíveis.
A notação O (Big O) é uma notação matemática utilizada para medir a eficiência e desempenho do algoritmo de forma simples e prática.
Ela é usada para descrever o limite superior do número de operações que um algoritmo realiza em função do tamanho de entrada. Por exemplo, se um algoritmo tem uma complexidade O (n), isso significa que o número de operações cresce linearmente com o tamanho de entrada.
Observa-se no gráfico acima, a diferença no tempo de processamento (eixo Y) conforme a quantidade de dados de entrada aumenta (eixo X).
Como implementar a notação O grande baseando-se no algoritmo?
Considere o seguinte algoritmo:
function calcular() {
return 15 * (30 + 90);
}
print(calcular());
O exemplo de algoritmo acima apenas realiza um pequeno cálculo. No caso acima, não há repetições, portanto o tempo de demora é representado como O(1).
Ao utilizarmos loops dentro do algoritmo o resultado pode variar um pouco:
functioncalcular(int $no) {
return 15 * ($no + 90);
}
foreach ($i = 0; $i < 1000; i++) {
print(calcular($i));
}
O Bubble Sort é um dos algoritmos de ordenação mais simples, que consiste em percorrer os N elementos de um vetor, para cada vez percorrida, todos os elementos são comparados com o seu próximo, para verificar se estão na ordem desejada. O passe pela lista é repetido até que não seja necessário nenhuma troca, indicando que a lista está ordenada. O algoritmo recebe esse nome porque os itens menores borbulham gradualmente até o topo da lista.
Esse algoritmo não é adequado para listas grandes, pois sua complexidade é de O(n²).
O Bubble Sort é mais útil para fins educacionais, pois é simples de entender e implementar. Em ambientes de produção, são preferidos algoritmos de classificação mais eficientes, como Quicksort, Heapsort ou Mergesort.
Exemplo:
Embora o Bubble Sort não seja eficiente em muitos casos devido à sua complexidade computacional (O(n²) no pior caso), ele pode ser útil em certas situações:
- Tamanho pequeno da lista: O Bubble Sort pode ser uma boa opção se a lista for relativamente pequena. Isso ocorre porque sua ineficiência é menos perceptível com listas menores.
- Listas quase ordenadas: O Bubble Sort se comporta bem quando a lista já está quase ordenada, já que é capaz de detectar se a lista está ordenada rapidamente.
- Simplicidade: Em termos de implementação, o Bubble Sort é bastante simples de entender e implementar. Isso pode ser útil em ambientes educacionais onde o foco é aprender os conceitos básicos de algoritmos de ordenação.
- Detecção de lista ordenada: O Bubble Sort é um dos poucos algoritmos que pode confirmar que uma lista está completamente ordenada em uma única passagem.
- Em memória: Como o Bubble Sort é um algoritmo de classificação in-place (ou seja, não precisa de espaço de memória extra significativo para realizar a classificação), pode ser uma escolha adequada se a memória for uma consideração.
No entanto, na maioria dos casos práticos, é aconselhável usar algoritmos de ordenação mais eficientes, como Quicksort, Mergesort ou Heapsort. Estes algoritmos têm complexidade computacional melhor e, consequentemente, lidam melhor com conjuntos de dados maiores.