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