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]