Форум программистов, компьютерный форум 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++ Упорядочите массив по возрастанию и убыванию методом обмена Упорядочите массив по возрастанию и убыванию методом обмена. подробнее

Показать сообщение отдельно
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
13.01.2013, 19:36
не читал и врядли много желающих найдётся.
Цитата Сообщение от Litcher Посмотреть сообщение
Используемый метод сортировки не совсем устраивает, хотелось бы проводить его за 1 цикл.
из всех алгоритмов сортировок произвольного массива даже самые оптимальные имеют сложность порядка о(n log n). Ты же ищешь алгоритм со сложностью порядка o(n). Так что не найдёшь.

Не, можно конечно дать ограничение, что тип элементов,скажем unsigned int, завести массив из UINT_MAX элементов и сделать так.
C++
1
2
3
4
5
6
7
8
9
int indicies[UINT_MAX];
int pos=0;
for (int i=0; i<UINT_MAX; i++)
indicies[i]=0;
for (int i=0; i<size_of_array; i++)
indicies[a[i]]++;
for (int i=0; i<UINT_MAX; i++)
for (int j=0; j<indicies[i]; j++)
a[pos++]=i;
Теоретически это должно иметь сложность порядка о(n)
практически сортируемый массив должен иметь длину более UINT_MAX, чтобы обогнать классические методы сортировки.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru