Please enable JavaScript.

Coggle requires JavaScript to display documents.

QUICKSORT - Coggle Diagram

- - - - Ordenar os elementos dos subarrays da esquerda e da direita de forma independente
  - - - Ex: escolher o primeiro elemento do subarray
        
        Escanear os subarrays a partir de ambas as pontas
        
        Scan da esquerda para a direita
        
        Índice \(i\)
        
        Começa no segundo elemento, pois o primeiro é o pivô
        
        Pula os elementos que são menores que o pivô
        
        1 more item...
        
        Scan da direita para a esquerda
        
        Índice \(j\)
        
        Começa no último elemento
        
        Pula os elementos que são maiores que o pivô
        
        1 more item...
        
        3 situações
        
        Os índices do scan não se cruzaram, ou seja, \(i < j\)
        
        Trocar de lugar os elementos de índices \(i\) e \(j\) e voltar a escanear
        
        Os índices se cruzaram, ou seja, \(i > j\)
        
        Trocar de lugar o pivô e o elemento de índice \(j\)
        
        O subarray terá sido particionado
        
        Combinando
        
        Trocar o pivô com o elemento de índice \(j\) quando \(i \ge j\)
        
        Os índices pararam apontando para o mesmo elemento, ou seja, \(i = j\)
        
        O valor para o qual eles estão apontando é igual ao pivô
        
        Trocar de lugar o pivô e o elemento de índice \(j\)
        
        1 more item...
  - - - \(n\) se os índices coincidem
      - \(n+1\) se os índices do scan se cruzam
    - - Todas as divisões acontecem no meio dos subarrays correspondentes
        
        Recorrência
        
        \(C_{best}\left(n\right)=2C_{best}\left(n/2\right)+n\) para \(n>1\), \(C_{best}\left(1\right)=0\)
        
        Pelo Teorema Mestre, \(C_{best}(n)\in \Theta(n\log_2n)\)
    - - Um dos subarrays fica vazio enquanto que o tamanho do outro será apenas 1 a menos que o tamanho do subarray que está sendo particionado
        
        Ex: Para arrays estritamente crescentes, ou seja, que já estão ordenados
        
        Se \(A[0...n-1]\) for um array ordenado de forma crescente e \(A[0]\) for o pivô
        
        O scan da esquerda para a direita para em \(A[1]\), enquanto que o da direita para a esquerda irá percorrer todo o array até parar em \(A[0]\), indicando a divisão na posição \(0\)
        
        Depois de fazer \(n+1\) comparações e trocar o pivô \(A[0]\) consigo mesmo, o algoritmo terá que ordenar o subarray \(A[1...n-1]\)
        
        O algoritmo repete essa situação até que \(A[n-2...n-1]\), que é o último subarray, seja processado
        
        1 more item...
    - - Número de comparações feita pelo algoritmo para um array de tamanho \(n\) ordenado aleatoriamente
        
        \(n+1\) comparações são feitas para produzir a partição
        
        Um subarray terá \(s\) elementos e o outro, terá \(n-1-s\)
        
        Assumindo que a partição pode acontecer em qualquer posição com a mesma probabilidade de \(1/n\), o número de comparações será, aproximadamente \(1.39n\log_2n\)
        
        Na média, o quicksort realiza \(39%\) mais comparações que o melhor caso