3 / 3 / 1
Регистрация: 17.11.2012
Сообщений: 39
|
|
1 | |
[Сортировка слиянием] Уменьшить количество требуемой памяти для сортировки07.06.2013, 09:39. Показов 2264. Ответов 1
Метки нет Все метки)
(
Добрый, на момент написания, день всем.
Изучаю алгоритмы данных, дошёл до сортировки слиянием (Merge Sort). Прочитал, что для сортировки как минимум требуется выделение памяти, эквивалентное одному экземпляру того массива/файла, который будем сортировать. Возникла такая идея: использовать для такой сортировки массив указателей на элементы сортируемого массива. Немного прикинул, если, допустим, имеется массив размером n элементов, то для массива указателей потребуется где-то n*4 байта, причём в процессе сортировки указатели, стоящие в массиве на позициях, кратных двойке, будут "сокращаться" с каждой итерацией цикла сортировки, пока всё дело не дойдёт до одного указателя, который показывает на начало отсортированного массива. При этом массив в памяти будет занимать что-то в районе n*sizeof(тип_данных), и вероятно снижение количества затрат памяти при определённых типах данных. Хотелось бы узнать ваше мнение по данному поводу, не скупитесь на критику. Только начинаю разбирать, не хочу потом из-за ложных представлений наломать дров. P.S. Насколько понимаю, это возможно в теории для небольших объёмов данных, для реальных ситуаций (к примеру с большими файлами с последовательным доступом) так лучше не делать. P.P.S. Пожалуйста, не подумайте что я какой-нибудь новый Попов или Бабушкин, интересуюсь лично для себя.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
|
|
07.06.2013, 09:39 | |
Ответы с готовыми решениями:
1
2 сортировки: пирамидальная сортировка и сортировка слиянием Внешние сортировки. Сортировка слиянием. Естественное слияние Внешние сортировки. Сортировка слиянием. Простое слияние Подсчитать количество инверсий в файле, модифицировав алгоритм сортировки слиянием |
503 / 352 / 94
Регистрация: 22.03.2011
Сообщений: 1,112
|
|
07.06.2013, 16:41 | 2 |
0
|
07.06.2013, 16:41 | |
Помогаю со студенческими работами здесь
2
Сравнительный анализ Методов Сортировки(метод прямого выбора,метод слиянием,сортировка подсчетом) Сортировка слиянием: подсчитать количество перестановок
Как уменьшить количество потребляемой памяти Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |