Информатика и технология программирования


Сортировки разделением


Сортировки, основанные на принципе разделения массива разделяют его на две части относительно некоторого значения, называемого МЕДИАНОЙ. Сами части не упорядочены, но обладают таким свойством, что элементы в левой части меньше медианы, а элементы правой - больше. Благодаря такому свойству эти части можно сортировать независимо. Для этого нужно вызвать ту же самую функцию сортировки, но уже не по отношению к массиву, а к его частям. Функции, вызывающие сами себя, называются рекурсивными и рассмотрены в 5.4. Рекурсивный вызов продолжается до тех пор, пока очередная часть массива не станет содержать единственный элемент:


void sort(int in[], int a, int b)
{
int i;
if (a==b) return;
// Разделить массив в интервале a..b


// на две части a..i-1 и i+1..b


// A[i] - медиана интервала


sort(in,a,i-1); sort(in,i+1,b);
}

В так называемой БЫСТРОЙ СОРТИРОВКЕ разделение производится с использованием оригинального алгоритма. Специфика алгоритма " быстрой сортировки" состоит в выполнении разделения на основе обмена. Сравнение элементов производится с концов массива (i=a, j=b) к середине (i++ или j--), причем "укорочение" происходит только с одной из сторон. После каждой перестановки меняется тот конец, с которого выполняется "укорочение". В результате этого массив разделяется на две части относительно значения первого элемента in[a] , который и становится медианой.


//------------------------------------------------------bk35-04.cpp


//-------"Быстрая" сортировка


void sort(int in[], int a, int b)
{
int i,j,mode;
if (a&#62=b) return;
for (i=a, j=b, mode=1; i &#60 j; mode &#62 0 ? j-- : i++)
if (in[i] &#62 in[j])
{
int c;
c = in[i]; in[i] = in[j]; in[j]=c;
mode = -mode;
}
sort(in,a,i-1); sort(in,i+1,b);
}

Очевидно, что медиана делит массив на две неравные части. Вышеуказанный алгоритм разделения можно выполнить итерационно, применяя его к той части массива, которая содержит его середину (по аналогии с двоичным поиском). Тогда в каждом шаге итерации медиана будет сдвигаться к середине массива. Другой пример обменной сортировки на основе разделения -ПОРАЗРЯДНАЯ СОРТИРОВКА - будет рассмотрен в 4.8.




Начало  Назад  Вперед



Книжный магазин