Estes são exemplos de algoritmos para classificar uma pilha de cartões com muitos números diferentes, para que os números estejam em ordem.
Os jogadores começam com uma pilha de cartas que não foram classificadas.
Primeiro algoritmo
Este algoritmo passa pela pilha de cartas, uma carta de cada vez. Esta carta é comparada com a próxima carta na pilha. Observe que esta posição só muda no passo 6. Este algoritmo é chamado de bubble sort. Ele é lento.
- Se a pilha de cartões estiver vazia, ou se ela contiver apenas um cartão, ela é classificada; você está acabado.
- Pegue a pilha de cartas. Veja a primeira carta (a parte superior) da pilha.
- O cartão que você está olhando é o cartão A. A posição onde o cartão A está atualmente, está na pilha P.
- Se não houver mais cartas na pilha depois da carta A, vá para o passo 8.
- A próxima carta na pilha é a carta B.
- Se a carta B tiver um número inferior à carta A, troque as posições das cartas A e B. Lembre-se de que você fez isso. Quando trocar as cartas, não mude a posição P.
- Se houver outra carta na pilha após a posição P, olhe para ela; volte ao passo 3.
- Se você não trocou a posição de nenhuma carta na última rodada, você está feito; a pilha de cartas é classificada.
- Caso contrário, volte ao passo 2.
Exemplo passo a passo
Vamos pegar uma pilha de cartões com os números "5 1 4 2 8", e classificá-la do menor número para o maior usando este algoritmo. Em cada etapa, o algoritmo compara os elementos escritos em negrito. A parte superior da pilha de cartas está do lado esquerdo.
Primeiro passe:
( 5 1 4 2 8 ) → {\a2}displaystyle {\a2} 
( 1 5 4 2 8 ) Aqui, o algoritmo compara os dois primeiros elementos, e os troca.
( 1 5 4 2 8 ) → {\i1}a ( 1 4 5 2 8 )
( 1 4 5 2 8 ) → {\i1}displaystyle {\i} ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\i1}displaystyle {\i} ( 1 4 2 5 8 ) Estes elementos já estão em ordem, portanto o algoritmo não os troca.
Segundo passe:
( 1 4 2 5 8 ) → {\i1}displaystyle {\i1} ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\i1}displaystyle {\i} ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\i1}displaystyle {\i} ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\i1}displaystyle {\i} ( 1 2 4 5 8 )
Agora, a pilha de cartões já
está classificada, mas nosso algoritmo não sabe disso. O algoritmo precisa de um passe inteiro sem nenhuma troca para saber que está classificado.
Terceiro passe:
( 1 2 4 5 8 ) → {\a10} ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\i1}displaystyle {\i} ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\i1}displaystyle {\i} ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\i1}displaystyle {\i} ( 1 2 4 5 8 )
Finalmente, a matriz é classificada, e o algoritmo pode parar.
História
Este é um algoritmo fácil de entender para a classificação. Os cientistas da computação o chamaram de Bubble sort, porque elementos menores subirão ao topo, mudando sua posição em cada corrida. Infelizmente, o algoritmo não é muito bom, porque precisa de muito tempo (muitos passam pela pilha de cartas) para classificá-lo.
Segundo algoritmo
Este algoritmo usa outra idéia. Às vezes a solução de um problema é difícil, mas o problema pode ser alterado para que seja feito de problemas mais simples que sejam mais fáceis de resolver. Isto é chamado de recursividade. É mais difícil de entender do que o primeiro exemplo, mas ele dará um algoritmo melhor.
Idéia básica
- Se a pilha não tiver cartões, ou tiver apenas um cartão, ela é classificada, e você está acabado.
- Dividir a pilha de cartas em duas metades de aproximadamente o mesmo tamanho. Se houver um número ímpar de cartas, uma das duas pilhas terá uma carta a mais do que a outra.
- Ordene cada uma das duas pilhas usando este algoritmo (Para cada pilha, comece no item 1 desta lista).
- Fundir as duas pilhas classificadas, como descrito abaixo.
- O resultado é uma pilha classificada de cartas. Você está feito.
Fusão de duas pilhas
Isto funciona com duas pilhas de cartões. Uma delas é chamada de A, a outra de B. Há uma terceira pilha que está vazia no início, chamada de C. No final, ela conterá o resultado.
- Se a pilha A ou a pilha B estiver vazia, coloque todas as cartas da pilha que não está vazia em cima da pilha C; você está feito, a pilha C é o resultado da fusão. (Nota: pegue a pilha inteira, e coloque-a na pilha C; fazê-lo cartão por cartão mudará a ordem e não funcionará como deveria).
- Veja as cartas superiores da pilha A e da pilha B. Coloque a que tem o número inferior em cima da pilha C. Se a pilha C não tinha cartas nela, ela terá agora uma carta.
- Se a pilha A ou a pilha B ainda tiver cartões, volte ao passo 1 para classificá-los.
História
John von Neumann desenvolveu este algoritmo em 1945. Ele não o chamou de Sorting by numbers, ele o chamou de Mergesort. É um algoritmo muito bom para ordenação, comparado a outros.
Terceiro algoritmo
O primeiro algoritmo leva muito mais tempo para classificar as cartas do que o segundo, mas pode ser melhorado (melhorado). Olhando para a classificação de bolhas, pode-se notar que as cartas com números altos se movem do topo da pilha muito rapidamente, mas as cartas com números baixos na parte inferior da pilha levam muito tempo para subir (mover-se para o topo). Para melhorar o primeiro algoritmo aqui é a idéia:
Ao invés de comparar duas cartas que estão ao lado uma da outra, no início é escolhida uma carta "especial". Todas as outras cartas são então comparadas com esta carta.
- Começamos com uma pilha A. Haverá duas outras pilhas B e C, que serão criadas mais tarde.
- Se a pilha A não tem cartões, ou tem apenas um cartão, terminamos a triagem.
- Uma carta é retirada da pilha A, se possível de forma aleatória. Isto é chamado de pivô.
- Todas as cartas restantes da pilha A são comparadas a este pivô. As cartas com um número menor vão para a pilha B, aquelas com um número igual ou maior vão para a pilha C.
- Se houver algum cartão nas pilhas B ou C, estas pilhas precisam ser classificadas com o mesmo algoritmo (Comece na pos 1 desta lista para a pilha B e para a pilha C, por sua vez).
- Feito. A pilha classificada de cartas tem primeiro a pilha classificada B, depois o pivô, e depois a pilha classificada C.
História
Este algoritmo foi desenvolvido por C. A. R. Hoare em 1960. É um dos algoritmos mais utilizados hoje em dia para a classificação. Ele é chamado de Quicksort.
