Tutorial do algoritmo Python Merge Sort
Aprenda como implementar Merge Sort em Python. Um exemplo interativo passo a passo da estratégia de classificação Dividir e Conquistar.
Visão geral
Merge Sort é um algoritmo de classificação altamente eficiente que utiliza uma estratégia de dividir e conquistar. Ele divide uma lista não classificada em sublistas menores, classifica essas sublistas e depois as mescla novamente.
O algoritmo divide recursivamente o array ao meio até atingir submatrizes de elemento único. Em seguida, ele mescla as submatrizes classificadas comparando os elementos de cada lado e colocando-os na ordem de classificação. Isso garante uma complexidade de tempo ideal.
Independentemente de a matriz inicial ser classificada, invertida ou completamente aleatória, Merge Sort é executado em tempo O(n log n). No entanto, requer O(n) espaço extra para armazenar as sublistas durante a fase de fusão.
Saída de código e execução
Uma implementação recursiva padrão do algoritmo Merge Sort em Python.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List: ", sorted_data)Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List: [3, 9, 10, 27, 38, 43, 82]Implementação passo a passo
- Classificar listas vinculadas onde a estrutura do nó facilita a fusão sem copiar
- Rotinas de classificação externa para arquivos que não cabem inteiramente na RAM do sistema
- Aplicativos de classificação estável onde as chaves correspondentes devem preservar sua ordem original
Perguntas frequentes
Merge Sort é um algoritmo de classificação estável?
Sim, Merge Sort é estável. Ao comparar elementos idênticos, o elemento do subarray esquerdo (original primeiro) é colocado primeiro, preservando suas posições relativas originais.
Por que o Python usa o Timsort em vez do Merge Sort puro?
O `sorted()` integrado do Python usa Timsort, que é um algoritmo híbrido que combina Merge Sort e Insertion Sort. Ele otimiza padrões de dados do mundo real, identificando subsegmentos já classificados, tornando-os mais rápidos do que o Merge Sort puro.
Tópicos Relacionados
Explore o algoritmo quicksort em Python. Aprenda seleção dinâmica, particionamento e recursão neste exemplo de codificação interativo.
Algoritmos de classificação PythonExplore algoritmos de classificação python. Visualize a classificação por bolha e a classificação por mesclagem nativamente em um contexto IDE do navegador.
Algoritmo de pesquisa binária PythonPesquise listas classificadas em tempo logarítmico O (log n). Execute e entenda a pesquisa binária em Python, incluindo lógica passo a passo, casos extremos e otimizações.