Processos de ordenação de números são muito importantes em computação. Existem vários tipos de algoritmos de ordenação, como, por exemplo: insertionsort, selectionsort, bubblesort, shellsort, heapsort, quicksort, mergesort, radixsort, entre outros.
Usamos uma notação matemática especial para representar o desempenho de algoritmos. A diferença está no tempo de execução. O pior deles leva tempo O(n2) e o melhor deles leva tempo O(n). Quanto mais rápido cresce a função (n2. cresce mais rápido do que n) pior ela é, porque requer um maior número de operações para uma entrada de n elemento. Entretanto, os recursos necessários para o desenvolvimento desses algoritmos também mudam. Os algoritmos de tempo O(n) utilizam menos recursos computacionais em relação aos que levam tempo quadrático O(n2).
Em muitas aplicações, os elementos precisam ser ordenados. E, para ordenar, você precisa rearranjar um conjunto de informações numa disposição que pode ser crescente ou decrescente. O principal objetivo de se ter os dados ordenados é a facilidade posterior de se realizar buscas.
Imagine procurar uma palavra em um dicionário físico, porém de forma que as palavras foram colocadas aleatoriamente. Ficaria muito difícil de encontrar a palavra, concorda? Por isso, no dicionário, as palavras estão ordenadas alfabeticamente. As comparações são poucas e a busca muito rápida, mesmo havendo milhares de palavras de entrada, representadas por n.
O bubblesort ou ordenação por bolhas é assim chamado porque tem a ideia de que os números maiores vão flutuando como bolhas até chegar na última posição, ou em suas posições corretas. Na computação, o bubblesort é um dos algoritmos de ordenação mais utilizados, por ser fácil de entender, desenvolver e de se usar.
Você vai comparando elementos dois a dois e quando o primeiro número é maior do que o segundo, acontece a troca dos elementos. Dessa forma, a comparação acontece do primeiro com o segundo elemento, do segundo com o terceiro elemento, do terceiro com o quarto, e assim sucessivamente até o penúltimo com o último elemento. Isso garante que o último elemento será o maior.
O processo continua, porém, agora considera a lista do primeiro até o penúltimo elemento, pois o último já está ordenado. O processo termina quando sobrar apenas um elemento para ordenar. Nesse caso, a lista toda já estará ordenada.
Para exemplificar, vamos considerar os valores inteiros relacionados a seguir:
26 47 38 11 95
26 47 38 11 95 // compara 26 e 47
26 47 38 11 95 // compara 47 e 38
26 38 47 11 95 // compara 47 e 11
26 38 11 47 95 // compara 47 e 95
26 38 11 47 95 // final do primeiro processo
26 38 11 47 95 // compara 26 e 38
26 38 11 47 95 // compara 38 e 11
26 11 38 47 95 // compara 38 e 47
26 11 38 47 95 // final do segundo processo
26 11 38 47 95 // compara 26 e 11
11 26 38 47 95 // compara 26 e 38
11 26 38 47 95 // final do terceiro processo
11 26 38 47 95 // compara 11 e 26
11 26 38 47 95 // final do último processo
11 26 38 47 95 // final do último processo
O algoritmo do BubbleSort está a seguir:
Bolha (numeros [] inteiro)
início_módulo
Declarar
constante n ← numeros.tamanho inteiro;
aux, i, j inteiro;
para i de 0 até n-2 passo +1 faça
para j de 0 até n-2-i passo +1 faça
se (numeros[j] > numeros[j+1])
então
aux ← numeros[j];
numeros[j] ← numeros[j+1];
numeros[j+1] ← aux;
fimse;
fimpara;
fimpara;
fim_módulo;
O QuickSort é o algoritmo de ordenação por troca de partição. O Quicksort usa a ideia de uma ordenação dos elementos por meio de partições.
No Quicksort, a lista é dividida em sublistas. Essas sublistas são as partições. Cada uma das partições é dividida novamente em outras partições até que a divisão não tem mais como acontecer. Nesse caso, a partição vai ter apenas um elemento.
A ideia do Quicksort é dividir o problema em problemas menores e depois conquistar para que possam ser solucionados de forma mais fácil e rápida.
O Pivô é o elemento escolhido de dentro da lista, normalmente, é o primeiro elemento. Ele ajuda a determinar as partições, de forma que os elementos da primeira partição são menores ou iguais ao pivô, depois vem o pivô, e os elementos da segunda lista são maiores do que o pivô.
Para exemplificar, vamos considerar os valores inteiros relacionados a seguir:
25 57 48 37 12 92 86 33
(12) 25 (57 48 37 92 86 33) // pivô 25
12 25 (57 48 37 92 86 33) // pivô 12
12 25 (48 37 33) 57 (92 86) // pivô 57
12 25 (37 33) 48 57 (92 86) // pivô 48
12 25 (33) 37 48 57 (92 86) // pivô 37
12 25 33 37 48 57 (92 86) // pivô 33
12 25 33 37 47 57 (86) 92 // pivô 92
12 25 33 37 47 57 86 92 // pivô 86
12 25 33 37 47 57 86 92 // lista ordenada