Conteúdo principal
Ciência da Computação
Fusão em tempo linear
A parte restante da ordenação por intercalação é a função
merge
, a qual intercala dois subarrays adjacentes que estão ordenados, array[p..q]
e array[q+1..r]
em um único subarray ordenado em array[p..r]
. Vamos ver como construir essa função de forma que seja o mais eficiente possível. Vamos dizer que os dois subarrays têm um total de n elementos. Temos que examinar cada um dos elementos a fim de intercalá-los no mesmo array, então o melhor que podemos esperar seria um tempo de intercalação de \Theta, left parenthesis, n, right parenthesis. De fato, vamos ver como intercalar um total de n elementos em um tempo \Theta, left parenthesis, n, right parenthesis.Para intercalar os subarrays ordenados
array[p..q]
e array[q+1..r]
e ter o resultado array[p..r]
, precisamos primeiro criar arrays temporários e copiar array[p..q]
e array[q+1..r]
nesses arrays temporários. Nós não podemos reescrever as posições em array[p..r]
até que tenhamos copiados os elementos que estavam originalmente em array[p..q]
e array[q+1..r]
com segurança.Portanto, a primeira tarefa da função
merge
é alocar dois arrays temporários, lowHalf
e highHalf
, para copiar todos os elementos de array[p..q]
para lowHalf
, e todos os elementos de array[q+1..r]
para highHalf
. Quão grande deve ser lowHalf
? O subarray array[p..q]
contém q, minus, p, plus, 1 elementos. E highHalf
? O subarray array[q+1..r]
contém r, minus, q elementos. (Em JavaScript, nós não temos que especificar o tamanho de um array quando o criamos, mas como nós temos que fazer isso em muitas outras linguagens, nós frequentemente levamos isso em conta quando estamos descrevendo o algoritmo.)No nosso array de exemplo
[14, 7, 3, 12, 9, 11, 6, 2]
, é assim que as coisas vão estar depois de termos ordenado recursivamente os arrays array[0..3]
e array[4..7]
(de forma que p, equals, 0, q, equals, 3, e r, equals, 7) e copiado esses subarrays para lowHalf
e highHalf
:Os números em
array
estão cinza para indicar que ainda que essas posições de array contenham valores, os valores "reais" agora estão em lowHalf
e highHalf
. Podemos sobrescrever os números cinza à vontade.Em seguida, nós mesclamos os dois arrays ordenados, agora em
lowHalf
e highHalf
, de volta para array[p..r]
. Deveríamos colocar o menor valor dos dois subarrays em array[p]
. Onde o menor valor poderia estar? Como os subarrays estão ordenados, o menor valor deve estar em um desses dois locais: ou em lowHalf[0]
ou em highHalf[0]
. (É possível que haja o mesmo valor no dois locais, nesse caso podemos considerar qualquer um dos dois o menor valor.) Com apenas uma comparação, podemos decidir entre copiar lowHalf[0]
ou highHalf[0]
para o array[p]
. Em nosso exemplo, highHalf[0]
era menor. Vamos estabelecer também três variáveis para indexar os arrays:i
indexa o próximo elemento delowHalf
que nós ainda não copiamos de volta paraarray
. Inicialmente,i
é 0.j
indexa o próximo elemento dehighHalf
que nós ainda não copiamos de volta paraarray
. Inicialmente,j
é 0.k
indexa a próxima posição dearray
para o qual nós copiamos. Inicialmente,k
é igual ap
.
Depois de copiarmos de
lowHalf
ou highHalf
para array
, devemos incrementar (adicionar 1 a) k
de forma a copiar o próximo menor elemento na próxima posição de array
. Também temos que incrementar i
se copiamos de lowHalf
, ou incrementar j
se copiamos de highHalf
. A seguir estão as representações dos arrays antes e depois do primeiro elemento ser copiado para array
:Nós deixamos
highHalf[0]
cinza para indicar que ele contém um valor que nós não vamos mais considerar. A parte do array highHalf
que ainda não foi intercalada começa no índice j
, que agora é 1. O valor em array[p]
não está mais cinza porque nós copiamos um valor "real" para esse campo.Onde o próximo valor a ser copiado de volta para
array
deve estar? Ele deve ser o primeiro elemento ainda não copiado de volta em lowHalf
(lowHalf[0]
) ou em highHalf
(highHalf[1]
). Com uma comparação nós determinamos que lowHalf[0]
é menor, e então o copiamos para array[k]
e incrementamos k
e i
:Em seguida, comparamos
lowHalf[1]
e highHalf[1]
, e determinamos que devemos copiar highHalf[1]
para array[k]
. E então incrementamos k
e j
:Continuando, sempre comparando
lowHalf[i]
e highHalf[j]
, copiando o menor dos dois para array[k]
, e incrementando i
ou j
:Em algum momento, todos os elementos de
lowHalf
ou de highHalf
serão copiados de volta para array
. Nesse exemplo, todos os elementos de highHalf
são copiados de volta antes de alguns elementos de lowHalf
terem sido copiados. Em casos assim, nós finalizamos apenas copiando os elementos restantes de up lowHalf
ou de highHalf
:Nós dissemos que intercalar n elementos leva um tempo \Theta, left parenthesis, n, right parenthesis, e portanto o tempo de execução da intercalação é linear em relação ao tamanho do subarray. Vamos verificar porque isso é verdade. Nós vimos três partes da intercalação:
- Copie cada elemento em
array[p..r]
emlowHalf
ouhighHalf
. - Enquanto alguns elementos ainda estiverem em
lowHalf
ehighHalf
, compare os primeiros dois elementos não usados e copie o menor deles emarray
. - Quando
lowHalf
ouhighHalf
tiverem todos os seus elementos copiados de volta emarray
, copie cada elemento restante do outro array temporário de volta paraarray
.
Quantas linhas de código nós precisamos executar para cada um desses passos? É um número constante por elemento. Cada elemento é copiado de
array
para lowHalf
ou highHalf
exatamente uma vez no passo 1. Cada comparação no passo 2 leva um tempo constante, já que compara apenas dois elementos, e cada elemento "vence" no máximo uma vez. Cada elemento é copiado de volta para array
exatamente uma vez nos passos 2 e 3 combinados. Como nós executamos cada linha de código um número constante de vezes por elemento e assumimos que o subarray array[p..q]
contém n elementos, o tempo de execução para intercalar é, de fato, \Theta, left parenthesis, n, right parenthesis.No próximo desafio, você irá implementar esta operação de intercalação de tempo linear. Combinado os dois desafios, você terá implementado o algoritmo merge sort por completo.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Quer participar da conversa?
Nenhuma postagem por enquanto.