Please enable JavaScript.
Coggle requires JavaScript to display documents.
MERGESORT - Coggle Diagram
MERGESORT
-
-
A técnica decrease-and-conquer baseia-se na exploração da relação entre uma solução para uma dada instância de um problema e uma solução para sua instância menor.
-
-
O insertion sort geralmente é feito varrendo o subarray ordenado da direita para a esquerda até o primeiro elemento menor ou igual a A[n − 1] ser encontrado para inserir A[n − 1] logo após esse elemento.
Embora a ordenação por inserção seja claramente baseada em uma ideia recursiva, é mais eficiente implementar este algoritmo de baixo para cima, ou seja, iterativamente.
O bom desempenho no caso médio, o qual é duas vezes mais rápido, juntamente com uma excelente eficiência em arrays quase ordenados faz com que a ordenação por inserção se destaque entre seus principais concorrentes (selection sort e bubble sort).
Mergesort é um exemplo de aplicação bem sucedida do divide-and-conquer. Ele ordena um determinado array dividindo-o em duas metades, ordenando cada uma delas recursivamente, e então mescla os dois arrays ordenados em um único.
A fusão de dois arrays ordenados pode ser feita da seguinte maneira: dois ponteiros são inicializados para apontar para os primeiros elementos dos arrays que estão sendo mesclados.
Os elementos apontados são comparados, e o menor deles é adicionado a um novo array sendo construído.
Depois disso, o índice do elemento menor é incrementado para apontar para seu sucessor imediato na matriz de onde foi copiado.
Esta operação é repetida até que um dos dois arrays dados se esgote, e então o restante dos elementos do outro array são copiados para o final do novo array.
-