Листинг 7.7

include <iostream.h>

void qsort(float* array, intleft, int right);

int main()

{

const int n = 10;

float arr[n];

int 1, 1, r;

cout «"введите элементы массива:”;

for (1 = 0; i < n; i++) cin» arr[i];

i = o;r = n - 1; /* левая и правая границы начального фрагмента*/

qsort(arr, 1, r); // 1

for (i = 0; i < n; i++) cout «arr[i] «‘ ‘;

return 0;

}

void qsort(float* array, int left, int right)

{

int i = left, j = right;

float middle = array[(left ⁺ right) / 2];

float temp;

while (i < j)

{

while (array[i] < middle) i++;

while (middle < array[j]) j--;

if (i <= j)

{

temp = array[i];

array[i] = array[j];

array[j] = temp;

i++;

j--;

}

}

if (left < j) qsort(array, left, j);

if (i < right) qsort(array, I, right);

}

Процедура разделения реализована здесь в виде рекурсивно вызываемой функции qsort(), в теле которой есть два обраще­ния к самой себе: в операторе 2 - для сортировки левой половинки текущего фраг­мента, и в операторе 3 - для сортировки его правой половинки.

Однако, у рекурсии есть и недостатки: во-первых, такую программу труднее отла­живать, поскольку требуется контролировать глубину рекурсивного обращения, во-вторых, при большой глубине стек может переполниться, а в-третьих, исполь­зование рекурсии повышает накладные расходы (например, в данном случае в сте­ке сохраняются отнюдь не два числа, представляющие собой границы фрагмента, а гораздо больше, не говоря уже о затратах, связанных с вызовом функции).