Please enable JavaScript.

Coggle requires JavaScript to display documents.

QUICKSORT - Coggle Diagram

- - - - Scanners se cruzam
        
        Troca entre A[ j ] e o pivot
        
        Duas sublistas formadas
        
        Repetição do algoritmo para as sublistas
        
        Após a parada final dos scanners, a troca entre o pivot e o elemento apontado por j usualmente garante que o pivot estará em sua posição final
        
        Formam-se finalmente duas sublistas à esquerda e à direita do pivot, onde a sublista da esquerda contém apenas elementos menores ou iguais e a da direita apenas elementos maiores ou iguais
        
        Varredura do scanner termina quando j < i ou quando j = i (no segundo caso, ambos apontam pra um elemento igual ao pivot)
        
        Pode ocorrer de j ter parado no primeiro elemento que encontrou enquanto i continuou até cruzar com j
        
        Nesse caso, há a possibilidade de i sair do escopo do array no caso onde todos os elementos da sublistas são menores que o pivot
        
        Se o pivot é o primeiro elemento da esquerda, isto ocorre notoriamente quando a lista já está ordenada
        
        Pode ser solucionado pela criação de um elemento sentinela ao final do array ou por uma escolha mais sofisticada do pivot
      - i parte da esquerda pra direita (começando de l e aumentando) e para ao encontrar elementos maiores ou iguais ao pivot
      - Funciona baseado em "paradas", onde os inteiros i e j param de mudar ao encontrarem uma condição desejada no elemento atual
        
        A operação de troca só é feita quando ambos os índices estão parados
      - j parte da direita pra esquerda (començando de r e diminuindo) e para ao encontrar elementos menores ou iguais ao pivot
      - Quando ambos j e i pararam, é feita uma troca entre os valores de A[ i ] e A[ j ]
    - - A lista ou sublista atualmente está delimitada na esquerda pelo índice l e na direita pelo índice r, portanto escolhe-se o elemento A[ l ] como pivot