/** * Método merge sort, ou ordenação por intercalação , é um exemplo de algoritmo * de ordenação do tipo dividir-para-conquistar. Su a idéia básica é que é muito * fácil criar uma sequência ordenada a partir de d uas outras também ordenadas. * Para isso, ele divide a sequência original em pa res de dados, ordena-as; * depois as agrupa em sequências de quatro element os, e assim por diante, * até ter toda a sequência dividida em apenas duas partes. O método MergeSort * rearranja o vetor v[BeginList..EndList-1] em ord em crescente. **/ void SortingAlgorithms::MergeSort( ElementVector & ev, int BeginList, int EndList) { if (BeginList < EndList -1) { int middle = (BeginList + EndList)/2; MergeSort(ev, BeginList, middle); MergeSort(ev, middle, EndList); Merges(ev, BeginList, middle, EndList); } } /** * Método auxiliar ao MergeSort que executa a inter calação das listas. * O método recebe vetores crescentes v[BeginList.. Middle-1] e * v[Middle..EndList-1] e rearranja v[BeginList..En dList-1] em ordem crescente. **/ void SortingAlgorithms::Merges( ElementVector & ev, int BeginList, int Middle, int EndList) { int i, j, k; ElementVector w; //Executa um resize na lista de elementos auxiliar alocando o necessário para a //intercalação dos elementos. w.resize(EndList - BeginList); //Estabelecendo os limites para a intercalação i = BeginList; j = Middle; k = 0; //Verifica quem deve ser intercalado while( i < Middle && j < EndList) { if (ev[i] <= ev[j]) w[k++] = ev[i++]; else w[k++] = ev[j++]; } //Executa as intercalações finais. while(i < Middle) { w[k++] = ev[i++]; } while(j < EndList) { w[k++] = ev[j++]; } //Copia a lista auxiliar para a lista original for( i = BeginList; i < EndList; ++i) { ev[i] = w[i-BeginList]; } //Limpa a lista auxiliar ... w.clear(); }

/** * Método de Ordenação QuickSort é um método de ord enação muito rápido e * eficiente, inventado por C.A.R. Hoare em 1960. O Quicksort é um algoritmo * de ordenação não-estável que adota a estratégia de divisão e conquista, * podendo sofrer degeneração no melhor caso e caso médio [nlogn] para o pior * caso [n^2]. Essa implementação pode ser encontra da no livro de Sedgewick. * O método rearranja o vetor v[p..r], com p <= r+1 , de modo que ele fique * em ordem crescente. Esse método não se utiliza d e um particionador explicito * e o pivô de verificação sempre é dado por um ele mento central. **/ void SortingAlgorithms::QuickSort( ElementVector & ev, int BeginList, int EndList) { int i , j; Element c, t; if (BeginList < EndList) { c = ev[(BeginList + EndList) / 2]; i = BeginList; j = EndList; while (i <= j) { while (ev[i] < c) { ++i; } while (c < ev[j]) { --j; } if (i <= j) { t = ev[i], ev[i] = ev[j], ev[j] = t; ++i, --j; } } //Segmento onde ocorre a chamada recursiva ao métod o QuickSort(ev, BeginList, j); QuickSort(ev, i, EndList); } }

/** * Método de ordenação quick sort que utiliza uma f unção de particionamento * da lista de elementos. Esse método utiliza um p articionador explícito * porém seu pivo de verificação não é um elemento central previamente definido * e sim elementos que se encontram mais a esquerda de cada partição definida. **/ void SortingAlgorithms::QSort( ElementVector & ev, int left, int right) { int new_right; if (right > left) { new_right = Partition(ev, left, right); QSort(ev,left, new_right - 1); QSort(ev,new_right + 1,right); } return; } /** * Método auxiliar ao QSort que executa particionam ento da lista de elementos. **/ int SortingAlgorithms::Partition( ElementVector & ev, int left, int right) { register int i, j; i = left; for (j = left + 1; j <= right; j++) { if (ev[j] < ev[left]) { ++i; ev.swap(i,j); } } //O elemento do limite da partição é trocado com o pivô. Necessariamente isso //é apenas uma reatribuição quando a lista já se en contra ordenada. ev.swap(left,i); return i; }