Сортировка массива с минимальным числом перестановок элементов

← →
AlexKniga (2003-08-08 19:10) [0]

Я пользуюсь методом быстрой сортировки проф. К.Хоара. Число требуемых сравнений значений ключа (C) и число перестановок элементов (M) имеют порядок O(n*log(n)).
Но счас мне надо отсортировать ассоциированный массив с минимальным числом перестановок элементов (т.к. это влечет перестановку ассоциированных данных), даже в ущерб числу сравнений значений ключа.

Ассоциированных данных не слишком много и поэтому заводить указатель на них не эффективно.

← →
Serginio478 (2003-08-08 19:18) [1]

QuickSort

← →
Serginio777 (2003-08-08 19:20) [2]

Можешь применить индексы в памяти типа Б деревьев.

← →
Alex Konshin (2003-08-09 09:30) [3]

А зачем ты вообще данные переставляешь?
Да просто заведи дин.массив целых, элементы - индексы элементов в твоем массиве.
Нет смысла заморачиваться с B-tree, если количество элементов известно (и наверняка небольшое).

← →
AlexKniga (2003-08-11 08:38) [4]

Serginio478
QuickSort = Метод К.Хоара

Serginio777
см. Alex Konshin

Alex Konshin
Да дополнительный массив Array [TBase] of TBase хорошее решение, но несколько нарушает читабельность в моем случае.
У меня сортируемый массив это собственные числа, а ассоциированный - соответствующие им собственные вектора. А матрица, составленная из собст. векторов, является матрицей косинусов. И доступ по обеим компонентам желательно иметь симметричный.

В общем, я решил этуц проблему вводом доп условия на равенство в метод К.Хоара.

← →
default (2003-08-11 09:08) [5]

диапазон данных какой?

Сортировка массива с минимальным числом перестановок элементов Найти похожие ветки