Форум программистов, компьютерный форум CyberForum.ru

[Сортировка слиянием] Уменьшить количество требуемой памяти для сортировки - C++

Восстановить пароль Регистрация
 
DarkSkazochnik
 Аватар для DarkSkazochnik
3 / 3 / 0
Регистрация: 17.11.2012
Сообщений: 39
07.06.2013, 09:39     [Сортировка слиянием] Уменьшить количество требуемой памяти для сортировки #1
Добрый, на момент написания, день всем.

Изучаю алгоритмы данных, дошёл до сортировки слиянием (Merge Sort). Прочитал, что для сортировки как минимум требуется выделение памяти, эквивалентное одному экземпляру того массива/файла, который будем сортировать.

Возникла такая идея: использовать для такой сортировки массив указателей на элементы сортируемого массива.

Немного прикинул, если, допустим, имеется массив размером n элементов, то для массива указателей потребуется где-то n*4 байта, причём в процессе сортировки указатели, стоящие в массиве на позициях, кратных двойке, будут "сокращаться" с каждой итерацией цикла сортировки, пока всё дело не дойдёт до одного указателя, который показывает на начало отсортированного массива.

При этом массив в памяти будет занимать что-то в районе n*sizeof(тип_данных), и вероятно снижение количества затрат памяти при определённых типах данных.

Хотелось бы узнать ваше мнение по данному поводу, не скупитесь на критику. Только начинаю разбирать, не хочу потом из-за ложных представлений наломать дров.

P.S. Насколько понимаю, это возможно в теории для небольших объёмов данных, для реальных ситуаций (к примеру с большими файлами с последовательным доступом) так лучше не делать.

P.P.S. Пожалуйста, не подумайте что я какой-нибудь новый Попов или Бабушкин, интересуюсь лично для себя.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.06.2013, 09:39     [Сортировка слиянием] Уменьшить количество требуемой памяти для сортировки
Посмотрите здесь:

C++ Сортировки слиянием с динамическим массивом
Ошибка в коде сортировки слиянием C++
C++ Алгоритм сортировки слиянием. Исправить ошибки в коде
C++ Сортировка слиянием: подсчитать количество перестановок
C++ может кто представить схему алгоритма сортировки слиянием?
C++ Оптимизировать алгоритм, чтобы уменьшить количество операций для проверок деления
C++ Внешние сортировки. Сортировка слиянием. Простое слияние
Внешние сортировки. Сортировка слиянием. Естественное слияние C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
stima
429 / 284 / 16
Регистрация: 22.03.2011
Сообщений: 925
Завершенные тесты: 1
07.06.2013, 16:41     [Сортировка слиянием] Уменьшить количество требуемой памяти для сортировки #2
Цитата Сообщение от DarkSkazochnik Посмотреть сообщение
Возникла такая идея: использовать для такой сортировки массив указателей на элементы сортируемого массива.
Ответьте на вопрос, что такое указатель, поймете в чем не правы.
Yandex
Объявления
07.06.2013, 16:41     [Сортировка слиянием] Уменьшить количество требуемой памяти для сортировки
Ответ Создать тему
Опции темы

Текущее время: 15:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru