Ordenação por intercalação

Esta página foi extraída (com algumas modificações) da seção 7.3, do livro de Eric Roberts.

O algoritmo Mergesort

/* A função abaixo rearranja o vetor array[0..n-1] de modo que * ele fique em ordem crescente. */ void MargeSort( int array[], int n) { int n1, n2, *arr1, *arr2; if (n <= 1) return; n1 = n/2; n2 = n - n1; arr1 = CopySubArray( array, 0, n1); arr2 = CopySubArray( array, n1, n2); MargeSort( arr1, n1); MargeSort( arr2, n2); Merge( array, arr1, n1, arr2, n2); free( arr1); free( arr2); } /* Esta função intercala os vetores crescentes * arr1[0..n1-1] e arr2[0..n2-1] produzindo assim * o vetor crescente array[0..n1+n2-1]. */ void Merge( int array[], int arr1[], int n1, int arr2[], int n2) { int p, p1, p2; p = p1 = p2 = 0; while (p1 < n1 && p2 < n2) { if (arr1[p1] < arr2[p2]) array[p++] = arr1[p1++]; else array[p++] = arr2[p2++]; } while (p1 < n1) array[p++] = arr1[p1++]; while (p2 < n2) array[p++] = arr2[p2++]; } /* A função CopySubArray devolve uma cópia * result[0..n-1] do vetor array[start..start+n-1]. * A função usa malloc para alocar uma quantidade * apropriada de espaço para o novo vetor e devolve * o endereço do primeiro elemento do novo vetor. */ int *CopySubArray( int array[], int start, int n) { int i, *result; result = malloc( n * sizeof (int)); if (result == NULL) exit( 1); for (i = 0; i < n; i++) result[i] = array[start + i]; return result; }

Consumo de tempo

O consumo de tempo do algoritmo é proporcional ao número de comparações entre elementos do vetor. Esse número é essencialmente

n lg n,

sendo lg uma abreviatura de log₂.  Dizemos que o consumo total de tempo "é da ordem de n lg n".

Exercícios

1. Escreva uma versão iterativa do algoritmo Mergesort. Tenha o cuidado de dizer qual o invariante principal do processo iterativo.

2. [Roberts exr.5, p.321.]  Tal como escrita acima, a função MergeSort precisa de  n lg(n)  posições temporárias na memória (além das n posições permanentes de array) para armazenar os vetores auxiliares.  Escreva uma nova versão que exija apenas  n  posições temporárias na memória.  Sugestão: Escreva uma "função embrulho" que faça a interface com o usuário e aloque um vetor temporário com n elementos. A função MegeSort propriamente dita não aloca novos vetores, usando apenas o espaço alocado pela "função embrulho".