Aprender algoritmos

Capítulo 5. Seleção sem chapéu

Este trabalho foi traduzido com recurso a IA. Agradecemos o teu feedback e comentários: [e-mail]

Neste capítulo, aprenderás:

• Como os algoritmos de ordenação baseados na comparação requerem duas operações fundamentais:

  • less(i,j) Determina se A[i] < A[j].

  • swap(i,j) troca o conteúdo de A[i] eA[j].

• Como fornecer uma função de comparação ao ordenar; por exemplo, podes ordenar inteiros ou valores de cadeia por ordem descendente. A função de comparação também pode ordenar estruturas de dados complexas sem ordenação predefinida; por exemplo, não é claro como ordenar uma coleção de pontos bidimensionais (x, y).

• Como identificar algoritmos de ordenação O(^N2) ineficientes, como o Insertion Sort e o Selection Sort, a partir da estrutura do seu código.

• Recursão, em que uma função se pode chamar a si própria. Este conceito fundamental da informática constitui a base de uma estratégia de dividir para conquistar para resolver problemas.

• Como o Merge Sort e o Quicksort podem ordenar uma matriz de N valores em O(N logN) utilizando dividir para conquistar. Como o Heap Sort também garante O(N log N).

• Como o Tim Sort combina o Insertion Sort e a funcionalidade do Merge Sort para implementar o algoritmo de ordenação predefinido do Python em O(N log N) garantido.

Neste capítulo, apresento algoritmos que reorganizam os N valores de um array para que fiquem em ordem crescente. Organizar uma coleção de valores em ordem ordenada ...