Учебник по Visual C++ .Net



             

Шаблон функции быстрой сортировки


Quicksort (double *ar, int 1, int r)

{

//========== Рабочие переменные

double mid, temp;

//========== Левая и правая границы интервала

int i = 1, j = r;

//========== Центральный элемент

mid = ar[ (1 + г) /2];

//========== Цикл, сжимающий интервал

do

//== Поиск индексов элементов, нарушающих порядок

while (ar[i] < mid)

i++; // слева

while (mid < ar[j])

j--; // и справа

//== Если последовательность нарушена,

if (i <= j)

{

//===== то производим обмен

temp = ar[i];

ar[i++] = ar[j];

ar[j-—] = temp;

}

}

//========= Цикл do-while повторяется, пока

//========= есть нарушения последовательности

while (i <= j);

//========= Если левая часть не упорядочена,

if (I < j)

Quicksort (ar, 1, j); // то занимаемся ею

// Если правая часть не упорядочена,

if (i < r)

Quicksort (ar, i, r); // то занимаемся ею }

//========== Тестируем алгоритм

void main()

{

//========= Размер массива сортируемых чисел

const int N = 21;

double ar[N]; // Сам массив

puts("\n\nArray before Sorting\n");

for (int i=0; i<N; i++)

{

ar[i] = rand()%20;

if (i%3==0)

printf ("\n");

printf ("ar[%d]=%2.0f\t",i,ar[ij);

}

Quicksort(ar,0,N-1); // Сортировка

puts("\n\nAfter SortingNn");

for (i=0; i<N; i++)

{

if (i%3==0)

printf ("\n");

printf ("ar[%d]=%2.0f\t",i,ar[i]);

}

puts ("\n");

}

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

template <class T>

void Quicksort (Т *ar, int 1, int r)

{

//======= Рабочие переменные

Т mid, temp;

//======= Далее следует тот же код, который приведен

//======= в оригинальной версии функции Quicksort

}

Проверьте функционирование, вставив в функцию main вызовы функции с другими типами параметров. Например:




Содержание  Назад  Вперед