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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
EnotikN
0 / 0 / 0
Регистрация: 11.07.2013
Сообщений: 14
#1

Функция сортировки - C++

14.07.2013, 20:02. Просмотров 1086. Ответов 14
Метки нет (Все метки)

Здравствуйте,коллеги! Подскажите какую-нибудь функцию сортировки с наименьшим количеством операций сравнения. В общем необходимо сравнить около тысячи элементов, sort занимает много времени. Просто каждая секунда играет роль. Заранее спасибо

Добавлено через 2 минуты
Может кому-то приходилось сталкиваться с такой проблемой. И у кого-то есть код
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.07.2013, 20:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Функция сортировки (C++):

Функция сортировки - C++
День добрый, пишу сортировку чисел, столкнулся с проблемой, комментирую в коде: #include <iostream> using namespace std; ...

Функция сортировки - C++
Здравствуйте, у меня есть функция, которая должна сортировать массив сначала по одному параметру, а потом по другому, для структуры....

Функция сортировки - C++
А ваше есть ли функция для сортировки массива, если да то как ей пользоваться ?

Функция сортировки массива - C++
Необходимо написать функцию сортировки массива структур с информацией по книгам по возрастанию года издания и возвращающую отсортированный...

Не работает функция сортировки - C++
void Sort(char path) { Rect *MyRect = new Rect ; //дин массив Rect temp; //буффер int k = 0,x1,y1,x2,y2; //вершины...

Функция сортировки и поиска - C++
Ужасная функция...неделю бился так ничего и не смог придумать...Само условие поставленное в задаче звучит так: "Написать алгоритм,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Jetu
касаткО
51 / 51 / 1
Регистрация: 01.10.2011
Сообщений: 227
15.07.2013, 11:41 #2
Здесь описаны все более менее известные сортировки. Посмотрите, поизучайте. И да, чуть не забыл:
а) что вы сортируете ?
б) что вы подразумеваете под "много времени" ?
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
16.07.2013, 19:53 #3
Цитата Сообщение от EnotikN Посмотреть сообщение
В общем необходимо сравнить около тысячи элементов
Так тут даже пузырьком можно засортить, раз ограничения настолько мелкие.
0
valik35
1 / 1 / 0
Регистрация: 17.07.2013
Сообщений: 29
17.07.2013, 01:39 #4
опишите что сортируете
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
17.07.2013, 07:29 #5
1 000 - это на столько мало, что даже по худшему алгоритму уйдут сотни микросекунд. Может проблема не в сравнениях, а в тёжлых перестановках?
1
EnotikN
0 / 0 / 0
Регистрация: 11.07.2013
Сообщений: 14
17.07.2013, 23:13  [ТС] #6
Просто это происходит в реальном времени и в течении минимум десяти минут. Например, зона обзора РЛС, представляет собой набор ячеек с информацией и все время необходимо их сравнивать.
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.07.2013, 15:08 #7
А машина какая? Тактовая частота, средняя такность операций с кешем, размер кеша, частота шины, тайминги оперативы, размер одного элемента. И ещё, какую долю процессорного времени, можно выделить на сортировку с учётом того, что паралельно надо делать ещё что то и по какому алгоритму выполняется отдельное сравнение. Доли миллисекунды и 10 минут на столько несопоставимы, что возникают сомнения в том, что проблема кроется именно в алгоритме верхнего уровня.
1
Dmitriy_M
1349 / 1230 / 114
Регистрация: 20.03.2009
Сообщений: 4,420
Записей в блоге: 11
18.07.2013, 18:11 #8
EnotikN, а что показывает профилировщик?
Для сортировок основанных на сравнениях предел http://www.cyberforum.ru/cgi-bin/latex.cgi?O\left(n\log \left( {n} \right)\right) , у std::sort именно такая характеристика.
1
EnotikN
0 / 0 / 0
Регистрация: 11.07.2013
Сообщений: 14
18.07.2013, 20:49  [ТС] #9
taras atavin, к сожалению описать алгоритм верхнего уровня не могу, так как это секрет. Могу лишь только сказать, что при сравнении до 80 элементов, алгоритм работает нормально. При большей загруженности начинает затыкаться.

Dmitriy_M, вроде еще функция mergesort имеет такую характеристику

Добавлено через 11 минут
Jetu, Сортирую ячейки с информацией по степени важности
0
Dmitriy_M
1349 / 1230 / 114
Регистрация: 20.03.2009
Сообщений: 4,420
Записей в блоге: 11
18.07.2013, 21:05 #10
EnotikN, merge sort, heap sort, quick sort, и т.д. Какая из них быстрее можно узнать только прогонкой тестов. Так же при анализе не учитывается стоимость сравнения ключей.
Погоняй в VTune, им можно бесплатно пользоваться 30 дней. Если Проект пишется под nix системой, то прогони под valgrind, и посмотри граф вызовов на повторное вычисление одних и тех же данных, и введи кеширование.
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.07.2013, 21:14 #11
Цитата Сообщение от EnotikN Посмотреть сообщение
при сравнении до 80 элементов
Значит тормозит либо свап, либо сравнение. На 80 элементах сортировка вообще не особо важна.
Лучше скажите, что именно сортируется. Вернее, какой размер у ваших ячеек, как они сравниваются и как свапаются.
1
EnotikN
0 / 0 / 0
Регистрация: 11.07.2013
Сообщений: 14
18.07.2013, 21:31  [ТС] #12
Dmitriy_M, спасибо вам большое



Добавлено через 3 минуты
diagon, жаль,что не могу привести управляющий алгоритм. Писала статьи по этому поводу, но что-то в интернете найти её не могу.
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
18.07.2013, 21:38 #13
Цитата Сообщение от EnotikN Посмотреть сообщение
taras atavin, к сожалению описать алгоритм верхнего уровня не могу, так как это секрет. Могу лишь только сказать, что при сравнении до 80 элементов, алгоритм работает нормально. При большей загруженности начинает затыкаться.
Проблема врядли в нём. А вот алгоритм сравнения не помешает.
1
EnotikN
0 / 0 / 0
Регистрация: 11.07.2013
Сообщений: 14
18.07.2013, 21:48  [ТС] #14
taras atavin, попробую сортировку mergesort. Спасибо вам
0
Зосима
23.07.2013, 07:10     Функция сортировки
  #15

Не по теме:

Спинным мозгом чувствую, что тут под элементом подразумевается не число, а матрица чисел типа double, размера эдак 100x100

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2013, 07:10
Привет! Вот еще темы с ответами:

Функция сортировки матрицы - C++
Функция сортировки матрицы по убыванию элементов 1 строки

Функция сортировки массива - C++
Дан массив целых чисел. Напишите функцию, которая получает данный массив в качестве аргумента и сортирует его по возрастанию, а также...

Функция сортировки массива - C++
Задание - необходимо осуществить сортировку, используя функцию. Я написал код, но он не работает. Прошу помочь его исправить. ...

Функция сортировки вектора и списка - C++
Добрый день, помогите пожалуйста) Суть задания в том, что нужно написать функцию сортировки (Одну!) сразу для вектора и списка без...


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

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

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