Classificando e pesquisando em Python

Se você recebesse um pedaço de papel com uma lista de 1.000 nomes e lhe pedissem para encontrar algum nome, mas essa lista não estivesse em nenhuma ordem (por exemplo, ordem alfabética), seria muito frustrante, não é? Colocar essa lista em ordem, embora leve muito tempo, torna muito mais fácil encontrar o nome. Assim, ter as coisas em ordem é um desejo natural que nós seres humanos temos, e pesquisar essa lista claramente exigiria menos esforço do que pesquisar uma lista não ordenada.

Vamos passar para o mundo dos computadores, onde as listas que podem ser necessárias para pesquisar são muito grandes e onde o desempenho pode ser afetado mesmo com computadores rápidos. Neste caso, ter um adequado classificando e pesquisando algoritmo seria uma solução para tal problema. Enquanto Ordenação é colocar uma lista de valores em ordem, procurando é o processo de encontrar a posição de um valor dentro de uma lista.

Para deixar claro quão crítica essa questão pode ser, deixe-me mostrar o que Donald Knuth, um cientista da computação americano, matemático e professor emérito da Universidade de Stanford mencionou em The Art of Computer Programming, vol.3, Sorting and Searching, página 3:

Os fabricantes de computadores da década de 1960 estimaram que mais de 25% do tempo de execução de seus computadores era gasto em classificação, quando todos os seus clientes eram levados em consideração. De fato, havia muitas instalações em que a tarefa de classificação era responsável por mais da metade do tempo de computação. A partir dessas estatísticas, podemos concluir que (i) existem muitas aplicações importantes de classificação, ou (ii) muitas pessoas classificam quando não deveriam, ou (iii) algoritmos de classificação ineficientes têm sido de uso comum.

Neste tutorial, descreverei especificamente o Ordenação de Seleção algoritmo (ordenação) e o Pesquisa linear algoritmo (busca).

Algoritmo de Ordenação de Seleção

o Ordenação de Seleção algoritmo é baseado na seleção sucessiva de valores mínimos ou máximos. Suponha que temos uma lista que queremos classificar em ordem crescente (de valores menores para maiores). O menor elemento estará no início da lista e o maior elemento estará no final da lista.

Digamos que a lista original tenha a seguinte aparência:

| 7 | 5 | 3.5 | 4 | 3.1 |

A primeira coisa que fazemos é encontrar o mínimo valor na lista, que é no nosso caso 3.1.

Após encontrar o valor mínimo, troca esse valor mínimo com o primeiro elemento da lista. Ou seja, troque 3.1 com 7. A lista agora terá a seguinte aparência:

| 3.1 | 5 | 3.5 | 4 | 7 |

Agora que temos certeza de que o primeiro elemento está na posição correta na lista, repetimos o passo acima (encontrando o valor mínimo) a partir do segundo elemento na lista. Podemos descobrir que o valor mínimo na lista (a partir do segundo elemento) é 3.5. Assim, agora trocamos 3.5 com 5. A lista agora fica da seguinte forma:

| 3.1 | 3.5 | 5 | 4 | 7 |

Neste ponto, temos certeza de que o primeiro elemento e o segundo elemento estão em suas posições corretas.

Agora, verificamos o valor mínimo no restante da lista, que é a partir do terceiro elemento 5. O valor mínimo no restante da lista é 4e agora trocamos por 5. A lista fica assim:

| 3.1 | 3.5 | 4 | 5 | 7 |

Temos agora a certeza de que o primeiro três os elementos estão nas posições corretas, e o processo continua assim.

Vamos ver como o algoritmo Selection Sort é implementado em Python (baseado em Isai Damier):

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k
                
        swap(aList, least, i)
        
def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp

Vamos testar o algoritmo adicionando as seguintes instruções no final do script acima:

my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5]
selectionSort(my_list)
print my_list

Nesse caso, você deve obter a seguinte saída:

[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]

Algoritmo de Pesquisa Linear

o Pesquisa linear aO lgorithm é um algoritmo simples, onde cada item da lista (a partir do primeiro item) é investigado até que o item necessário seja encontrado ou até o final da lista ser alcançado.

O algoritmo Linear Search é implementado em Python da seguinte forma (com base na Python School):

def linearSearch(item,my_list):
    found = False
    position = 0
    while position < len(my_list) and not found:
        if my_list[position] == item:
            found = True
        position = position + 1
    return found

Vamos testar o código. Digite a seguinte instrução no final do script Python acima:

bag = ['book','pencil','pen','note book','sharpener','rubber']
item = input('What item do you want to check for in the bag?')
itemFound = linearSearch(item,bag)
if itemFound:
    print 'Yes, the item is in the bag'
else:
    print 'Oops, your item seems not to be in the bag'

Quando você entra no inputcertifique-se de que está entre aspas simples ou duplas (ou seja, 'pencil'). Se você inserir 'pencil'por exemplo, você deve obter a seguinte saída:

Yes, the item is in the bag

Considerando que, se você entrar 'ruler' como entrada, você obterá a seguinte saída:

Oops, your item seems not to be in the bag

Como podemos ver, o Python prova novamente ser uma linguagem de programação que facilita a programação de conceitos algorítmicos como fizemos aqui, lidando com Ordenação e procurando algoritmos.

É importante notar que existem outros tipos de algoritmos de ordenação e busca. Se você quiser se aprofundar nesses algoritmos usando Python, consulte esta página.