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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Litcher
0 / 0 / 0
Регистрация: 11.07.2012
Сообщений: 21
#1

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

13.01.2013, 19:15. Просмотров 408. Ответов 4
Метки нет (Все метки)

Доброго времени суток господа, имеется программа которая сортирует массив(состоящий из 0 и 1), так чтобы в начале были 0, а потом 1. Используемый метод сортировки не совсем устраивает, хотелось бы проводить его за 1 цикл. Жду ваших предложений, советов по этому поводу, код программы прилагаю.
Вложения
Тип файла: rar Test_1i.rar (1.8 Кб, 4 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.01.2013, 19:15     Метод сортировки
Посмотрите здесь:

C++ Метод сортировки выбором!!!
Метод сортировки выбором -2 C++
C++ Метод сортировки в файле
C++ Метод поразрядной сортировки.
C++ Н-ленточное слияние с метод сортировки
C++ Н-ленточное слияние с метод сортировки
C++ Метод сортировки обменом
C++ Метод линейной сортировки
C++ метод сортировки Шелла
Пузырьковый метод сортировки с оптимизацией C++
Метод сортировки пузырьком C++ C++
C++ Изменить метод "быстрой сортировки" на метод "сортировки вставками"

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1886 / 1741 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
13.01.2013, 19:36     Метод сортировки #2
не читал и врядли много желающих найдётся.
Цитата Сообщение от 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, чтобы обогнать классические методы сортировки.
Litcher
0 / 0 / 0
Регистрация: 11.07.2012
Сообщений: 21
13.01.2013, 20:05  [ТС]     Метод сортировки #3
Благодарю за совет
Nick Alte
Эксперт С++
1599 / 991 / 117
Регистрация: 27.09.2009
Сообщений: 1,911
Завершенные тесты: 1
13.01.2013, 20:06     Метод сортировки #4
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
из всех алгоритмов сортировок произвольного массива даже самые оптимальные имеют сложность порядка о(n log n
Это не совсем верно, в данном случае - особенно. Линейные методы есть, только требуют количества памяти под все возможные значения элементов массива. Вот тут-то нам и повезло. Достаточно подсчитать количество единиц, чтобы либо подменять обращения к массиву на проверку индекса (сравнение его с границей, отделяющей нули от единиц), либо во второй проход перезаписать в массив то, что в нём будет после сортировки. Вот где-то так.
Kuzia domovenok
 Аватар для Kuzia domovenok
1886 / 1741 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
13.01.2013, 20:19     Метод сортировки #5
Цитата Сообщение от Nick Alte Посмотреть сообщение
Это не совсем верно, в данном случае - особенно. Линейные методы есть, только требуют количества памяти под все возможные значения элементов массива.
Так я говорил об алгоритмах сортировок ПРОИЗВОЛЬНОГО массива. А потом привёл то, о чём говоришь ты. Правда, не обратил внимание, что массив состоит лишь из 0 и 1. Поэтому пересчитывал количество всех чисел до UINT_MAX. Особенно в данном случае, произвольный массив значений от 0 до UINT_MAX лучше каким классическим алгоритмом отсортировать, чем заводить массив счётчиков элементов размером многократно больше самого массива.
Yandex
Объявления
13.01.2013, 20:19     Метод сортировки
Ответ Создать тему
Опции темы

Текущее время: 14:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru