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

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

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

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

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

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

Метод медиан из трех элементов VS улучшенный быстрый метод сортировки(метод Бентли-Макилроя) - C++
Здравствуйте! Дали весьма интересное задание. Сравнить два вышеуказанных метода сортировки для массива из 10000 элементов, результаты...

Изменить метод "быстрой сортировки" на метод "сортировки вставками" - C++
Как изменить метод "интеративной быстрой сортировки" на метод "сортировки вставками «с конца массива»"? Нужно изменить только метод...

Метод сортировки обменом - C++
Используя метод сортировки обменами,получить из вектора Х размерности 1 вектор В, в котором элементы,начиная с К-го(к<1) размещены по...

Метод пузырьковой сортировки - C++
Подскажите как сделать сортировку одномерного массива методом пузырька по убыванию? //сортировка методом пузырька for (int...

Метод сортировки выбором!!! - C++
ВАРИАНТ 21 Написать программу, которая методом сортировки выбором сортирует введенный пользователем массив слов. Также найти количество...

Метод сортировки выбором -2 - C++
Доброе время суток, Чтоб не засорять чужую тему с чужими задачи, решил создать новую. :) Используя сортировку выбором необходимо...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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, чтобы обогнать классические методы сортировки.
1
Litcher
0 / 0 / 0
Регистрация: 11.07.2012
Сообщений: 21
13.01.2013, 20:05  [ТС] #3
Благодарю за совет
0
Nick Alte
Эксперт С++
1638 / 1010 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
13.01.2013, 20:06 #4
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
из всех алгоритмов сортировок произвольного массива даже самые оптимальные имеют сложность порядка о(n log n
Это не совсем верно, в данном случае - особенно. Линейные методы есть, только требуют количества памяти под все возможные значения элементов массива. Вот тут-то нам и повезло. Достаточно подсчитать количество единиц, чтобы либо подменять обращения к массиву на проверку индекса (сравнение его с границей, отделяющей нули от единиц), либо во второй проход перезаписать в массив то, что в нём будет после сортировки. Вот где-то так.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
13.01.2013, 20:19 #5
Цитата Сообщение от Nick Alte Посмотреть сообщение
Это не совсем верно, в данном случае - особенно. Линейные методы есть, только требуют количества памяти под все возможные значения элементов массива.
Так я говорил об алгоритмах сортировок ПРОИЗВОЛЬНОГО массива. А потом привёл то, о чём говоришь ты. Правда, не обратил внимание, что массив состоит лишь из 0 и 1. Поэтому пересчитывал количество всех чисел до UINT_MAX. Особенно в данном случае, произвольный массив значений от 0 до UINT_MAX лучше каким классическим алгоритмом отсортировать, чем заводить массив счётчиков элементов размером многократно больше самого массива.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.01.2013, 20:19
Привет! Вот еще темы с ответами:

Метод сортировки в файле - C++
Значит так,помогите сделать такое : есть файл(*.txt) в середине есть 1000 строчек (допустим цифри ,int) так вод надо не считивая все...

Метод сортировки Шелла - C++
помогите дописать программу в case 6 СТРОИТЕЛЬНАЯ КОМПАНИЯ (поля: заказчик, вид строительных работ, продолжительность работ,...

Метод поразрядной сортировки. - C++
Помогите решить задачу, для её решения необходимо реализовать метод поразрядной сортировки, отсортировав последовательность в порядке...

Метод сортировки Шелла - C++
Написать программу которая реализует метод сортировки Шелла. Сгенерировать три массива 100, 1.000 и 10.000 элементов типа integer...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.01.2013, 20:19
Ответ Создать тему
Опции темы

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