Сортировка фон Неймана

Метод фон Неймана (1945 г.) использует тот факт, что некото­рые группы элементов уже упорядочены в исходной последо­ва­тель­ности. Используются две области памяти, назовем их A и B. В исходном состоянии таблица находится в области A. Сначала вы­пол­няем слияние отрезков упо­ря­доченности, начинающихся на

разных концах таблицы (рис. 36).

Рис 36. Сортировка фон Неймана

Результат слияния помещается в начало области В. Затем от достигнутых позиций продолжаем движение по области А (вторая строка рис. 35), помещая результат, начиная с последней позиции в области B. Следующий процесс слияния вновь помещает результат в левую часть области B, начиная от уже заполненных позиций. Таким образом, двигаемся по области А слева направо и справа налево, помещая результаты слияния поочередно в левую и правую часть области В до тех пор, пока перенос всех данных из области А в область В не будет завершен. В результате такого переноса число отрезков упорядоченности уменьшится вдвое. Затем тот же процесс повторяется для переноса из области В в область А. Алгоритм заканчивает свою работу, когда в результате очередного переноса из области в область, будет получен единственный отрезок. Текст алгоритма приведен ниже.

void Join(int A[], int B[], int *left, int *right,

int *kl, int *kr, int Step){

// Выполняется слияние отрезков массива ключей A:

// левого, начиная с *left и правого, начиная с *right

// (по ходу дела *left, *right изменяются)

// результат слияния помещается в массив B, начиная с

// *kl или *kr, которые изменяются с шагом Step. Step=1,

// если результат слияния помещается в b слева направо и

// Step=-1, если справа налево

bool l=true,r=true; // признаки того, что участок

// упорядоченности (left,right) еще не кончился

int v;

while(l || r){

// найдем v - меньший ключ в сливаемых отрезках

if(l && (!r || A[*left] <= A[*right])){

v=A[(*left)++];

l=(*left<*right && A[*left] >= A[*left-1]);

} else {

v=A[(*right)--];

r=(*right>*left && A[*right] >= A[*right+1]);

}

if(Step==1){

B[(*kl)++]=v;

} else {

B[(*kr)--]=v;

}

}

}

//------------------------------------------------

int Prohod(int A[], int B[], int N){

// функция выполняет перекачку из области A в область B

// и возвращает число отрезков упорядоченности в области B

int left,right,kl,kr;

int Count,Step;

left=0; right=N-1; kl=0; kr=N-1; step=1;Count=0;

while(left<right){

Join(A,B,&left,&right,&kl,&kr,Step);

if(right==left){

B[kl]=A[left];

Count++;

}

Count++;

Step=-Step;

}

return Count;

}

//----------------------------------------------

void Neumann(int N, int A[]){

int *B;

bool flag=false; // если flag=false, то выполняем

// перекачку из A в B

int *from,*to;

B=new int[N];

do {

if(flag){

from=B;

to=A;

} else {

from=A;

to=B;

}

flag=!flag;

} while(Prohod(from,to,N) > 1);

if(flag){

memcpy(A,B,N*sizeof(int));

}

delete [] B;

}

Время работы сортировки пропорционально , так как потребуется не более переходов из области в область, и при каждом переходе проходятся все данные.

Дата добавления: 2014-12-08