Lançado · em melhoria
Algorithm
Algoritmos de ordenação colocam dados em ordem: merge sort, quicksort, heapsort, estabilidade, o limite inferior n log n e as ordenações nativas.
Ordenar é reorganizar elementos segundo uma ordem definida, como numérica, alfabética ou cronológica. Há duas grandes famílias: as ordenações por comparação (bubble sort, insertion sort, selection sort, merge sort, quicksort e heapsort), que só perguntam se um elemento vem antes de outro, e as que não comparam, como counting sort e radix sort, que usam diretamente os valores inteiros ou seus dígitos.
A ordenação é a etapa preparatória de busca binária, remoção de duplicatas, junção de intervalos, rankings e muitas outras tarefas, por isso está entre os primeiros algoritmos estudados. Conhecer o limite inferior Ω(n log n) das ordenações por comparação, a diferença entre ordenação estável e in-place e o funcionamento das ordenações nativas, como o Timsort do Python ou o introsort da maioria das implementações de std::sort em C++, ajuda a escolher bem no trabalho e em entrevistas.
Para estudar, acompanhe à mão o insertion sort, o merge sort e o quicksort em arrays pequenos, depois implemente merge sort e quicksort e compare o melhor caso, o caso médio e o pior caso. Em seguida, pratique ordenar com funções de chave e comparadores e resolva problemas baseados em ordenação, como juntar intervalos ou contar inversões.
O merge sort divide a entrada ao meio e intercala as metades; o quicksort particiona em torno de um pivô. Ambos rodam em O(n log n) no caso médio.
Uma ordenação estável preserva a ordem original de elementos com chaves iguais; uma ordenação in-place quase não usa memória extra. Qual importa mais depende da tarefa.
Um argumento com árvores de decisão mostra que toda ordenação por comparação precisa da ordem de n log n comparações no pior caso. Merge sort e heapsort atingem esse limite.
Counting sort e radix sort ordenam inteiros com faixa de valores ou número de dígitos limitado em tempo quase linear, sem comparar os elementos entre si.
merge_sort divide a lista ao meio, ordena cada metade recursivamente e depois intercala as duas, sempre pegando o menor dos dois elementos da frente. Em caso de empate, pega primeiro o da esquerda (<=), o que torna a ordenação estável, e roda em O(n log n) para qualquer entrada. A última linha compara o resultado com a função nativa sorted().
merge_sort.py
def merge_sort(items):
"""Return a new sorted list (stable, O(n log n))."""
if len(items) <= 1:
return list(items)
mid = len(items) // 2
left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # take the left one on ties: stable
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort(data) == sorted(data)) # True
python merge_sort.pySeis capítulos que levam você da instalação aos conceitos essenciais de Ordenação.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Ordenação.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.