Please enable JavaScript.

Coggle requires JavaScript to display documents.

Quicksort, Radix Sort, Binsort - Coggle Diagram

- - - - Se o index do início encontrar um elemento maior que o pivot, ele para
        
        Se o index do fim encontrar um elemento menor ou igual ao pivot ele para
        
        À direita do pivot, só deveria haver elementos maiores. Então o elemento encontrado é marcado para ser movido
        
        Quando os dois indexes estiverem parados, três situações podem ter acontecido
        
        Os indexes se encontraram
        
        Os dois indexes pararam apontando para um mesmo elemento
        
        O elemento onde pararam tem o mesmo valor que o pivot. Essa é outra situação que marca o fim da formação de uma partição
        
        Os indexes se cruzaram
        
        O index do início parou em elemento depois do index do fim
        
        Isso marca o fim da formação da particção. Todos os elementos à esquerda da array são menores ou iguais ao pivot, e todos à direita são maiores
        
        Os indexes não se cruzaram nem se encontraram
        
        Nenhuma das outras situações citadas ocorreu
        
        Essa é a situação padrão ao longo da formação da partição e significa que dois elementos foram encontrados em regiões onde não deveriam estar
        
        2 more items...
        
        À esquerda do pivot, só deveria haver elementos não maiores. Então o elemento encontrado é marcado para ser movido
- - - - Depois, os itens são ordenados usando o dígito mais à direita como chave
        
        E segue-se comparando até o dígito mais à esquerda
        
        Após a primeira ordenacão, os itens são ordenados na array original de acordo com a array auxiliar
        
        Após os itens serem ordenados com base no primeiro digito, o processo se repete realizando comparações com o segundo dígito mais à direita
        
        Se necessário, isso acontece de novo para um terceiro e quarto dígitos. Até que seja alcançado o último dígito do elemento de mais dígitos
        
        Para números com quantidade de dígitos menores, é considerado que seus dígitos mais à esquerda são 0
        
        Os itens são copiados em uma array de arrays em registros de posições iguais ao primeiro dígito
      - Essa primeira iteração pela array a ser ordenada serve para determinar quantos bins são necessários para os elementos
        
        Sabendo quantas bins são necessárias, é possível contornar o overhead de instanciar múltiplas listas ligadas
- - - - No melhor caso, ela fica na classe ômega nlog(n)
        
        Esse, porém, é o melhor caso. A eficiência decai à medida que o alcance das chaves aumenta
        
        Mas, estranhamente, a eficiência volta a melhorar para alcances maiores
        
        O Radix Sort se torna realmente eficiente quando número de bins for grande em comparação com o tamanho das chaves
- - - - Apesar do uso das bins garantir boa eficiência temporal, também proporciona limitações, como a incapacidade de lidar com múltiplas ocorrências de um valor
        
        Essas limitações, porém, podem ser contornadas através de extensões
        
        O problemas da repetição de um valor por exemplo, pode ser resolvido transformando a array auxiliar em uma array de listas ligadas
        
        Assim, cada bin pode guardar quantas ocorrências de um valor quanto aparecem na array original
        
        Outra extensão permite aumentar o alcance dos valores possíveis inicializando uma lista auxiliar com um tamanho diferente da array original
        
        Assim, os elementos da array original podem ter valores entre 0 e o tamanho da array auxiliar - 1
        
        1 more item...
      - Uma generalização do Binsort envolve algo chamado bucket sort
        
        Nessa generalização, ao invés de uma bin guardar ocorrências de um valor, ela guarda intervalos de valores
        
        ex.: Se os valores da array a ordenar variarem de 0 a 99, a auxiliar poderia ter 10 bins em que o bin 0 contém valores de 0 a 9, o 1, valores de 10 a 19, e assim em diante
        
        Para organizar ainda mais esses bins, é possível guardá-los em listas da array auxilar a depender do valor de seu dígito mais à direita e então organizá-los nessa lista a partir do dígito seguinte
        
        Aqui, entramos no território da Radix Sort