у кого нибудь есть, или алгоритм написания!! Помогите пожалуйста...
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Сортировка слиянием |
| Автор: MegBegb 26.5.2005, 15:25 |
| сортировка массива однократным слиянием с использованием массива указателей у кого нибудь есть, или алгоритм написания!! Помогите пожалуйста... |
| Автор: Royan 26.5.2005, 17:29 |
| А ты уверен, что сортировка именно массива, может быть списка? |
| Автор: yaja 26.5.2005, 22:24 |
А сколько дополнительной памяти можно ипользовать?? Еслb O(1) то не знаю как решать, но знаю, где можно об этом прочитать (господин Кнут написал про эту тему в своем 3-м томе). А если есть O(n) дополнительной памяти, то делаем, следующим образом. Используем метод рзделяй и властвуй  , т.е. прога рекурсивная. Общий вид следующий:Merge-Sort(A, p, r) if (p < r) then q <-(p+r)/2; Merge-Sort(A, p, q) Merge-Sort(A, q + 1, r) Merge(A, p, q, r) Где Merge соединяет два отсортированных куска масива за время O(n). Происходит это следующим образом. Изначально храним указатели на начало каждого куска. На каждом шаге сравниваем элемента на которые указывают эти указатели и наименьший из них сливаем в доп. массив и указатель увеличиваем на единицу (указатель - идекс элемента в массиве). И так далее |
| Автор: MegBegb 26.5.2005, 23:25 |
| Вот задание: Сортировка масива однократным слиянием с использованием массива указателей. Составляется массив указателей на динамические массивы, в каждый из которых копируется N элементов исходного массива и некоторое максимальное значение в качестве ограничителя последовательности. Каждый динамический массив сортируется. Затем производится слияние с использованием и продвижением указателей (указатель ссылается на очередное значение в динамическом массиве) Помогите пжжжалста |
| Автор: MegBegb 28.5.2005, 18:11 |
Блин пятый день мучаюсь ничаго не получается!!!  Может у кого есть алгоритм к данной программке?  |