Работа с 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.
|