Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Ordenação
(Sorting), O(n^2), O(n.log n), Algoritmo Misto,…
-
-
-
Algoritmo Misto
Mistura algoritmos dos dois tipos, O(n^2) e O(nlogn), de modo a gerar algoritmos mais eficientes para determinadas situações
-
-
Bubble Sort
O bubble trabalha, basicamente, com a ideia de percorrer o input uma vez para cada par que pode ser formado dentre os elementos do input . A cada percurso, o algoritmo traz o maior elemento para o topo da lista.
complexidade baixa, estável, o espaço de memória necessário é do tamanho do input.
Insertion Sort
Divide o input em uma parte "organizada" e outra "desorganizada". De início, a parte organizada tem tamanho um, mas, o algoritmo vai inserindo os itens um por um em seus respectivos lugares, até a parte organizada ter tamanho n
-
Selection Sort
Também divide o input em uma parte organizada e outra desorganizada, mas, em adição à isso, ele também fica achando o menor item da lista e movendo-o para o início.
Excelente para inputs pequenos, tido como o melhor dentre os sorting algorithms de ordem O(n^2)
Merge Sort
Primeiro, separa o input em mini listas de 2 elementos. Depois ordena todas essas mini listas. Junta essas mini listas aos pares e ordena os elementos dessa junção. Repete esse processo até sobrar uma única lista de tamanho n.
Estável, porém necessita de mais espaço
Quicksort
-
Pega um elemento da lista , chamado de pivot e divide o input em duas listas de elementos maiores que o pivot e menores que o pivot, Repete esse processo nas listas, de novo e de novo, até só sobrar uma única lista, completamente ordenada.
Heap Sort
Organiza todos os elementos numa árvore, chamada de heap, e vai fazendo comparações até essa árvore estar ordenada por completo. Depois disso, é só ir tirando os elementos da raiz da árvore, gerando uma lista totalmente ordenada
Não precisa de espaço extra, bom tempo de desempenho, não éestável.
-
-
input = { a, b, c... n}
int i, j, aux
for i=0;i<len(input);i++
for j=i+1;j<len(input);j++
if(input[j]<input[i]) {
aux =input[j]
input[j] = input[i]
input[i] = aux
-
São classificados de acordo com a quantidade de operações feitas para organizar os elementos em sequência