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

Метод сортировки - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Удаление массива указателей http://www.cyberforum.ru/cpp-beginners/thread760683.html
есть класс: class test { private: static test **list; static int count_object; public: void mesto::Add() {
C++ Переписать из одного массива в другой Дан массив целых чисел из n элементов. Известно, что в массиве все элементы по модулю меньше 100. Переписать в другой массив из данного сначала все однозначные числа, затем все двузначные, сохранив порядок их следования. http://www.cyberforum.ru/cpp-beginners/thread760677.html
Вычислить сумму целых частей элементов массива, расположенных после последнего отрицательного элемента C++
Вычислить сумму целых частей элементов массива, расположенных после последнего отрицательного элемента.
C++ Найдите количество абсолютных и локальных минимумов и максимумов среди элементов одномерного массива
Найдите количество абсолютных и локальных минимумов и максимумов среди элементов одномерного массива.
C++ Перегрузка http://www.cyberforum.ru/cpp-beginners/thread760635.html
В одномерном массиве, состоящем из n элементов вычислить: 1. Минимальный элемент массива 2. Сумму элементов массива, расположенных между первым и последним положительными элементами. 3. Преобразовть массив таким образом, чтобы сначала располагались все элементы равные нулю, а потом все остальные Для каждого пункта задания создать: 1. Перегружаемые функции для типов int и double 2. Шаблоны...
C++ Упорядочите массив по возрастанию и убыванию методом обмена Упорядочите массив по возрастанию и убыванию методом обмена. подробнее

Показать сообщение отдельно
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
13.01.2013, 20:06     Метод сортировки
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
из всех алгоритмов сортировок произвольного массива даже самые оптимальные имеют сложность порядка о(n log n
Это не совсем верно, в данном случае - особенно. Линейные методы есть, только требуют количества памяти под все возможные значения элементов массива. Вот тут-то нам и повезло. Достаточно подсчитать количество единиц, чтобы либо подменять обращения к массиву на проверку индекса (сравнение его с границей, отделяющей нули от единиц), либо во второй проход перезаписать в массив то, что в нём будет после сортировки. Вот где-то так.
 
Текущее время: 17:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru