Please enable JavaScript.

Coggle requires JavaScript to display documents.

ALGORITMOS DE ORDENÇÃO, QUICKSORT, SHELL SORT, ALGORITMOS DE ORDENAÇÃO…

- - - - Eficiência com big O de (n²)
        
        A eficiência pode melhorar consideravelmente se especificarmos que o algoritmo deve parar após um varredura sem fazer alterações
- - - - Após encontra-lo, há uma troca de posição, entre o menor item encontrado e o que ocupava o inicio ou fim da lista(depende se é pra ordenar em ordem crescente ou decrescente), o algoritmo varre novamente a lista, agora a partir do segundo item ( a lista tem tamanho de n-1) para repetir a operação.
    - - Ou seja, torna-se muito vantajoso quando os dados em questão são strings longas ou arquivos grandes
  - - - A formula exata para chegar a esta conclusão é
        
        Somatório de i==0 até n-2 na formula (n - 1 + i)
        
        QUE RESULTA EM:
        
        (n - 1) n / 2
      - A operação básica é:
        
        A[j] < A[min]
        
        Em que A[j] representa o termo atual que será comparado e A[min] é o menor termo encontrado na lista durante aquela varredura.
      - A operação básica pode se repetir até (n -1) vezes para cada n. Isto é, no pior dos casos
- - - - Em caso de uma ordenação crescente
        
        Se o segundo item for menor que o primeiro eles serão trocados
        
        Em seguida o terceiro elemento é comparado com o segundo, se forem menores, serão trocados e este elemento será comparado com o primeiro, e se for menor, serão trocados novamente
        
        Assim cada item adjacente vai ser comparado com os que estão a sua frente e serão inseridos exatamente atrás do primeiro item que não seja menor que eles. E cada idem que passarem terá apenas uma troca de posição
        
        Diferença entre Insertion sort e Selection sort
        
        ENQUANTO
        
        2 more items...
    - - No melhor dos casos tem eficiência big TETA(N)
- - - - No caso de ordenação de uma lista consistiria em dividir a lista ao meio e organizar cada parte separadamente e em seguida mesclar
        
        A parte de mesclar é feita a partir da comparação entre os elementos de cada uma das sublistas.
        
        A principio um ponteiro apontando para o primeiro item de cada uma, uma comparação seria realizada e o menor entre os dois seria adicionado a matriz final
        
        A parte de merge(mesclar) apresenta uma eficiência altissima da ordem logaritmica em um caso médio.
        
        Sua principal desvantagem é o fator de ocupar demasiada memória
        
        Este algoritmo é apresenta uma eficiência superior ao Selection sort e insertion sort
      - A Técnica de dividir para conquistar é muito utilizada na computação
        
        Consiste essencialmente em subdividir o problema em problemas menores que sejam mais simples de resolver de maneira eficiente
        
        De preferencia dividirem problemas do mesmo tamanho, e caso necessário unir as soluções de cada subproblema para resolver o maior
  - - - Assim enquanto o merge sort divide a lista na metade,
- - - - Um destes casos é quando todas as divisões estão vazias exceto uma que contem apenas 1 elemento.
      - No pior dos casos, quando cada divisão de sublistas o pivô é mal estabelecido deixando um nova sublista vazia e outra com todos os elementos, a efiviência do quicksort se torna tão ruim quanto o bubble sort
        
        Porém, esta situação é muito improvável e o Quicksort mesmo com alguns pivôs mal selecionados ainda pode funcionar muito bem.
  - - - E quando a matriz é muito grande mas ja foi subdividida em arrays menores de pouco elementos(9 ou menos) não é preciso continuar organizando eles, pois ja estão em um nivel de ordem bastante aceitavel.
        
        O que será feito é que ao fim da execução do Quicksort, será utilizado o insertion sort, para organizar os poucos elementos que ainda não chegaram ao seu devido lugar.
        
        Fazendo assim com que o insertion sort lide apenas com pequenas listas pouco desorganizadas.
- - - - Então utiliza-se um função para definir o pivô
        
        template <typename E>nline int findpivot (E A[], int i, int j) { return (i+j)/2; }
        
        Uma escolha tambem interessante e utilizar a mediana de três, utilizando o valor A[0], A[n/2] e A[n]
- - - - O critério para definir o pivô será:
        
        Um valor será estabelecido como divisor, os valores que o escolhido maiores ficarão em um sub array a direita, jáo valores menores ficarão em um subarray a esquerda
        
        Cada subarray é ordenado e não haverá um momento para mesclar os arrays como com o mergesort
- - - - Após organizar as listas mínimas junta com outras um pouco maiores, e as organiza tambematraves do selection sort ou insertion sort, isto otimiza o algoritmo.