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

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

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

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

07.06.2013, 09:39. Просмотров 436. Ответов 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++ Внешние сортировки. Сортировка слиянием. Простое слияние
Внешние сортировки. Сортировка слиянием. Естественное слияние C++
Сортировка слиянием для char элементов C++
C++ Ассемблерные вставки в C++. Алгоритм сортировки слиянием
Сортировка слиянием для массива состоящего из букв C++

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

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

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