Форум программистов, компьютерный форум 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
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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, чтобы обогнать классические методы сортировки.
 
Текущее время: 06:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru