Пакет Vstudio7
Шаблон функции быстрой сортировки
Шаблон функции быстрой сортировки
Приведем пример реализации вышеупомянутого рекурсивного алгоритма сортировки массива переменных 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 будет настроена на проверку шаблона функции сортировки для массива вещественных. Проверьте и этот случай. Шаблон должен справиться с обоими.
Примечание 1
Примечание 1
Перед запуском консольных приложений настройте консольное окно так, чтобы его размеры вмещали весь выходной текст. Для этого вызовите контекстное меню на заголовке консольного окна и дайте команду Properties. Откройте страницу на вкладке Layout и подстройте размеры окна в полях Width и Height группы Window Size.
