Classificação e ppesquisa

UFSC-CTC-INE INE5384 - Estruturas de Dados

Ordenação de Dados (IV)

Prof. Ronaldo S. Mello 2002/2

MergeSort
• MergeSort é um método particular de ordenação
– baseia-se em junções sucessivas (merge) de 2 seqüências ordenadas em uma única seqüência ordenada

•

Aplica um método “dividir para conquistar”
– divide o vetor em 2 segmentos (sub-vetores) de comprimento n/2  e  n/2  – ordena recursivamente cada sub-vetor (dividindo novamente, quando possível) – faz o merge dos 2 sub-vetores ordenados para obter o vetor ordenado completo

1

MergeSort - Exemplo
1 1 1 1 1 1 1 4 4 4 3 2 4 4 8 8 8 3 4 3 8 3 3 3 3 8 8 4 5 6 6 6 6 5 2 6 5 5 5 5 6 5 7 6 8 2 2 2 2 2 7 7 7 7 7 7

MergeSort - Junção ou Merge
• Utiliza um vetor temporário (Vtemp) para manter o resultado da ordenação dos 2 sub-vetores
– o método não é “in-place” – Vtemp deve ser um atributo da classe OrdenadorMergeSort
1 1 4 3 3 4 8 8 Vtemp

2

MergeSort - Junção ou Merge
• Após a ordenação, o conteúdo de Vtemp é transferido para o vetor
0 1 2 3

1
0

4
1

3
2

8
3

Vetor

1

3

4

8

Vtemp

transfere os dados ordenados para as mesmas posições do vetor 0 1 2 3 ... ... ... ...

1

3

4

8

...

...

...

...

Vetor

MergeSort - Junção ou Merge
• Número de comparações?
1 1 4 3 4 3 8 8

(1,3) → 1 (4,3) → 3 (4,8) → 4 →8
2 5 6

3 comparações para 4 elementos (n = 4) (1,2) → 1 (3,2) → 2 (3,5) → 3 (4,5) → 4 (8,5) → 5 (8,6) → 6 (8,7) → 7 →8

1

3

4

8

7

1

2

3

4

5

6

7

8

7 comparações para n = 8

– máximo de comparações: n - 1

• Complexidade: O(n)

3

MergeSort - Método Merge
• Recebe 3 parâmetros: esq, meio, dir
– esq, meio e dir são posições do vetor que delimitam 2 sub-vetores contíguos ordenados – sub-vetor 1: [esq, meio] – sub-vetor 2: [meio+1, dir]

• Ordena os 2 vetores em Vtemp
– o resultado fica no intervalo [esq, dir] de Vtemp
• Vtemp deve ter o mesmo comprimento do vetor

•