|
|
|
Регистрация Восстановить пароль |
|||||||
| Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
||||
 |
|
|
Опции темы | Поиск в этой теме |
02.06.2010, 22:49
|
#1 |
|
Новичок
Джуниор
Регистрация: 02.06.2010
Сообщений: 1
|
Алгоритм сортировки
есть множество обьектов скажем например штук 1000
есть некая функция которая сортирует 10-ь обьектов по спаду. Нужно раставить обьекты в множестве по мере спада. решение есть: 1.берем первые 10, определяем какой из них последний 2. на его место ставим 11 элемент и опять определяем последний обьект .. 3. повторяем пункт 2 пока не дойдем до конца так мы определим первый обьект.. откидываем его, а с оставшимися обьектами проводим все по пунктам 1,2,3.. Те элементы что откидывали образуют отсортированное множество. При таком алгоритме количество обращений к функции сортировки ~1милион Подскажите пожалуйста алгоритм при котором число обращений к функции сортировки было минимальным. |
|
|
|
03.06.2010, 10:03
|
#2 |
|
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
А нельзя сделать функцию которая вместо 10 элементов сортирует их произвольное количество. Тогда обращение к функции будет всего 1 раз
 .
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика
|
|
|
|
|
03.06.2010, 13:58
|
#3 | |
|
Старожил
Регистрация: 20.04.2008
Сообщений: 5,542
|
Цитата:
сортирум(10..19) максимальный с предыдущего шага и девять новых сортируем(19..28) .. за m/9 шагов знаем последний возвращаемся к началу итого результат N *(N/9) шагов смотрим (1..10). уже отсортировано (1..8) (9..10) поэтому начинаем сортируем (8..17) (17..26)(26..35)...
программа — запись алгоритма на языке понятном транслятору
|
|
|
|
|
|
03.06.2010, 16:11
|
#4 |
|
Форумчанин
Регистрация: 12.05.2010
Сообщений: 219
|
Может быть поможет: сортировка методом "пузырька"
1)сравниваем первый объект и второй, если второй больше, меняем их местами 2)сравниваем первый (текущий) и третий, если третий больше. меняем их местами и т.д., потом 3)сравниваем второй и третий, если третий больше - меняем местами до тех пор,пока не сравним 9 и 10 объекты. Получаем отсортированные по спаду 10 элементов. В итоге мы на каждом шаге выбираем максимальное из двух значений. а не из 10. Всего операций сравнения для сортировки 10 объектов 45 |
|
|
|
|
Похожие темы
|
||||
| Тема | Автор | Раздел | Ответов | Последнее сообщение |
| Алгоритм сортировки строк в Memo | Toha_88 | Помощь студентам | 4 | 29.04.2010 14:20 |
| алгоритм сортировки «вставкой» | curly182 | Помощь студентам | 2 | 19.10.2009 22:56 |
| Алгоритм сортировки по категориям | retail_ret | PHP | 8 | 11.08.2009 00:06 |
| Алгоритм сортировки одномерного массива | JOFRIF | Общие вопросы C/C++ | 4 | 19.07.2009 17:23 |
