Pergunta sobre sorting, introsort, algorithm – Quando o introsort muda de quicksort para heapsort?

6

Introsort começa com quicksort e alterna para heapsort quando a profundidade de recursão excede um nível com base no número de elementos que estão sendo classificados. Qual é esse número? Existe um intervalo específico ou um valor limite?

Sua resposta

2   a resposta
6

Algoritmo Introsort comutadores de Quicksort para Heapsort é determinado pordepth_limit:

depth_limit = 2 · ⎣log2(l⎦

Ondel é o comprimento da seqüência que deve ser classificada, entãol‍ = ‍n para toda a sequência. Com cada chamada recursivadepth_limit é diminuído por um. Quandodepth_limit atinge 0, muda de Quicksort para Heapsort.

@auto. Bem, dividir ao meio é o melhor caso; no pior caso, a sequência será dividida em (1, N-1). Nesse caso depth_limit atinge 0. Gumbo
Pela sua lógica, o Heapsort nunca acontecerá, pois o limite de profundidade nunca será alcançado. this
@auto. Porque você acha isso? Gumbo
Leia meu comentário abaixo; Outro exemplo: Array de 10000 membros teria um limite de profundidade de (13 * 2), se o array fosse dividido ao meio em cada recursão, então no 14º nível os sub-arrays teriam 0 elementos. this
2

Eu apenas tentei ler o introdutórioArtigo da Wikipédia. Diz

Conta a profundidade da recursão. Se uma profundidade logarítmica for excedida, o algoritmo alterna para o Heapsort do Quicksort para manter o resultado do pior caso do Quicksort

e através do artigo original do Musser no Introsort.

Ele diz que introsort é mais lento que heapsort porque executa cálculos de 2 * log (2, N) antes de alternar para heapsort.

Meu entendimento é que a profundidade de recursão é 2 * log (2, N)

Para N = 300 elementos para classificar, será 2 * 8 = 16

Se estiver usando o limite de profundidade de 16 em um arry de 300 elementos em aproximadamente o 10º nível de profundidade, o subarray terá 0 elementos. this

Perguntas relacionadas