Por que o Quicksort é descrito como "no local" se os sublistas ocupam bastante memória? Certamente, apenas algo como o tipo de bolha está no lugar?

7

O Quicksort é descrito como "no local", mas usando uma implementação como:

def sort(array):
    less = []
    equal = []
    greater = []
    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
        return sort(less) + equal + sort(greater)
    else:
        return array

Você precisa criar uma cópia da lista para cada recursão. No primeiro retorno, na memória, temos:

  • matriz
  • maior + igual + menos

Então, pela segunda recursão em todas as sub-listas, temos:

  • matriz
  • maior, igual, menor desde a primeira recursão
  • maior + igual + menor de menor1, maior + igual + menor de maior1

etc ...

É apenas um código mal escrito ou estou correto ao pensar que, para uma grande lista, você realmente precisa ter, proporcionalmente, uma quantidade razoável de espaço extra para armazenar esses itens?

Quando penso em algo "in-loco", penso na classificação de bolhas, que simplesmente troca elementos da lista como: http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px. gif

O BubbleSort requer apenas 1 variável extra para armazenar um elemento potencialmente trocado.

LittleBobbyTables
fonte
11
Não sei dizer o que você está perguntando. Deseja tentar editar a pergunta para esclarecer qual é a sua pergunta? Você está apenas perguntando se é possível implementar o QuickSort no local? Nesse caso, essa é uma pergunta padrão com uma resposta padrão nos locais habituais - você não fez pesquisas suficientes. PS Além disso, você pode tentar ser mais preciso na sua redação. Por exemplo, não sei dizer o que a primeira frase está dizendo (parece que falta um verbo). Na segunda frase, não sei dizer quem é o "você".
DW
11
No local, você pode evitar o uso de áreas de dados externas, mas somente o array original que você está classificando. Esta implementação não faz isso.
Thorbjørn Ravn Andersen 12/03

Respostas:

21

Essa implementação específica do quicksort não está em vigor. Ele trata a estrutura de dados como uma lista que só pode crescer em uma direção (nesse caso, uma classificação de mesclagem seria mais simples e rápida). No entanto, é possível escrever uma implementação no local do quicksort, e é dessa maneira que geralmente é apresentada.

Em uma implementação no local, a função de classificação não é chamada recursivamente em matrizes recém-construídas que se tornam cada vez menores, mas em limites que se aproximam cada vez mais.

def sort(array, start, end):
    if end >= start: return
    pivot = array[start]
    middle = start + 1
    for i in range(start+1, end):
        if array[i] >= array[middle]:
            tmp = array[i]
            array[i] = array[middle]
            array[middle] = tmp
            middle += 1
    sort(array, start, middle)
    sort(array, middle, end)

(Cuidado com este código, eu apenas o digitei, não o provei. Quaisquer erros pontuais são seus para corrigir. As implementações do mundo real usariam um algoritmo diferente para tamanhos pequenos, mas isso não afeta o comportamento assintótico. Real As implementações do -world escolheriam um pivô melhor, mas não abordarei isso aqui, pois não é realmente para esta pergunta.)

A página da Wikipedia apresenta uma versão não in-loco e in-loco do algoritmo.

O Quicksort, conforme escrito aqui, requer armazenamento extra de , onde é a profundidade da recursão (que depende da qualidade do pivô) é o tamanho do elemento. O requisito de tamanho da pilha pode ser aprimorado: há duas chamadas recursivas e podemos fazer da segunda uma chamada final (que não consome nenhuma pilha). Se sempre fizermos a chamada recursiva na metade menor primeiro, o tamanho máximo da pilha para comprimentos de matriz até satisfaz com , então . Assim, podemos atingir os requisitos de armazenamento extra de , independentemente da opção de pivô.O(d)+sdsnS^(n)S^(m)mn/2S^(n/2)S^(n)lg2(n)S^(1)O(logn)+s

Existem muitos outros algoritmos de classificação que podem ser implementados no local, incluindo classificação de inserção, classificação e seleção de heap. A forma simples de classificação por mesclagem não está no lugar, mas existe uma variante mais sofisticada .

Agradecemos a Aryabhata por apontar que o Quicksort sempre pode ser feito na pilha e que existe uma variante de classificação de mesclagem com armazenamento adicional e tempo de execução .lg(n)O(1)O(nlog(n))

Gilles 'SO- parar de ser mau'
fonte
11
@Gilles: Não. Mesmo que o algoritmo de seleção dinâmica sempre escolha o mínimo, podemos implementar o Quicksort para usar o espaço . (Você pode argumentar que é uma variante do quicksort). A chave é sempre recursar na partição mais curta e recuar na recursão mais longa. O(logn)
Aryabhata 12/03
11
Aliás, acho que a fusão no local com também foi alcançada. akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/04/… afirma uma mesclagem linear no local no tempo. O(nlogn)
Aryabhata 12/03
3

Além da resposta de Gilles, você também pode instalar o Quicksort com seu código, se você usar listas vinculadas em vez de matrizes. Apenas remova o elemento da lista original ao anexá-lo a uma das listas menores.

O seguinte pseudocódigo assume / garante:

  • A primeira entrada em cada lista (a seguir denominada cabeçalho) não olha um elemento e permite manter os ponteiros da lista intactos nas modificações. new listcria uma lista que consiste em uma cabeça com o NILpróximo ponteiro.
  • sortleva um ponteiro para uma cabeça e retorna um ponteiro para o último elemento da lista classificada. O ponteiro fornecido como argumento também é o cabeçalho da lista classificada.
  • A localização da memória de cada elemento e do cabeçalho da lista permanece a mesma.

.

sort(list):
    less_cur = less = new list
    equal_cur = equal = new list
    greater_cur = greater = new list
    if list.next != NIL:
        cur = list.next
        pivot = cur.value
        while cur != NIL:
            list.next = cur.next
            if cur.value < pivot:
                less_cur.next = cur
                less_cur = less_cur.next
            if cur.value == pivot:
                equal_cur.next = cur
                equal_cur = equal_cur.next
            if cur.value > pivot:
                equal_cur.next = cur
                equal_cur = equal_cur.next
            cur = cur.next
        less_cur.next = greater_cur.next = NIL
        less_last = sort(less) 
        list.next = less.next
        less_last.next = equal
        greater_last = sort(greater)
        equal_cur.next = greater.next
        return greater_last
    else:
        return list

Embora exista alguma otimização possível a partir do código acima, esta implementação possui uma sobrecarga de memória maior que a implementação baseada em array na resposta de Gilles. Além disso, sofre na prática do problema de que as listas vinculadas geralmente são menos localizadas e, portanto, induzem um número maior de falhas de cache do que a manutenção dos mesmos dados em uma matriz.

No entanto, essa implementação é vantajosa, se você precisar manter ponteiros para os elementos através da classificação. Também é bom estar ciente disso, se você estiver armazenando seus dados em uma lista vinculada por motivos não relacionados à classificação. (Se o local da classificação é motivo de preocupação, a conversão entre lista e matriz provavelmente está fora de questão.)

FrankW
fonte
Isso considera "no local" como "não ter que copiar os elementos", mas, por sua vez, trabalha muito com todas as listas apontando para os elementos. Eu consideraria o uso de todas estas estruturas de dados auxiliares (todos acabar como lixo que precisam ser recolhidos) como não sendo totalmente "in-place"
Thorbjørn Ravn Andersen
@ Thorbjørn Você pode remover a lista original e anexá-la à lista menor alterando 2 ponteiros (4 para listas duplamente vinculadas). Não vejo onde isso gera lixo.
FrankW
Talvez você deva mostrar uma implementação do que sugere para garantir que estamos discutindo a mesma coisa.
Thorbjørn Ravn Andersen 12/03
@ ThorbjørnRavnAndersen Um em Common Lisp é o truque dos carneiros do Pitmanual . Ele não está "no lugar", pois o nó da lista que era o início original da lista pode não estar depois, mas não requer armazenamento adicional. O particionamento modifica destrutivamente a estrutura da lista para que as sublistas sejam construídas a partir dos mesmos nós da lista original. Obviamente, isso requer a capacidade de modificar a estrutura da lista, que algumas implementações (por exemplo, a interface de lista do Java) não fornecem.
21414 Joshua Taylor #:
@FrankW Eu não acho correto chamar isso de "no lugar" tanto quanto "sem armazenamento adicional". Um nó da lista na posição i antes da classificação da lista pode não estar na posição i posteriormente.
Joshua Taylor