Classificação rápida em C

“Quicksort ou Quick-Sort é um algoritmo de classificação. Classificação rápida é um algoritmo de divisão e conquista. Deixe a lista de personagens ser classificados por:

Q W E R T Y U I O P

A lista classificada é:

E i o p q r t u w y

Isso é meio que ascendente. Neste artigo, a explicação para o Quicksort, as espécies ascendentes, usando a lista: "q", "w", "e", "r", "t", "y", "u", "i", "" O ”,“ P ” e a linguagem C.”

Classificação rápida em teoria

Da lista, "Q", "W", "E", "R", "T", "Y", "U", "I", "O", "P", Classificação rápida parecerá por um valor central, chamado de pivô. Na lista classificada,

"E", "I", "O", "P", "Q", "R", "T", "U", "W", "Y"

O pivô é "q" ou "r", já que a lista está em número. Se a lista fosse ímpar em número, o pivô teria sido claramente o valor do meio. "Q" no índice 4 é escolhido como o pivô. Lembre -se de que a lista a ser classificada é,

Q W E R T Y U I O P

e não a lista classificada. Existem 10 elementos nesta lista não classificada.

O primeiro estágio é procurar o pivô (valor central) na lista não classificada. O segundo estágio é colocar o pivô em sua posição legítima na lista não classificada (neste caso, índice 4); e coloque todos os elementos menores que o pivô à esquerda e todos os elementos maiores que o pivô à direita. Os elementos à esquerda do pivô não devem ser necessariamente classificados, e os elementos à direita do pivô não devem necessariamente ser classificados. Esta fase é a fase de divisão ou partição no algoritmo de dividir e conquista. Existem três partes para este estágio: a sub-lista esquerda, a sub-lista direita e a sub-lista do meio. A sub-lista do meio consiste em apenas um elemento, que é o pivô. Para a lista acima não derrotada, o resultado seria:

E i o p q w r t y u

Como o pivô já está em sua posição final, a última etapa, em teoria, é classificar a sub-lista esquerda e classificar a sub-lista direita. Isso é conquistando. É uma coincidência que a sub-lista esquerda, neste caso, já esteja classificada. A sub-lista certa, neste caso, ainda está para ser classificada. Classificando a sub-lista esquerda e direita separadamente, o resultado é:

E i o p q r t u w y

como requerido.

Classificação rápida na prática

Na prática, a partição com alguma classificação (troca) é feita repetidamente de maneira recursiva. Isto é, novas sub-listas menores e menores são desenvolvidas com seus próprios pivôs. Em outras palavras, sub-listas de três partes e menores estão sendo desenvolvidas a partir da lista principal até que toda a lista seja classificada.

Há um problema quando se trata de escolher o pivô. Toda a lista não classificada não pode ser digitalizada elemento a elemento para obter o pivô certo. Isso vai demorar muito tempo. Então, um palpite inteligente tem que ser feito.

Lembre -se de que a lista a ser classificada é:

Q W E R T Y U I O P

Deixe o palpite inteligente ser P, o elemento mais certo. Em seguida, deixe todos os elementos menos que P, lendo da esquerda, vá para a esquerda de P e deixe todos os elementos maiores que P, ainda lendo da esquerda, vá para a direita de P sem classificação consciente. Isto dá:

E i o p q w r t y u

As três primeiras sub-listas são:

"E", "i", "O", "p", "q", "w", "r", "t", "y", "u"

P está em sua posição legítima (na prática, pode não ser necessariamente o índice 4; aqui, é o índice 3 nesta fase). O próximo passo é uma chamada recursiva para dividir a sub-lista esquerda em três sub-listas; e a sub-lista direita em três sub-listas, cada uma com seu próprio pivô, de um palpite inteligente.

Dividindo "E", "I", "O"
Deixe seu adivinhe inteligente, o elemento mais certo. Todos os elementos que são menos que O precisam ir para a esquerda e todos os elementos maiores que O têm que ir para a direita, lendo para os dois casos da esquerda. Isto dá:

"E", "i", "o",

sem elemento à direita. Se "e", "i" também for recursivamente dividido, então ["e", "i", ] resultará. E assim a primeira sub-lista esquerda classificada é:

"E", "I", "O"

Dividindo "Q", "W", "R", "T", "Y", "U"
"Q", "W", "R", "T", "Y", "U" é a primeira sub-lista direita. Deixe seu pivô inteligente adivinhar, seja você, o elemento mais certo. Todos os elementos que são menos do que você precisam ir para a esquerda e todos os elementos maiores do que você tem que ir para a direita; lendo para os dois casos, da esquerda. Isto dá:

"Q", "r", "t", "u", "w", "t"

Ao particionar recursivamente "q", "r", "t" e "w", "t" da mesma maneira, a primeira sub-lista direita seria:

"Q", "R", "T", "U", "W", "Y"

E a lista de classificação completa seria:

E i o p q r t u w y

Observe que cada partição se classifica em um sentido amplo, colocando valores mais baixos não classificados na esquerda e valores mais altos não classificados à direita.

Além disso, observe que o palpite inteligente estava apenas escolhendo o elemento mais certo de uma sub-lista. Esse não é o melhor palpite inteligente. Por outro lado, a solução (para adivinhação inteligente) não é escanear toda a lista dada! - Veja abaixo para obter melhores opções.

Código de classificação rápido em c

Embora o valor mais à direita tenha sido escolhido para cada sub-lista acima, convencionalmente, é o valor mais esquerdo que é escolhido. Mesmo quando um palpite mais inteligente é feito, o bom valor adivinhado terá que ser colocado na posição mais à esquerda; e o valor esquerdo que foi lá será colocado em alguma outra posição apropriada (ainda na lista).

Existem quatro funções C com os nomes, Swap (), Pivot (), Partition () e Quicksort (). quicksort (), a função, é codificado de uma maneira recursiva e chama as outras funções.

A função swap ()
Esta função troca dois elementos de matriz, usando seus índices. Isso é:

Void Swap (char a [], int m, int n)
char temp = a [m];
A [m] = a [n];
A [n] = temp;

Uma função simples de pivô ()
Esta função escolhe entre o elemento mais esquerdo e o elemento mais à direita da lista inteira dada. Ele coloca o menor de qualquer posição na posição mais à esquerda e maior na posição mais à direita. Isso é:

Void Pivot (char a [], int esquerda, int à direita)
if (a [esquerda]> a [direita])
trocar (A, esquerda, direita);

Isso é melhor do que apenas escolher o elemento mais certo para a lista e sub-listas, como feito acima. Uma função pivot ainda melhor é dada abaixo.

Uma função partition ()
Assim como a função pivot () pode ser escrita de maneiras diferentes, a função partition () pode ser escrita de maneiras diferentes. O escolhido para este artigo é:

int partitio (char a [], int esquerdista, int direito)
int pivot = a [esquerda];
int i = esquerda;
int j = direita + 1;
fazer
do ++ i;
enquanto (a [i] pivô);
se eu < j)
trocar (a, i, j);
enquanto eu < j);
trocar (a, j, à esquerda);
retornar j;

Depois de colocar o elemento pivô na posição mais à esquerda da lista ou sub-lista, pela função pivot (), a função de partição verifica a lista ou a sub-lista de ambas as extremidades, trocando os elementos que não estão no lado correto do pivô. A varredura da extremidade esquerda começa após o pivô da extremidade mais esquerda (da lista ou da sub-lista); Porque o pivô será trocado por último ("Do ++ i;" acima).

O índice de retorno, J, é a nova (próxima) posição de pivô.

A função Quicksort ()
Esta é uma função recursiva que chama as outras funções. Isso é:

Void Quicksort (char a [], int esquerda, int à direita)
se (esquerda < right)
pivô (a, esquerda, direita);
int k = partição (a, esquerda, direita);
Quicksort (A, esquerda, K-1);
Quicksort (A, K+1, à direita);

Aqui, k é o mesmo que J retornou acima.

Todas as funções acima codificadas juntas, na ordem descrita, formarão o programa Quicksort.

A função C principal C

Uma função principal C adequada para testar o programa é:

int main (int argc, char ** argv)

char a [] = "Q", "W", "E", "R", "T", "Y", "U", "I", "O", "P";
int sz = sizeof (a)/sizeof (a [0]);
Quicksort (A, 0, SZ-1);
para (int i = 0; iprintf ("%c", a [i]);
printf ("\ n");
retornar 0;

A função Quicksort () é chamada da função C principal C, passando a matriz como o primeiro argumento. O segundo argumento que resta é um índice, 0, de toda a lista. O terceiro argumento, certo, é o último índice, mas um de toda a lista.

Pivô mediano

Se três números diferentes forem organizados em ordem ascendente, a mediana é o valor médio (segundo). Uma maneira melhor do que a anterior, para obter o pivô, é procurar a mediana, entre o valor mais à esquerda, o valor médio da lista ou sub-lista e o valor mais à direita. O código é:

int midIndex = (esquerda + direita) / 2; // Número inteiro tomado
If (um [MidIndex] < A[left])
trocar (A, esquerda, Midindex);
se (um [direito] < A[left])
trocar (A, esquerda, direita);
If (um [MidIndex] < A[right])
trocar (A, Midindex, à direita);
char pivot = a [direita];

Observe que os três elementos podem ter mudado de posição. Este código é combinado com a função Pivot () acima de ter:

Void Pivot (char a [], int esquerda, int à direita)
// obtendo a mediana
int midIndex = (esquerda + direita) / 2; // Número inteiro tomado
If (um [MidIndex] < A[left])
trocar (A, esquerda, Midindex);
se (um [direito] < A[left])
trocar (A, esquerda, direita);
If (um [MidIndex] pivô)
trocar (A, esquerda, direita); // caso contrário, um [esquerda] é o pivô

Observe a última condição se.

Conclusão

Quick-Sort é um algoritmo de divisão e conquista de classificação. Continua dividindo (particionando) a lista em três sub-listas recursivamente. A sub-lista do meio sempre consiste em um elemento, que é o pivô. Ao fazer o pivô, a classificação é feita em um sentido amplo nesse estágio. No entanto, à medida que a recursão continua, a classificação perfeita é obtida no final do programa.