Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
DarkSkazochnik
3 / 3 / 1
Регистрация: 17.11.2012
Сообщений: 39
#1

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

07.06.2013, 09:39. Просмотров 557. Ответов 1
Метки нет (Все метки)

Добрый, на момент написания, день всем.

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

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

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

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

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

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

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

2 сортировки: пирамидальная сортировка и сортировка слиянием
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма...

Внешние сортировки. Сортировка слиянием. Естественное слияние
Пом-гите решить, заранее благодарен.)) Билет 9 1 .Внешние сортировки....

Внешние сортировки. Сортировка слиянием. Простое слияние
Пом-гите решить, заранее благодарен.)) Билет 8 1 .Внешние сортировки....

Сравнительный анализ Методов Сортировки(метод прямого выбора,метод слиянием,сортировка подсчетом)
Ввод данных: 1. с клавиатуры, 2.с файла (C:\Users\'NAME'\Desktop), 3.случайным...

Сортировка слиянием: подсчитать количество перестановок
Привет всем. Дана задача: подсчитать количество перестановок при сортировке...

Сортировка слиянием для char элементов
Ниже, мой код, который "сортировкой слиянием" сортирует числа...всё отлично...

1
stima
495 / 345 / 93
Регистрация: 22.03.2011
Сообщений: 1,107
Завершенные тесты: 2
07.06.2013, 16:41 #2
Цитата Сообщение от DarkSkazochnik Посмотреть сообщение
Возникла такая идея: использовать для такой сортировки массив указателей на элементы сортируемого массива.
Ответьте на вопрос, что такое указатель, поймете в чем не правы.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.06.2013, 16:41
Привет! Вот еще темы с решениями:

Сортировка слиянием для массива состоящего из букв
Всем привет, помогите пожалуйста с задачкой: с помощью сортировки слиянием...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит...

Сортировки слиянием с динамическим массивом
Добрый вечер! мне нужно отсортировать массив слиянием с динамическим массивом...

Ошибка в коде сортировки слиянием
Вобщем, я реализовал рекурсивную сортировку слиянием (Merge Sort), но она...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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