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

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

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

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

07.06.2013, 09:39. Просмотров 452. Ответов 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 сортировки: пирамидальная сортировка и сортировка слиянием - C++
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель качества сортировки (количество операций, т.е....

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

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

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

Сортировка слиянием для char элементов - C++
Ниже, мой код, который "сортировкой слиянием" сортирует числа...всё отлично работает. НО нужно сделать так, чтобы эта же программа, так же...

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

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

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом? - C++
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким именно образом? #include <iostream> ...

Сортировки слиянием с динамическим массивом - C++
Добрый вечер! мне нужно отсортировать массив слиянием с динамическим массивом помогите пожалуйста!!! массив #include "stdafx.h" ...

Ошибка в коде сортировки слиянием - C++
Вобщем, я реализовал рекурсивную сортировку слиянием (Merge Sort), но она работает за O(N), а должна за O(N log N), помогите найти ошибку в...

Ассемблерные вставки в C++. Алгоритм сортировки слиянием - C++
Нужна помощь.Необходимо реализовать алгоритм сортировки слиянием по возрастанию из элементов массивов, отсортированный по убыванию. Пишу в...


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

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

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