Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmos de sort - Coggle Diagram

- - - - A solução se baseia em verificar todos os valores do array e encontrar o menor valor (ou maior, depende de como o programador quer) e colocar ele na primeira posição. Depois, procura o menor valor de novo (esquece do valor que ja foi organizado) e coloca ele na posição depois do primeiro. Esse processo é repetido até o array estar organizado
      - O selection sort tem eficiencia de big-theta(n²) para todas as entradas
    - - A solução se baseia em fazer uma verificação entre dois termos em sequencia (ex.: 0 e 1, 1 e 2, 2 e 3 e etc) até o fim do array, dessa forma, o ultima posição será o maior ou menor termo (escolha do programador). O processo é repetido e o penultimo termo é colocado e o algoritmo acaba quando o array estiver organizado
      - O bubble sort tem eficiencia de big-theta(n²) para todas as entradas
- - - - 1 - Reduzir o problema em subproblemas do mesmo tipo(normalmente de tamanho igual), mas menores que o original
      - 2 - Resolver os subproblemas (normalmente por recursão ou por outra função)
      - 3 - Juntar os subproblemas (se precisar) e receber a resposta do problema original
  - - - Consiste em dividir um array em duas partes (de preferencia iguais) até chegar em um ponto que o array seja unitario. Então, analisar entre os array unicos que foram originados de um mesmo pai qual é o menor ou maior (de acordo com o desejo do programador) e criar um novo array com os numeros organizados. Repete o processo até o array do mesmo tamanho do original ser gerado e esse estará organizado
      - O mergesort tem eficiencia de omega(n log n) para todos os tamanhos de entradas
    - - Consiste em escolher um numero como pivô e dizer em qual posição ele estará no final do sort. Depois, fazer novamente o quicksort nos dois novos arrays (o da esquerda do pivo e o da direita) de forma recursiva. Até o ponto onde teremos todos os indices do array e quem ocupa cada lugar. Nesse momento, agrupamos tudo de novo no array original e temos a solução
      - O mergesort tem eficiencia de omega(n²) para o pior caso e para o melhor e caso médio, tem eficiencia de O(n log n)
      - Essa forma de sort é EXTREMAMENTE importante de se conhecer. A sua velocidade é muito boa para a maioria dos outros algoritmos do genero (isso muito pelo seu caso médio, que é aproximadamente 1.39 n log n para ser muito preciso, que é muito melhor que outros, como o mergesort). Contudo, devemos lembrar que sua eficiencia espacial não é O(1).
      - Tem diversas formas de se implementar o quicksort, usando duas variaveis para decidir onde será o pivo, apenas uma. Escolher o pivo como o primeiro elemento, ou como o ultimo, ou o meio e etc.
- - - - As 3 formas mais usadas de diminuir e conquistar
        1 - Diminuir por uma constante
        2 - Diminuir por um fator constante
        3 - Diminuir por um valor variavel
  - - - Baseia que parte do array ja esteja organizado (no minimo um array de tamanho um, que sempre esta organizado). Então, recebe o primeiro valor depois da parte organizada do array e compara com os elementos do array antigo, inserindo o novo elemento no local correto, depois, faz o mesmo processo até todo o array estar organizado
      - O insertion sort tem eficiencia de big-theta(n²) para worst case e para average case. Para better case, a eficiencia é big-theta(n)