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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
DarkSkazochnik
3 / 3 / 0
Регистрация: 17.11.2012
Сообщений: 39
#1

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

07.06.2013, 09:39. Просмотров 447. Ответов 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++ Сортировка слиянием: подсчитать количество перестановок
Сортировка слиянием для char элементов C++
Сортировка слиянием для массива состоящего из букв C++
C++ Сортировки слиянием с динамическим массивом
Ошибка в коде сортировки слиянием C++
C++ Ассемблерные вставки в C++. Алгоритм сортировки слиянием
C++ Алгоритм сортировки слиянием. Исправить ошибки в коде
C++ может кто представить схему алгоритма сортировки слиянием?
C++ Оптимизировать алгоритм, чтобы уменьшить количество операций для проверок деления
Как открыть файл в требуемой для него программе? C++

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru