Please enable JavaScript.

Coggle requires JavaScript to display documents.

Quicksort - Coggle Diagram

- - - - O elemento divisória vai ter o valor de A0, mas sua posição vai mudar de acordo com a implicação:
        
        Se todos os elementos a esquerda de A[k] forem menores ou iguais ao futuro divisória (até então A[0]) e todos elementos a direita de A[k] forem maiores ou iguais ao futuro divisória, então o A[0] vai para a posição A[k]
        
        O que foi chamado de A[k] na verdade é uma posição dividida, pois na teoria o A[k] fica entre duas posições (entre um menor que o A[l] (chamado de A[i]) e um maior (chamado de A[j]), então o que o algoritmo faz é trocar a posições A[l] e A[i]
        
        Sabendo que o que foi chamado de A[0] na verdade vai ser o A[l] onde l é a primeira posição do sub array
- - - - A assinatura seria mais ou menos assim: quickSort(int[n]A,l,r)
    - - Uma checagem para garantir que a posição do começo vem antes do final, mas também uma condição de parada para a recurção
      - s (variável int) recebe Partition(A[l..r])
        
        O Partition(A[l..r]) vai fazer grande parte do(se não todo o) trabalho, ele vai organizar o (sub)array de forma que o elemento que inicialmente estava em A[l] fique numa posição em que todos a sua direita são maiores que ele e todos a sua esquerda são menores
        
        O Partition vai retornar o valor da posição do pivô (que é o antigo A[l])
        
        Aplique Quicksort(A[n], l, s - 1) e Quicksort(A[n], s + 1, r)
        
        Recursivamente cada subarray de A vai ficar ordenado
        
        Array Ordendo
- - - - Atribua A[l] a p(variável do tipo dos elementos de A)
        
        i recebe l e j recebe r+1
        
        Repita esses processos:
        
        Repita esse processo
        
        Incremente i
        
        Até A[i] >= p
        
        Repita esse processo
        
        Decremente j
        
        Até A[j ]<= p
        
        Troque as posições de A[i] e A[j]
        
        Até i >= j
        
        Troque as posições de A[i] e A[j] (desfazendo a ultima troca, quando i >= j)
        
        Troque as posições de A[l] e A[j]
        
        1 more item...