Cамоучитель по Visual Studio.Net

       

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



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

Приведем пример реализации вышеупомянутого рекурсивного алгоритма сортировки массива переменных Quicksort. Его идея состоит в том, что меняются местами элементы массива, стоящие слева и справа от выбранного «центрального» (mid) элемента массива, если они нарушают порядок последовательности. Интервал, в котором выбирается центральный элемент, постепенно сжимается, «расправляясь» сначала с левой половиной массива, затем с правой. Функция Quicksort, приведенная ниже, реализует рекурсивный алгоритм быстрой сортировки. Далее следует код, который позволяет протестировать работу функции. Сортируется массив вещественных чисел, элементы которого заданы случайным образом:

void 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 вызовы функции с другими типами параметров. Например:

void main()

{

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

const int N = 21;

// double ar[N];

int ar[N];

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

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[i]);

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

}

Quicksort(ar,0,N-1);

puts("\n\nAfter SortingXn");

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

{

if (i%3==0)

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

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

}

puts("\n");

}

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

Примечание
Примечание

Перед запуском консольных приложений настройте консольное окно так, чтобы его размеры вмещали весь выходной текст. Для этого вызовите контекстное меню на заголовке консольного окна и дайте команду Properties. Откройте страницу на вкладке Layout и подстройте размеры окна в полях Width и Height группы Window Size.



Содержание раздела