Considere a seguinte sequência de chaves do vetor [25, 18, 30, 5, 10, 12, 3,22,15,7,9]. 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]

Exercícios relacionados