Вопрос 2. Разработать многопоточную программу для сортировки массива чисел с плавающей точкой методом Хоара
Добавил: | DMT |
Дата создания: | 30 декабря 2007, 18:18 |
Дата обновления: | 30 декабря 2007, 18:18 |
Просмотров: | 8987 последний вчера, 19:30 |
Комментариев: | 2 |
Вопрос 2. Разработать многопоточную программу для сортировки массива чисел с плавающей точкой методом Хоара |
Комментарии для "Вопрос 2. Разработать многопоточную программу для сортировки массива чисел с плавающей точкой методом Хоара"
Пользователь: ruslan Сообщений: 23 Статус: Незримый Зарегистрирован: 5 января 2008, 2:42 Был:29 января 2008, 21:23 | Дата: 11 января 2008, 1:30 Сообщение № 1 |
|
Пользователь: ruslan Сообщений: 23 Статус: Незримый Зарегистрирован: 5 января 2008, 2:42 Был:29 января 2008, 21:23 | Дата: 14 января 2008, 0:26 Сообщение № 2 |
Несколько слов про метод Хоара... Быстрая сортировка Хоара. Массив разбивается на две части таким образом, чтобы каждый элемент левой части был не больше любого элемента правой части. Затем для каждой из этих двух частей подпрограмма вызывается рекурсивно. Иными словами, схема подпрограммы будет выглядеть так: void qsort(int l, int u, int *x) { if(l>=u) return; Разбиение массива на две части; qsort(l,p-1,x); // p – середина массива qsort(p+1,u,x); } Под серединой массива p понимается индекс такого элемента, что для любых i<p<j имеют место неравенства x[i]<=x[p]<=x[j]. Данная подпрограмма будет сортировать элементы x[l],x[l+1],...,x[u]. Для сортировки всего массива она вызывается как [B]qsort(0,n-1,x)[I]. Опишем алгоритм разбиения массива, индексы элементов которого имеют значения l,l+1,...,u. Будем разбивать этот массив на два из следующих соображений. Установим t=x[l]. Будем перебирать элементы массива, начиная с x[l]. Схема массива представлена на рис. 2.1. Здесь m – индекс последнего элемента, меньшего, чем t, i – номер элемента, начиная с которого массив еще не разбит, т.е. i – индекс рассматриваемого элемента. Если x[i]>=t, то, увеличивая i на 1, мы расширяем область, для элементов которой известно, относятся они к левой или правой области разбиения. Если же x[i]<t, то, меняя местами x[i] и x[m+1] и увеличивая m и i на 1, мы вновь расширяем область, разбиение которой известно. Получаем следующие операции: t=x[l]; m=l; for(i=l+1; i<=u; i++) if (x[i]<t) { m++; swap (m,i); } swap (l,m); последняя из которых меняет местами x[l] и x[m]. Пример. Применим быструю сортировку Хоара для следующих входных данных: • При i=1 будет x[1]<55, m=1, и x[1] поменяется местами сам с собой. • При i=2 будет x[2]>=55. • При i=3 будет x[3]<55, m=2, и x[3] поменяется местами c x[2]; получим массив: 55, 41, 26, 59, 53, 58, 97, 93. • При i=4 будет x[4]<55, m=3, и x[4] поменяются местами с x[3]: 55, 41, 26, 53, 59, 58, 97, 93. • При i>4 элементы x[i]>=55, поэтому массив остается прежним. После цикла x[l] и x[m] меняются местами. Получим массив, равный искомому разбиению: Для дальнейшей сортировки нужно вызвать подпрограммы qsort(0,2,x) и qsort(4,7,x). |