Ordenação de um vetor: Quicksort

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

O algoritmo

typedef enum {FALSE, TRUE} bool; /* A função abaixo rearranja o vetor arr[0..n-1] de modo que * ele fique em ordem crescente. */ void SortIntegerArray( int array[], int n) { int boundary; if (n < 2) return; boundary = Partition( array, n); SortIntegerArray( array, boundary); SortIntegerArray( array + boundary + 1, n - boundary - 1); } /* A função abaixo rearranja os elementos do vetor * arr[0..n-1] (n >= 2) em relação a um número pivot, * que é igual a array[0]. A função devolve um índice * boundary tal que * array[i] < pivot para todo i < boundary, * array[i] == pivot para i == boundary e * array[i] >= pivot para todo i > boundary. */ int Partition( int array[], int n) { int lh, rh, pivot, temp; pivot = array[0]; lh = 1; rh = n - 1; while (TRUE) { while (lh < rh && array[rh] >= pivot) rh--; while (lh < rh && array[lh] < pivot) lh++; /*A*/ if (lh == rh) break; temp = array[lh]; array[lh] = array[rh]; array[rh] = temp; } if (array[lh] >= pivot) return 0; array[0] = array[lh]; array[lh] = pivot; return lh; }

Para entender o funcionamento do algoritmo, convém entender suas invariantes. A cada passagem pelo ponto A temos

• 1 <= lh <= rh <= n-1 ,
• array[0] == pivot ,
• array[1..lh-1] < pivot ,
• array[rh+1..n-1] >= pivot .

Além, disso, a cada passagem pelo ponto A temos uma das seguintes configurações:

1.  lh == rh == 1  e   nada posso afirmar sobre array[lh]    ou
2.  lh < rh ,   array[lh] >= pivot   e   array[rh] < pivot    ou
3.  1 < lh == rh   e  array[lh] < pivot .

Consumo de tempo

O consumo de tempo do algoritmo é proporcional ao número de comparações entre elementos do vetor. No pior caso (por exemplo, se o vetor já está em ordem crescente!), esse número é

n².

Mas "em média" o número de comparações é apenas

n lg n,

sendo lg uma abreviatura de log₂.