Please enable JavaScript.
Coggle requires JavaScript to display documents.
Selection Sort and Bubble sort, decrease-and-conquer - Coggle Diagram
-
decrease-and-conquer
Divide-and-conquer
-
A problem is divided into several subproblems of the same type, ideally of
about equal size.
The subproblems are solved (typically recursively, though sometimes a different algorithm is employed, especially when subproblems become small
enough).
If necessary, the solutions to the subproblems are combined to get a solution
to the original problem
-
decrease by a constant
o tamanho de uma instância é reduzido
pela mesma constante em cada iteração do algoritmo. na mairia das vezes a constante é 1
-
-
insertion sort.
examinamos o subarray (resultado da decrease-by-a-constant) classificado da direita para a esquera até o menor ou igual elemento a A[n-1], quando encontrado, inserir A[n-1] logo apos esse elemento.
A técnica é baseada na exploração do relacionamento entra a solução para uma determinada instância de um problema e uma solução para a sua instância menor.