Qual é a maneira mais rápida (pelo menos em teoria) para classificar uma pilha?

Question

A pilha é uma lista onde se aplica o seguinte:

l[i] <= l[2*i] && l[i] <= [2*i+1]

para 0 <= i < len(list)

Eu estou procurando no local de classificação.

Answer 1

Bem, você está a meio caminho através de um Heap Sort já, por ter seus dados em um heap. Você só precisa implementar a segunda parte do algoritmo de heap de ordenação. Este deve ser mais rápido do que usar quicksort na matriz de heap.

Se você estiver se sentindo corajoso, você poderia ter um ir para a implementação smoothsort , que é mais rápido do que heapsort para dados de quase-ordenadas.

Answer 2

Apenas uso heap-sort. É no local. Isso seria a escolha mais natural.

Você pode também apenas usar sua pilha como ele e classificá-lo com algum outro algoritmo. Depois você re-construir a sua pilha a partir da lista de classificação. Quicksort é um bom candidato, porque você pode ter certeza que não será executado no pior caso O (n²) a fim simplesmente porque sua pilha está já pré-classificadas.

Isso pode ser mais rápido se o seu-função de comparação é caro. Heap-sort tendem a avaliar a função comparar com bastante frequência.

Answer 3

Classificando uma espécie de pilha no local de sons como um trabalho para Heap Sort .

Eu assumo a memória é limitada, um aplicativo embutido, talvez?

Answer 4

Uma vez que você já tem uma pilha, você não poderia usar apenas a segunda fase do tipo pilha ? Ele funciona no lugar e deve ser agradável e eficiente.

Answer 5

Para triagem no local, a maneira mais rápida segue. Cuidado com os erros de off-por-um no meu código. Note-se que este método dá uma lista ordenada invertida que precisa ser não invertida na etapa final. Se você usar um max-pilha, este problema desaparece.

A idéia geral é um puro um: troca o menor elemento (no índice 0) com o último elemento na pilha, bolha esse elemento para baixo até que a propriedade heap é restaurado, encolher o tamanho da pilha por um e de repetição.

Esta não é a maneira mais rápida absoluta para não-in-place classificando como David Mackay demonstra aqui -. você pode fazer melhor, colocando um elemento mais provável que seja o mais pequeno no topo da pilha em vez de um da linha de fundo

complexidade Tempo é T (n.log n) pior caso -. N iterações com possivelmente log n (a altura da pilha) atravessa o while

for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
  {
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
  {
    if (l[i] > l[left])
      {
    swapidx = left;
      }
  }
else
  {
    if (l[i] > l[right])
      {
    swapidx = right;
      }
  }

if (swapidx == i)
  {
    // Found right place in the heap, break.
    break;
  }
swap( l, i, swapidx );
i = swapidx;
  }}

// Now reverse the list in linear time:
int s = 0; 
int e = len(l)-1;
while (e > s)
  {
    swap( l, s, e );
    s++; e--:
  }

Answer 6

Leia os itens fora do topo da pilha um por um. Basicamente o que você tem, então é uma espécie de pilha.