Que tipos de ordenação conhece e quais são as suas dificuldades em tempo e memória?

Existem muitos algoritmos de ordenação, aqui estão os principais com a sua complexidade temporal e espacial:

• Ordenação Bubble (Bubble Sort)

  • Tempo: O(n²) no pior e médio caso
  • Memória: O(1) (ordenamento in-place)

• Ordenação por inserção (Insertion Sort)

  • Tempo: O(n²) no pior caso, O(n) no melhor (array quase ordenado)
  • Memória: O(1)

• Ordenação por seleção (Selection Sort)

  • Tempo: O(n²) em todos os casos
  • Memória: O(1)

• Ordenação por fusão (Merge Sort)

  • Tempo: O(n log n) em todos os casos
  • Memória: O(n) (requer memória adicional para fusão)

• Ordenação rápida (Quick Sort)

  • Tempo: O(n log n) em média, O(n²) no pior caso (raro)
  • Memória: O(log n) (pilha recursiva)

• Ordenação por heap (Heap Sort)

  • Tempo: O(n log n) em todos os casos
  • Memória: O(1)

• Timsort — ordenação híbrida usada em Python e Java

  • Tempo: O(n log n) em média e no pior caso
  • Memória: O(n)

A escolha do algoritmo depende do tamanho dos dados, dos requisitos de memória e da estabilidade da ordenação (se mantém a ordem de elementos iguais). Por exemplo, o Merge Sort é estável, o Quick Sort costuma ser mais rápido, mas instável.