Introdução
Classificar um array é um dos primeiros problemas sérios estudados no curso clássico "Algoritmos e Estruturas de Dados" da disciplina de ciência da computação. Nesse sentido, as tarefas de classificação por escrito e as perguntas correspondentes são frequentemente encontradas em entrevistas para a posição de um desenvolvedor estagiário ou júnior.
Formulação do problema
Tradicionalmente, vale a pena iniciar a apresentação das soluções para o problema com seu enunciado. Normalmente, a tarefa de classificação envolve ordenar algum array de inteiros em ordem crescente. Mas, na verdade, isso é uma simplificação exagerada. Os algoritmos descritos nesta seção podem ser usados para ordenar uma matriz de quaisquer objetos entre os quais uma relação de ordenação seja estabelecida (ou seja, para quaisquer dois elementos, podemos dizer: o primeiro é maior que o segundo, o segundo é maior que o primeiro ou eles são iguais). Você pode classificar em ordem crescente e decrescente. Usaremos a simplificação padrão.
Ordenação rápida
Da última vez, falamos sobre um tipo um pouco mais complexo - o tipo de inserção. Hoje vamos falar sobre um algoritmo muito mais complexo - classificação rápida (também chamada de classificação Hoare).
Descrição do Algoritmo
O algoritmo de classificação rápida é recursivo, portanto, para simplificar, o procedimento tomará como entrada os limites do segmento da matriz de l inclusive a r não inclusivo. É claro que, para classificar o array inteiro, 0 deve ser passado como o parâmetro l en como r, onde, por tradição, n denota o comprimento do array.
O algoritmo quicksort é baseado no procedimento de partição. A partição seleciona algum elemento da matriz e reorganiza os elementos da matriz de tal forma que a matriz é dividida em 2 partes: o lado esquerdo contém elementos que são menores que este elemento, e o lado direito contém elementos que são maiores ou iguais a este elemento. Esse elemento de separação é chamado de pivô .
Implementação do Partiion:
partition(l, r):
pivot = a[random(l ... r - 1)]
m = l
for i = l ... r - 1:
if a[i] < pivot:
swap(a[i], a[m])
m++
return m
O pivô em nosso caso é escolhido aleatoriamente. Este algoritmo é chamado de randomizado . Na verdade, o pivô pode ser selecionado de várias maneiras: ou pegar um elemento aleatório, ou pegar o primeiro / último elemento da seção, ou selecioná-lo de alguma forma “inteligente”. A escolha do pivô é muito importante para a complexidade final do algoritmo de classificação, mas falaremos mais sobre isso posteriormente. A complexidade do procedimento de partição é O (n), onde n = r - l é o comprimento da seção.
Agora usamos partição para implementar classificação:
Implementação de partição:
sort(l, r):
if r - l = 1:
return
m = partition(l, r)
sort(l, m)
sort(m, r)
Um caso extremo - uma matriz de um elemento tem a propriedade de ser ordenada. Se a matriz for longa, usamos partição e chamamos o procedimento recursivamente nas duas metades da matriz.
Se você percorrer a classificação escrita no exemplo do array 1 2 2, verá que ela nunca terminará. Por que isso aconteceu?
Ao escrever a partição, partimos do pressuposto - todos os elementos do array devem ser únicos. Caso contrário, o valor de retorno de m será le a recursão nunca terminará, porque sort (l, m) chamará sort (l, l) e sort (l, m). Para resolver esse problema, você precisa dividir a matriz não em 2 partes (<pivô e> = pivô), mas em 3 partes (<pivô, = pivô,> pivô) e chamar a classificação recursiva para a 1ª e a 3ª partes.
Análise
Proponho analisar esse algoritmo.
A complexidade de tempo do algoritmo é expressa por meio dele pela fórmula: T (n) = n + T (a * n) + T ((1 - a) * n). Assim, quando chamamos a classificação de uma matriz de n elementos, leva cerca de n operações para executar a partição e executar-se 2 vezes com os parâmetros a * n e (1 - a) * n, porque o pivô dividiu o elemento em frações.
No melhor caso, a = 1/2, ou seja, o pivô divide a área em duas partes iguais a cada vez. Neste caso: T (n) = n + 2 * T (n / 2) = n + 2 * (n / 2 + 2 * T (n / 4)) = n + n + 4 * T (n / 4 ) = n + n + 4 * (n / 4 + 2 * T (n / 8)) = n + n + n + 8 * T (n / 8) =…. O total será log (n) termos, porque os termos aparecem até que o argumento diminua para 1. Como resultado, T (n) = O (n * log (n)).
No pior caso, a = 1 / n, ou seja, o pivô corta exatamente um elemento. A primeira parte da matriz contém 1 elemento e a segunda contém n - 1. Ou seja: T (n) = n + T (1) + T (n - 1) = n + O (1) + T (n - 1) = n + O (1) + (n - 1 + O (1) + T (n - 2)) = O (n ^ 2). O quadrado aparece devido ao fato de que aparece na fórmula para a soma de uma progressão aritmética que aparece no processo de rabiscar a fórmula.
Em média, idealmente, a expectativa matemática de várias opções deve ser considerada. Pode-se mostrar que se o pivô divide a matriz em uma proporção de 1: 9, então a assintótica resultante ainda será O (n * log (n)).
A classificação é chamada de rápida, porque a constante que está oculta sob o sinal O acaba sendo muito pequena na prática, o que levou ao uso generalizado do algoritmo na prática.
Consulte Mais informação
