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

Сортировка списка - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Месяц и квартал http://www.cyberforum.ru/cpp-beginners/thread878904.html
Задано целое число N (1 ≤ N ≤ 12), которое определят номер месяца в году. По заданному значению N выведите название квартала, к которому принадлежит месяц. Входные данные Единственное число - номер месяца в году. Выходные данные Единственная строка, в которой расположено название соответствующего квартала. Выведите First для первого квартала, Second - для второго, Third - для...
C++ Очередь на основе массива Есть код) помогите переделать его под очередь на основе массива =) еще кто знает как перенести функцию вывода print() в дружественную функцию класса так как сказали мне что тип нельзя сделать как метод класса вывод очереди #include <stdlib.h> #include <iostream> #include <conio.h> #include <math.h> #include <stdio.h> #include <locale.h> #include <windows.h> http://www.cyberforum.ru/cpp-beginners/thread878899.html
Операции с динамическим двумерным массивом C++
Добрый день, мне нужно Сформировать динамический двумерный массив, заполнить его случайными числа-ми и вывести на экран монитора, а затем Добавить строку в начало матрицы. И причем в коде нельзя использовать индексацию, то есть нужно чтобы массив и добавление строки были оформлены через указатели, realloc или что-то в этом роде, вот мой код, но он сделан с помощью индексации, а как по другому я...
C++ Как добавить элементы в конец, начало, середину list?
list<int> m;
C++ Найти квадрат суммы цифр двуцифрового натурального числа http://www.cyberforum.ru/cpp-beginners/thread878883.html
Найти квадрат суммы цифр двуцифрового натурального числа?
C++ Написать программу удаления заданного числового значения из массива объединений Написать программу удаления заданного числового значения из массива объединений. Я представляю что такое объединения, но не знаю как выглядят массивы объединений. Как обычные массивы, только с названиями объединений? И какой тогда у них тип данных? помогите разобраться подробнее

Показать сообщение отдельно
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
26.05.2013, 12:55     Сортировка списка
Связные списки сортируются мердж-сортом. Точка.

Квик-сорт и мердж-сорт основаны на одном и том же инварианте, просто заходят к проблеме с разных сторон.

Квик-сорт не требует O(N) памяти сверху и может работать in-place, но чтобы это использовать, необходим быстрый произвольный доступ к элементам. Это отлично подходит для сортировки массивов, но ужасно работает на списках, где доступ к произвольному элементу выполняется за O(N).

Мердж-сорт требует больше лишней памяти на хранение частично отсортированных элементов, но существенная часть этой памяти уже есть в самих элементах связных списков, и это позволяет обойтись последовательным доступом к частично отсортированным кускам. Это отлично работает на связных списках, но ужасно для массивов, которые надо будет постоянно перемещать и перевыделять.
 
Текущее время: 08:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru