Considere a seguinte sequência de chaves do vetor [25, 18, 30, 5, 10, 12,
. Mostre o passo a passo da ordenação utilizando o MergeSort, ordenando de forma crescente.
Passo 1
Beleza, vamos lá! A gente tem um vetor com as chaves
[25, 18, 30, 5, 10, 12, 3, 22, 15, 7, 9] que precisa ser ordenado de forma crescente usando o MergeSort. MergeSort é um algoritmo de ordenação que segue o método “dividir para conquistar”. Para resolver isso, vamos dividir o vetor em partes menores, ordenar essas partes e depois juntá-las de volta de forma ordenada. Vamos começar!Passo 2
Primeiro, vamos entender como o MergeSort funciona. Ele divide o vetor em duas metades até que cada parte tenha apenas um elemento. Depois, ele começa a combinar essas partes de forma ordenada.
Nosso vetor inicial tem 11 elementos:
[25, 18, 30, 5, 10, 12, 3, 22, 15, 7, 9].Passo 3
Vamos dividir o vetor em duas metades:
- Primeira metade:
[25, 18, 30, 5, 10] - Segunda metade:
[12, 3, 22, 15, 7, 9]
Passo 4
Agora, continuamos dividindo cada metade até termos sub-vetores com apenas um elemento.
Dividindo a primeira metade
[25, 18, 30, 5, 10]:[25, 18, 30][5, 10]
Dividindo a segunda metade
[12, 3, 22, 15, 7, 9]:[12, 3, 22][15, 7, 9]
Passo 5
Vamos continuar dividindo:
Dividindo
[25, 18, 30]:[25, 18][30]
Dividindo
[5, 10]:[5][10]
Dividindo
[12, 3, 22]:[12, 3][22]
Dividindo
[15, 7, 9]:[15, 7][9]
Passo 6
Agora, cada sub-vetor tem apenas um ou dois elementos. Podemos começar a ordenar e a combinar.
Ordenando
[25, 18]:Comparando 25 e 18, vemos que 18 é menor. Então, ordenado fica
[18, 25].Ordenando
[12, 3]:Comparando 12 e 3, 3 é menor. Fica
[3, 12].Ordenando
[15, 7]:Comparando 15 e 7, 7 é menor. Fica
[7, 15].Os outros sub-vetores
[30], [5], [10], [22], e [9] já têm um elemento, então estão ordenados.Passo 7
Agora, vamos começar a combinar os sub-vetores ordenados.
Combinando
[18, 25] com [30]:Vamos comparar os elementos:
- 18 (primeiro de
[18, 25]) com 30 → 18 é menor, então coloca 18. - 25 (próximo de
[18, 25]) com 30 → 25 é menor, coloca 25. - Restou 30 → adiciona.
Resultado:
[18, 25, 30]Combinando
[5] com [10]:- 5 é menor que 10 → adiciona 5.
- Restou 10 → adiciona.
Resultado:
[5, 10]Combinando
[3, 12] com [22]:- 3 é menor que 22 → adiciona 3.
- 12 é menor que 22 → adiciona 12.
- Restou 22 → adiciona.
Resultado:
[3, 12, 22]Combinando
[7, 15] com [9]:- 7 é menor que 9 → adiciona 7.
- 15 é maior que 9 → adiciona 9.
- Restou 15 → adiciona.
Resultado:
[7, 9, 15]Passo 8
Continuamos combinando os sub-vetores maiores agora.
Combinando
[18, 25, 30] com [5, 10]:Vamos comparar elemento a elemento:
- 18 vs 5 → 5 é menor, adiciona 5.
- 18 vs 10 → 10 é menor, adiciona 10.
- 18 vs nada → adiciona 18.
- 25 → adiciona 25.
- 30 → adiciona 30.
Resultado:
[5, 10, 18, 25, 30]Combinando
[3, 12, 22] com [7, 9, 15]:- 3 vs 7 → 3 é menor, adiciona 3.
- 12 vs 7 → 7 é menor, adiciona 7.
- 12 vs 9 → 9 é menor, adiciona 9.
- 12 vs 15 → 12 é menor, adiciona 12.
- 22 vs 15 → 15 é menor, adiciona 15.
- Restou 22 → adiciona.
Resultado:
[3, 7, 9, 12, 15, 22]Passo 9
Por fim, vamos combinar as duas metades ordenadas.
Combinando
[5, 10, 18, 25, 30] com [3, 7, 9, 12, 15, 22]:Vamos comparar passo a passo:
- 5 vs 3 → 3 é menor, adiciona 3.
- 5 vs 7 → 5 é menor, adiciona 5.
- 10 vs 7 → 7 é menor, adiciona 7.
- 10 vs 9 → 9 é menor, adiciona 9.
- 10 vs 12 → 10 é menor, adiciona 10.
- 18 vs 12 → 12 é menor, adiciona 12.
- 18 vs 15 → 15 é menor, adiciona 15.
- 18 vs 22 → 18 é menor, adiciona 18.
- 25 vs 22 → 22 é menor, adiciona 22.
- Restam 25 e 30 → adiciona 25 e 30.
Resultado final:
[3, 5, 7, 9, 10, 12, 15, 18, 22, 25, 30]Resposta
A sequência ordenada de forma crescente usando o MergeSort é:
[3, 5, 7, 9, 10, 12, 15, 18, 22, 25, 30]