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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ long double и double в MSVC 12 одно и тоже, нужна информация,желательно быстрей http://www.cyberforum.ru/cpp-beginners/thread894172.html
Здравствуйте все знают что в VC long double и double одно и тоже, да и при простой проверке это легко выясняется, но нужна информация от самого майкрософта, цитата или ещё что нито, где сказано что в...
C++ Реализовала формулу. Все хорошо, вот только в результатах взялось откуда-то #INF Мне нужно вычислить дифференциал интерполяционного многочлена Лагранжа третьей степени, и подставить значения иксов/игриков и аргумента. ... http://www.cyberforum.ru/cpp-beginners/thread894164.html
Не записывает ничего в файл C++
Добро всем утро! Надеюсь хоть у кого-то оно доброе=) Помогите пжл с программой(написать либо подправить). Задача следующая: "Создать текстовый файл и напечатать в нем не менее пяти строк (можно на...
Почему точность Double такая же как у Float ? C++
Вначале столкнулся с проблемой float: time=65536.0f; (можно и больше число указать) time+=0.003; Тут time не меняетя! Оно меняется, только если не меньше 0.004 прибавлять. Понятно. Проблема с...
C++ Наследование http://www.cyberforum.ru/cpp-beginners/thread894147.html
Доброе утро всем. Есть готовая рабочая программа "Студент. Преподаватель. Человек" нужно закоментить код, не могу разобраться в нем #ifndef MAN_H #define MAN_H #include<iostream> #include...
C++ Программа численного дифф-ия с использованием многочлена третьей степени. Работает, но выдает что-то странное Мне нужно вычислить дифференциал интерполяционного многочлена Лагранжа третьей степени, и подставить значения иксов/игриков и аргумента. ... подробнее

Показать сообщение отдельно
DarkSkazochnik
3 / 3 / 0
Регистрация: 17.11.2012
Сообщений: 39

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

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

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

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

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

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

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

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

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

P.P.S. Пожалуйста, не подумайте что я какой-нибудь новый Попов или Бабушкин, интересуюсь лично для себя.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru