Сортировка фон Неймана
Метод фон Неймана (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
Дата добавления: 2014-12-02; просмотров: 1020;