|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
08.09.2013, 17:38 | #1 |
Форумчанин
Регистрация: 10.11.2008
Сообщений: 120
|
Сортировка массива
Не могу решить легкую на слух задачу!
Дан массив, элементы которого равны либо единицы либо двойки. Написать программу, которая расставит элементы таким образом, чтобы за каждой единицой следовала двойка, причем если каких то елементов больше, то они выписываются в конец. Например, последовательность {2,1,1,1,2,1} должна преобразовываться в {1,2,1,2,1,1}. Код:
помог - жми на весы
|
08.09.2013, 18:33 | #2 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Я бы в таком направлении двигался:
Код:
I'm learning to live...
|
08.09.2013, 18:38 | #3 |
Форумчанин
Регистрация: 10.11.2008
Сообщений: 120
|
У меня былы такая мысль, полностью поддерживаю.
помог - жми на весы
|
08.09.2013, 18:42 | #4 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,291
|
Вроде работает (красивое решение не приходит в голову):
Код:
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
Последний раз редактировалось BDA; 08.09.2013 в 19:36. |
09.09.2013, 22:35 | #5 |
Форумчанин
Регистрация: 10.11.2008
Сообщений: 120
|
BDA, спасибо
помог - жми на весы
|
15.09.2013, 00:00 | #6 |
Форумчанин
Регистрация: 10.11.2008
Сообщений: 120
|
А, все понял.
Код:
помог - жми на весы
|
15.09.2013, 06:34 | #7 |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Ну да, тут все предложили сортировку подсчетом )
осталось заметить что это лучший вариант и выполняется за линейное время |
15.09.2013, 13:45 | #8 |
Старожил
Регистрация: 16.12.2011
Сообщений: 2,329
|
http://ideone.com/MYc0Ab
Код:
|
15.09.2013, 14:30 | #9 |
Старожил
Регистрация: 16.12.2011
Сообщений: 2,329
|
Вот другая версия, ещё более быстрого алгоритма:
http://ideone.com/MYc0Ab #include <set> #include <algorithm> // std::random_shuffle #include <iostream> using namespace std; Код:
Здесь мы теряем всю скорость из-за: 1. Пересоздание массива в виде дерева multiset. Для этого производится обход по всему оригинальному массиву. Это колоссальная потеря времени. 2. При моздании дерева multiset задействуется стандартный аллокатор динамической памяти. Единократное использование которого проссаживает рантайм сильнее, чем вся остальная процедура сортировки вместе взятая. Таким образом, не смотря на то, что сам по себе алгоритм более быстр, он даст профит к скорости только если изначально в качестве контейнера будет использован multiset, а не сишный массив. И если стандартный аллокатор будет заменен на какой нибудь пул памяти, который не будет дергать кучу. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Быстрая сортировка(сортировка Хоара). Сортировка фрагмента массива [C++] | druger | Помощь студентам | 0 | 20.04.2012 15:49 |
сортировка массива | feras | Общие вопросы Delphi | 6 | 23.05.2011 09:56 |
Сортировка массива методами предсортировки и слияния, и пирамидальная сортировка. | lenny_24 | Помощь студентам | 2 | 17.04.2011 18:57 |
Сортировка массива | Paladast | Помощь студентам | 2 | 18.01.2010 16:28 |
Сортировка массива | Paul_AG | Общие вопросы C/C++ | 16 | 05.06.2009 21:42 |