Como ordenar listas de forma recursiva em Python

Escrito por g.s. jackson | Traduzido por josé fabián
  • Compartilhar
  • Tweetar
  • Compartilhar
  • Pin
  • E-mail
Como ordenar listas de forma recursiva em Python
O método "merge sort" em Python pode fazer com que buscas grandes sejam rápidas e eficientes (Jupiterimages/Photos.com/Getty Images)

Ordenar é uma tarea tradicionalmente difícil na ciência de computadores. Escolher um algoritmo de ordenamento que seja eficiente e rápido pode ser difícil. Muitas vezes a escolha certa requer conhecimentos dos dados que estejam sendo ordenados, e métodos especializados funcionam muito melhor do que outros generalizados. No entanto, certos procedimentos de ordenamento, tais como o "merge sort" ("classificar e ordenar"), podem funcionar em situações generalizadas, dividindo listas e ordenando os conjuntos menores de forma recursiva.

Outras pessoas estão lendo

A lista

Um "merge sort" é um algoritmo de "divisão e conquista", pois se tomam porções da lista e se dividem em metades até chegar aos seus componentes individuais, os quais são unidos depois na ordem. Por exemplo, comece com a seguinte lista numérica:

5 6 2 4 1 9 8 3 7

Ordenar uma lista como esta usando "merge sort" requerirá dividi-la em metades de forma repetida até que cada número fique isolado. Depois, ao ordenar os números, eles se combinarão na ordem correta (neste caso, do menor ao maior).

O método de combinação

O método de combinação é simples:

def merge(first, second)

O método toma duas listas e as combina começando pelo início de cada uma. Depois, adiciona a menor quantidade possível de elementos de cada lista em uma nova. O resultado é uma lista ordenada (lembre-se de inserir espaços adequadamente depois das palavras "while" e "if/else"):

while i < len(first) and j < len(second): if first[i] <= second[j]: new_list.append(first[i]) i = i + 1

else: new_list.append(second[j]) j = j + 1}

Finalmente, quando uma das duas listas acabar, os valores restantes serão colocados na nova:

new_list += first[i:] new_list += second[j:] return end_list

Condições do "merge sort"

O "merge sort" atual conduz o algoritmo de ordenamento principal. Há duas partes funcionais principais: o aspecto condicional que detém a recursividade depois de que as listas são subdivididas, e a recursividade atual que as divide em metades. A condição de parada aparece primeiro:

def mergesort(list):

if len(list) == 1: return list

Isso certifica que quando uma sublista contiver apenas um elemento, ele será devolvido de forma de poder ser combinado em ordem com os outros.

Recursividade do "merge sort"

A segunda metade do processo é a recursividade. Continuando com a condição "if", adicione o seguinte:

else:

middle = len(list) / 2 start = mergesort(list[middle:]) end = mergesort(list[:middle]) return merge(start, end)

Por causa da recursividade, depois de que as listas sejam divididas até os seus componentes individuais, o algoritmo volta para o último método executado. Portanto, quando for executada a sentença "return merge(start, end)", o algoritmo devolverá uma lista classificada e ordenada a partir de duas listas menores que passaram pelo mesmo processo.

Não perca

Filtro:
  • Geral
  • Artigos
  • Slides
  • Vídeos
Mostrar:
  • Mais relevantes
  • Mais lidos
  • Mais recentes

Nenhum artigo disponível

Nenhum slide disponível

Nenhum vídeo disponível