18 января 2021 года    
Понедельник | 18:57    
Главная
 Новости
Базы данных
Безопасность PC
Всё о компьютерах
Графика и дизайн
Интернет-технологии
Мобильные устройства
Операционные системы
Программирование
Программы
Связь
Сети
 Документация
Статьи
Самоучители
 Общение
Форум







 

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

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

 

Лента новостей


2006 (c) Copyright Hardline.ru