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

сортировки этого типа используются повторяющийся процесс разделения исходной последовательности на части с последующим их соединением обратно. При этом на одном этапе происходит изменение порядка следования элементов, а другой является чисто формальным.

Сортировки рекурсивным разделением. Сортировки разделяют массив на две части относительно некоторого значения, называемого медианой. Медианой может быть выбрано любое «среднее» значение, например, среднее арифметическое. Сами части не упорядочены, но обладают таким свойством, что элементы в левой части меньше медианы, а элементы правой - больше. Благодаря такому свойству эти части можно сортировать независимо. Для этого нужно вызвать ту же самую функцию сортировки, но уже не по отношению к массиву, а к его частям. Функции, вызывающие сами себя, называются рекурсивными (см. 7.1). Рекурсивный вызов продолжается до тех пор, пока очередная часть массива не станет содержать единственный элемент. Так будет выглядеть «заготовка» сортировки разделением, использующая простейший способ реализации разделения

Главная цель – не разделить исходный массив, а отсортировать его. Однако, разделив массив, можно сделать то же самое с обеими полученными частями, а затем с частями частей и т.д., пока каждая часть будет содержать только один элемент. Соответствующие действия можно выполнить, используя рекурсию или механизм стека.

void sort(int in[],int a,int b){

if (a>=b) return; // осталось не более 1 элемента - выход

int i,j,k,n1=b-a+1; // размерность интервала

int *out=new tmp[b-a+1]; // временный массив для разделения

double s;... // вычислить медиану, например (min+max)/2

for(i=a,j=0,k=n1-1;i<=b;i++) // цикл разделения из 2.4 с учетом

... // начала интервала – a

If (j!=0){ // если все элементы одинаковые -

sort(tmp,0,k); // разделения не будет

sort(tmp,j,n-1);

}

for(i=a,j=0;i<=b;i++,j++) in[i]=tmp[j]; // вернуть отсортированные данные