Quicksort: Escolhendo o pivot

StackOverflow https://stackoverflow.com/questions/164163

Pergunta

Ao implementar Quicksort, uma das coisas que você tem que fazer é escolher um pivô. Mas quando eu olho para pseudocódigo como a abaixo, não está claro como eu deveria escolher o pivô. Primeiro elemento da lista? Outra coisa? 

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Alguém pode me ajudar a entender o conceito de escolher um pivô e se ou não diferentes cenários exigem estratégias diferentes.

Foi útil?

Solução

A escolha de um pivot aleatória minimiza a chance que você vai encontrar de pior caso O (n 2 ) desempenho (escolhendo sempre primeiro ou último causaria desempenho pior caso para quase-ordenadas ou quase-reverse dados -sorted). Escolher o elemento do meio também seria aceitável na maioria dos casos.

Além disso, se você estiver implementando isso sozinho, existem versões do algoritmo que o trabalho no local (ou seja, sem a criação de duas novas listas e, em seguida, concatenando-los).

Outras dicas

Depende de suas necessidades. Escolhendo um pivô em marcas aleatórias mais difícil criar um conjunto de dados que gera O desempenho (n ^ 2). 'Median-de-três' (primeiro, último, no meio) é também uma forma de evitar problemas. Cuidado com o desempenho relativo de comparações, embora; se suas comparações são caros, então Mo3 faz mais comparações do que escolher (um valor único pivot) de forma aleatória. registros de banco de dados pode ser caro para comparar.

Update:. Puxando comentários em resposta

mdkess afirmou:

'mediana de 3' não é o primeiro último meio. Escolha três índices aleatórios, e tomar o valor médio deste. A questão toda é para se certificar de que sua escolha de pivôs não é determinista -. Se for, piores dados de casos pode ser facilmente gerado

Ao que eu respondi:

  • Análise de Find de Hoare Algoritmo Com Median-Of partição -três (1997) por P Kirschenhofer, H Prodinger, C Martínez suporta a sua contenção (que 'mediana-de-três' é de três itens aleatórios).

  • Há um artigo descrito em portal .acm.org que é sobre 'o pior caso Permutation para Median-de-três Quicksort' por Hannu Erkiö, publicado no The Computer Journal, Vol 27, no 3, 1984. [Update 2012-02-26: tem o texto para o artigo . Seção 2 'The Algorithm' começa: ' Usando a mediana das primeiras, médio e último elementos de A [L: R], divisórias eficientes em partes de tamanhos bastante iguais pode ser alcançado na maioria das situações práticas ' Assim, é discutir a abordagem Mo3 primeira meia-passado.]

  • Outro pequeno artigo que é interessante é por MD McIlroy, "A Killer adversário para Quicksort ", publicado em Software-prática e experiência, Vol. 29 (0), 1-4 (0 1999). Ele explica como fazer quase qualquer Quicksort se comportar de forma quadrática.

  • AT & T Bell Labs Tech Journal, Out 1984 "Teoria e Prática na construção de um Trabalho Classificar rotina" estados "Hoare sugeriu particionar em torno da mediana das várias linhas selecionadas aleatoriamente. Sedgewick [...] recomendado escolher o mediana do primeiro [...] última [...] e do meio". Isto indica que ambas as técnicas para 'mediana-de-três' são conhecidos na literatura. (Atualização 2014/11/23: O artigo parece estar disponível em IEEE Xplore ou de Wiley -. Se você tem membros ou estão dispostos a pagar uma taxa)

  • 'Engenharia de Ordenar Função' por JL Bentley e MD McIlroy, publicado em Software Prática e Experiência, Vol 23 (11), novembro de 1993, vai para uma ampla discussão das questões, e eles escolheram um algoritmo de particionamento adaptativo baseado em parte do tamanho dos dados conjunto. Há muita discussão de trade-offs para várias abordagens.

  • uma pesquisa no Google para 'mediana-de-três' funciona muito bem para posterior monitoramento.

Obrigado pela informação; Eu só tinha encontrado o determinista 'média-de-três' antes.

Heh, eu só ensinou esta classe.

Existem várias opções.
Simples: Escolha o primeiro ou o último elemento da gama. (Mau na entrada parcialmente ordenado) Melhor: Escolha o item no meio da faixa. (Entrada de melhor em parcialmente ordenado)

No entanto, escolhendo qualquer elemento arbitrário corre o risco de mal particionamento da matriz de tamanho n em duas matrizes de tamanho 1 e n-1. Se você fizer isso com bastante frequência, o quicksort corre o risco de se tornar O (n ^ 2).

Uma melhoria que eu vi é pegar mediana (primeiro, último, médio); Na pior das hipóteses, ele ainda pode ir para O (n ^ 2), mas probabilisticamente, este é um caso raro.

Para a maioria dos dados, escolher a primeira ou a última é suficiente. Mas, se você achar que você está correndo para os piores cenários, muitas vezes (entrada parcialmente ordenados), a primeira opção seria a de escolher o valor central (que é uma estatística boa pivot para dados parcialmente ordenados).

Se você ainda está correndo em problemas, em seguida, ir a rota mediano.

Nunca escolher um pivô fixo - este pode ser atacado de explorar do seu algoritmo de pior caso O (n ^ 2) tempo de execução, que é apenas a pedir sarilhos. do tempo de execução de Quicksort pior caso ocorre quando o particionamento resultados em uma matriz de um elemento, e um conjunto de n-1 elementos. Suponha que você escolher o primeiro elemento como sua partição. Se alguém alimenta um array para o seu algoritmo que é em ordem decrescente, o seu primeiro pivô será o maior, então tudo o resto na matriz irá se mover para a esquerda dele. Então, quando você recurse, o primeiro elemento será o maior de novo, então uma vez mais você colocar tudo para a esquerda dele, e assim por diante.

A melhor técnica é o método média-of-3, onde você escolhe três elementos de forma aleatória, e escolher o meio. Você sabe que o elemento que você escolher não vai ser o primeiro ou o último, mas também, pelo teorema do limite central, a distribuição do elemento do meio será normal, o que significa que você tenderá para o meio (e, portanto, , n lg n tempo).

Se você realmente quiser garantir O (NLGN) tempo de execução para o algoritmo, o método colunas-of-5 para encontrar a mediana de uma matriz é executado em O (n), o que significa que a equação de recorrência para quicksort na pior caso será T (n) = o (n) (encontrar a mediana) + o (n) (partição) + 2T (n / 2) (recurse esquerda e direita.) Pelo Teorema Mestre, este é o (n lg n). No entanto, o fator constante será enorme, e se pior desempenho caso é a sua principal preocupação, use um merge sort em vez disso, que é apenas um pouco mais lento do que quicksort em média, e garantias O (NLGN) tempo (e será muito mais rápido do que isso quicksort coxo mediana).

Explicação da mediana das medianas Algoritmo

Não tente ficar muito inteligente e combinar estratégias articuladas. Se você combinou média de 3 com pivot aleatória escolhendo a mediana da primeira, última e uma aleatória índice no meio, então você ainda estará vulnerável a muitas das distribuições que enviam média de 3 quadrático (pelo que a sua realmente pior do que pivot aleatória simples)

Por exemplo, um órgão de distribuição de tubo (1,2,3 ... N / 2..3,2,1) primeira e última vontade tanto ser um e o índice aleatório será algum número maior do que 1, tendo a mediana dá 1 ( o primeiro ou o último) e você terá uma partição extermely desequilibrado.

É inteiramente dependente da forma como os seus dados são ordenados para começar. Se você acha que vai ser pseudo-aleatório, em seguida, sua melhor aposta, quer seja para escolher uma seleção aleatória ou escolher o meio.

Se você está classificando um conjunto aleatório acessível (como um array), é em geral melhor para escolher o item do meio físico. Com isso, se a matriz está tudo pronto classificadas (ou quase classificadas), as duas partições será perto mesmo, e você vai ter a melhor velocidade.

Se você está classificando algo com apenas o acesso linear (como uma lista ligada), então é melhor escolher o primeiro item, porque é o item mais rápida de acesso. Aqui, no entanto, se a lista já está classificado, você está ferrado -. Uma partição será sempre nula, eo outro tem tudo, produzindo o pior momento

No entanto, para uma lista ligada, pegando qualquer coisa além da primeira, só vai piorar a situação. Ele escolhe o item do meio em uma lista na lista, você teria que passo por ele em cada etapa partição - adicionando uma operação O (N / 2), que é feito vezes logN fazendo tempo total de O (1,5 N * log N) e isso é se sabemos quanto tempo a lista é, antes de começar - geralmente nós não, então teríamos para o passo todo o caminho através de contá-las, em seguida, passo a meio de encontrar o meio, então passo através de um terceira vez para fazer a partição real: o (2,5 N * N log N)

É mais fácil quebrar o quicksort em três seções fazer isso

  1. função Exchange ou elemento de dados de swap
  2. A função de partição
  3. Processamento as partições

É apenas um pouco mais ineficiente do que uma função muito tempo, mas é muito mais fácil de entender.

código a seguir: 

/* This selects what the data type in the array to be sorted is */

#define DATATYPE long

/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */

void swap (DATATYPE *x, DATATYPE *y){  
  DATATYPE Temp;

  Temp = *x;        // Hold current x value
  *x = *y;          // Transfer y to x
  *y = Temp;        // Set y to the held old x value
};


/* This is the partition code */

int partition (DATATYPE list[], int l, int h){

  int i;
  int p;          // pivot element index
  int firsthigh;  // divider position for pivot element

  // Random pivot example shown for median   p = (l+h)/2 would be used
  p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point

  swap(&list[p], &list[h]);                   // Swap the values
  firsthigh = l;                                  // Hold first high value
  for (i = l; i < h; i++)
    if(list[i] < list[h]) {                 // Value at i is less than h
      swap(&list[i], &list[firsthigh]);   // So swap the value
      firsthigh++;                        // Incement first high
    }
  swap(&list[h], &list[firsthigh]);           // Swap h and first high values
  return(firsthigh);                          // Return first high
};



/* Finally the body sort */

void quicksort(DATATYPE list[], int l, int h){

  int p;                                      // index of partition 
  if ((h - l) > 0) {
    p = partition(list, l, h);              // Partition list 
    quicksort(list, l, p - 1);        // Sort lower partion
    quicksort(list, p + 1, h);              // Sort upper partition
  };
};

O ideal seria o pivô deve ser o valor médio em toda a matriz. Isso irá reduzir as chances de ficar pior desempenho caso.

complexidade do tipo Breve varia muito com a seleção de valor pivô. por exemplo, se você sempre escolher primeiro elemento como um pivô, a complexidade do algoritmo torna-se tão pior como O (n ^ 2). aqui é um método inteligente para escolher pivot element- 1. Escolha o primeiro, meio, último elemento do array. 2. comparar estas três números e encontrar o número que é maior do que um e menor do que o outro ou seja mediana. 3. fazer este elemento como elemento pivô.

escolher o pivô por este método divide a matriz em quase duas meia e, portanto, a complexidade reduz a O (nlog (n)).

Em média, mediana de 3 é bom para a pequena n. A mediana de cinco é um pouco melhor para n maior. O ninther, que é a "média de três medianas de três" é ainda melhor para muito grande n.

Quanto maior você vai com a amostragem do melhor que você começa quando n aumenta, mas a melhora dramaticamente diminui à medida que aumenta as amostras. E você provoca a sobrecarga de amostragem e triagem de amostras.

Eu recomendo usar o índice de média, como pode ser facilmente calculado.

Você pode calcular-lo por arredondamento (array.length / 2).

Em uma implementação verdadeiramente otimizado, o método para a escolha de pivot deve depender do tamanho da matriz - para uma grande variedade, vale a pena gastar mais tempo escolhendo um bom pivô. Sem fazer uma análise completa, eu acho "meio de O (log (n)) elementos" é um bom começo, e isso tem a vantagem adicional de não requerer qualquer memória extra: Usando tail-call sobre a maior partição e in- lugar de particionamento, usamos o mesmo o (log (n)) de memória extra em quase todas as fases do algoritmo.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top