Шаблон
функции быстрой сортировки
Приведем пример
реализации вышеупомянутого рекурсивного алгоритма сортировки массива переменных
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.
|
