| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Delphi: Общие вопросы > Турнирная сортировка |
| Автор: ENTiTY 18.12.2002, 06:10 |
| Нужен алгоритм турнирной сортировки для сортировки матрицы |
| Автор: Medved 18.12.2002, 06:24 |
| Модератор: Ну и? А вопрос где? Что вы хотите от посетителей форума? 1) Если Вам непонятен сам алгоритм то я перемещу тему в раздел алгоритмов 2) Если у Вас затруднение в реализации на Дельфи той или иной функции то хотелось бы услышать какая именно функция у Вас не выходит и тот код который у Вас не работает. |
| Автор: ENTiTY 18.12.2002, 06:43 |
| Понял, сейчас объясню. Алгоритм сортировки не могу найти в нэте именно для паскаля. Нашел для C++, но там он написан с использованием классов, а мне нужно без использования всяких структур данных (ну по возможности) или хотя бы на паскале. С С++ очень не хочется переводить. |
| Автор: Cashey 18.12.2002, 07:05 |
| Так что тебе надо? Алгоритм или готовый код программы? Мой знакомый реализовал это на FoxPro. Подойдет? |
| Автор: ENTiTY 18.12.2002, 07:09 |
| Нужен код. На FoxPro кинь, плиз, может разберусь, если он не сильно отличается от чистого паскаля. |
| Автор: ENTiTY 18.12.2002, 07:11 |
| На всякий случай приведу код на С++. template <class T> class DataNode { public: // элемент данных, индекс в массиве, логический флажок T data; int index; int active; friend int operator <= (const DataNode<T> &x, const DataNode<T> &y); }; Сортировка реализуется с помощью функций TournamentSort и UpdateTree. // сформировать последовательное дерево, скопировать туда элементы массива; // отсортировать элементы и скопировать их обратно в массив template <class T> void TournamentSort (T a[], int n) { DataNode<T> *tree; // корень дерева DataNode<T> item; // минимальная степень двойки, большая или равная n int bottomRowSize; // число узлов в полном дереве, нижний ряд которого // имеет bottomRowSize узлов int treesize; // начальный индекс нижнего ряда узлов int loadindex; int i, j; // определить требуемый размер памяти для нижнего ряда узлов bottomRowSize = PowerOfTwo(n); // вычислить размер дерева и динамически создать его узлы treesize = 2 * bottomRowSize - 1; tree = new DataNode<T>[treesize]; loadindex = treesize - bottomRowSize // скопировать массив в дерево объектов типа DataNode j = 0; for (i=loadindex; i<treesize; i++) { item.index = i; if (j < n) { item.active = 1; item.data = a[j++]; } else item.active = 0; tree[i] = item; } // выполнить начальные сравнения для определения наименьшего элемента i = loadindex; while (i > 0) { j = i; while (j < 2*i); // обработать пары соревнующихся { // проведение матча. сравнить tree[j] с его соперником tree[j+1] // скопировать победителя в родительский узел if (!tree[j+1].active || tree[j] < tree[j+1]) tree[(j-1)/2] = tree[j]; else tree[(j-1)/2] = tree[j+1]; j += 2; // перейти к следующей паре } // обработать оставшиеся n-1 элементов. скопировать победителя // из корня в массив. сделать победителя неактивным. обновить // дерево, разрешив сопернику победителя снова войти в турнир for (i=0; i<n-1; i++) { a[i] = tree[0].data; tree[tree[0].index].active = 0; UpdateTree(tree, tree[0].index); } // скопировать значение в массив a[n-1] = tree[0].data; } В функцию UpdateTree передается индекс i, указывающий исходное положение наименьшего текущего элемента в нижнем ряду дерева. Это — удаляемый узел (становится неактивным). Значению, которое "проиграло" предварительный раунд последнему победителю (наименьшему значению), разрешается снова войти в турнир. // параметр i есть начальный индекс текущего наименьшего элемента // в списке (победителя турнира) template <class T> void UpdateTree(DataNode<T> *tree, int i) { int j; // определить соперника победителя. позволить ему продолжить // турнир, копируя его в родительский узел. if (i % 2 == 0) tree [(i-1)/2] = tree[i-1]; // соперник левый узел else tree [(i-1)/2] = tree[i+1]; // соперник правый узел // переиграть те матчи, в которых принимал участие // только что исключенный из турнира игрок i = (i-1)/2; while (i > 0) { // соперником является правый или левый узел? if (i % 2 == 0) j = i-1; else j = i+1; // проверить, является ли соперник активным if (!tree[i].active || !tree[j].active) if (tree[i].active) tree[(i-1)/2] = tree[i]; else tree[(i-1)/2] = tree[j]; // устроить соревнование. // победителя скопировать в родительский узел else if (tree[i] < tree[j]) tree[(i-1)/2] = tree[i]; else tree[(i-1)/2] = tree[j]; // перейти к следующему кругу соревнования (родительский уровень) i = (i-1)/2; } // Турнир с новым соперником закончен. // очередное наименьшее значение находится в корневом узле } |
| Автор: Cashey 18.12.2002, 21:29 |
| Какой смысл ты вкладываешь в понятие сортировки? Программа подбора пар в шахматном турнире по швейцарской системе отвечает этому понятию? А приведенный код на Си отрабатывает только частный случай и понять общую идею по нему невозможно. |
| Автор: Black_Joker 19.12.2002, 02:10 |
| Скажите подробнее, что вы хотите? И как это должно выглядеть. |
| Автор: ENTiTY 22.12.2002, 22:24 |
| На самом деле - зто не частный случай, а общий. (чемпион - это самый большой элемент в массиве, потом он выпадает и турнир начинается сначала). Ладно, ничего не надо. Сам всё сделаю. Все равно всем спасибо. |