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

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

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

C++ Метод сортировки выбором!!!
Метод сортировки выбором -2 C++
C++ Метод сортировки в файле
C++ Метод поразрядной сортировки.
C++ Метод сортировки обменом
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 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
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
13.01.2013, 20:06     Метод сортировки #4
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
из всех алгоритмов сортировок произвольного массива даже самые оптимальные имеют сложность порядка о(n log n
Это не совсем верно, в данном случае - особенно. Линейные методы есть, только требуют количества памяти под все возможные значения элементов массива. Вот тут-то нам и повезло. Достаточно подсчитать количество единиц, чтобы либо подменять обращения к массиву на проверку индекса (сравнение его с границей, отделяющей нули от единиц), либо во второй проход перезаписать в массив то, что в нём будет после сортировки. Вот где-то так.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
13.01.2013, 20:19     Метод сортировки #5
Цитата Сообщение от Nick Alte Посмотреть сообщение
Это не совсем верно, в данном случае - особенно. Линейные методы есть, только требуют количества памяти под все возможные значения элементов массива.
Так я говорил об алгоритмах сортировок ПРОИЗВОЛЬНОГО массива. А потом привёл то, о чём говоришь ты. Правда, не обратил внимание, что массив состоит лишь из 0 и 1. Поэтому пересчитывал количество всех чисел до UINT_MAX. Особенно в данном случае, произвольный массив значений от 0 до UINT_MAX лучше каким классическим алгоритмом отсортировать, чем заводить массив счётчиков элементов размером многократно больше самого массива.
Yandex
Объявления
13.01.2013, 20:19     Метод сортировки
Ответ Создать тему
Опции темы

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