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

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

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

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

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

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

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

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

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

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

P.P.S. Пожалуйста, не подумайте что я какой-нибудь новый Попов или Бабушкин, интересуюсь лично для себя.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.06.2013, 09:39
Ответы с готовыми решениями:

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

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

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

Подсчитать количество инверсий в файле, модифицировав алгоритм сортировки слиянием
Ножно подсчитать количество инверсий в файле, модифицировав алгоритм сортировки слиянием. Числа в...

1
501 / 350 / 94
Регистрация: 22.03.2011
Сообщений: 1,112
07.06.2013, 16:41 2
Цитата Сообщение от DarkSkazochnik Посмотреть сообщение
Возникла такая идея: использовать для такой сортировки массив указателей на элементы сортируемого массива.
Ответьте на вопрос, что такое указатель, поймете в чем не правы.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.06.2013, 16:41

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

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

Программа для графической иллюстрации сортировки массивов слиянием
Задача. Напишите программу для графической иллюстрации сортировки массивов алгоритмом слияния....

Как уменьшить количество потребляемой памяти
Написал простенькую консольную програмку с несколькими классами. В диспечере задач она занимает не...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru