Форум программистов, компьютерный форум, киберфорум
Pascal ABC
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.85/26: Рейтинг темы: голосов - 26, средняя оценка - 4.85
31 / 31 / 23
Регистрация: 23.03.2015
Сообщений: 210
1

Какой способ сортировки одномерного массива самый быстрый?

28.03.2015, 18:14. Показов 4959. Ответов 15
Метки нет (Все метки)

Нужно написать программу как можно очень быстро сортирующую одномерный массив из 1000 элементов
Какой способ сортировки одномерного массива самый быстрый?

Знаю что самая быстрая "Быстрая сортировка",а "Пузырьковая медленная" но тут проблема:
Пузырьковая сортировка работающая из тела программа(без функции/процедуры) занимает в среднем 0000700 мск.
Быстрая сортировка т.к она работает через рекурсию и без функции ее не напишешь. Занимает 0004500 мск (вызов даже пустой функции занимает много времени).
Так какую сортировку использовать?
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.03.2015, 18:14
Ответы с готовыми решениями:

минимальный и самый простой способ сортировки массива
Вот минимальный и самый простой способ сортировк массива. Кто ни бдь может сказать более короткий?...

Определить самый большой* отрицательный (т.е. максимум близко к нулю) элемент одномерного массива
Ребята, помогите мне пожалуйста написать программы! Я вообще в этом ниче не понимаю! ...

Использование пирамидальной сортировки одномерного массива.
Вот оригинальный текст задачи: Дан одномерный массив. Отсортировать все четные элементы по...

Разработать программу сортировки одномерного массива.
Описать алгоритм сортировки массива данных. Метод включения и тип символьный. Дублирование тем...

15
Модератор
Эксперт функциональных языков программированияЭксперт Python
30461 / 16831 / 3464
Регистрация: 12.02.2012
Сообщений: 28,199
Записей в блоге: 5
28.03.2015, 20:54 2
Цитата Сообщение от 0x0152 Посмотреть сообщение
Нужно написать программу как можно очень быстро сортирующую одномерный массив из 1000 элементов
- а что известно про эти числа? Их тип и величина? И есть ли в массиве какой-либо порядок?
0
Модератор
8679 / 4336 / 2976
Регистрация: 17.08.2012
Сообщений: 13,803
28.03.2015, 22:11 3
Цитата Сообщение от 0x0152 Посмотреть сообщение
Быстрая сортировка т.к она работает через рекурсию и без функции ее не напишешь
Это почему ещё обязательно через рекурсию? Есть и итерационная реализация этого алгоритма. Числа какие? Может, поразрядную сортировку применить? В зависимости от вида чисел и размера массива поразрядная сортировка может быть быстрее быстрой.
0
31 / 31 / 23
Регистрация: 23.03.2015
Сообщений: 210
29.03.2015, 10:07  [ТС] 4
Числа случайные.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
30461 / 16831 / 3464
Регистрация: 12.02.2012
Сообщений: 28,199
Записей в блоге: 5
29.03.2015, 10:12 5
Цитата Сообщение от 0x0152 Посмотреть сообщение
Числа случайные.
- из какого диапазона? Чтобы получить случайное целое, обычно умножают rnd на некое N. Тогда все числа будут в диапазоне [0,N]. Если N << 1000, то самый быстрый способ - сортировка подсчетом!
0
Модератор
8679 / 4336 / 2976
Регистрация: 17.08.2012
Сообщений: 13,803
29.03.2015, 10:31 6
Я не корректно выразился, а Вы немного не поняли. Это всё равно, какова природа чисел, по мне их пусть хоть гоблин наколдовал. Интересует формат чисел, их машинное представление: integfer, real, double, extended... Вообще говоря, количество двоичных разрядов каждого числа и назначение этих разрядов.

Добавлено через 11 минут
Catstail, это я не Вам. И да, для перечисляемых типов - подсчётом самая быстрая сортировка. А при современных объёмах RAM самое главное, чтобы массив для подсчёта в память влез. Так что N - хоть миллион. Ну, если компилятор только позволит такого калибра динамический массив создать...
0
31 / 31 / 23
Регистрация: 23.03.2015
Сообщений: 210
29.03.2015, 11:45  [ТС] 7
Тип чисел integer;

Странно но если замерять через
Pascal
1
2
3
4
 var t:=new stopwatch();
  t.Start); 
  t.stop(); 
 console.WriteLine(t.elapsed);
То пузырек сортирует быстрее
А если замерять через функцию
Milliseconds
То быстрая сортировка показывает лучший результат.
Почему они показывают разный результат?
0
Модератор
8679 / 4336 / 2976
Регистрация: 17.08.2012
Сообщений: 13,803
29.03.2015, 11:57 8
Ага, уже кое-что. В Pascal ABC integer занимает 4 байта. То есть, понадобится всего 32 прохода поразрядной сортировки по массиву. Ну а, если диапазон чисел ограничен, так и вовсе 2 прохода сортировки подсчётом. Быстрая сортировка нервно курит в сторонке.

Цитата Сообщение от 0x0152 Посмотреть сообщение
Почему они показывают разный результат?
Не знаю. Все вопросы к создателям pascal ABC.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
30461 / 16831 / 3464
Регистрация: 12.02.2012
Сообщений: 28,199
Записей в блоге: 5
29.03.2015, 17:15 9
Цитата Сообщение от 0x0152 Посмотреть сообщение
Тип чисел integer;
- а диапазон? Из тебя информацию приходится как на допросе вытягивать...

Цитата Сообщение от 0x0152 Посмотреть сообщение
То пузырек сортирует быстрее. А если замерять через функцию Milliseconds, То быстрая сортировка показывает лучший результат. Почему они показывают разный результат?
- тут еще важна методика измерения. Если однократная сортировка, то это ненадежно. Лучше отсортировать в цикле 200-300 раз.
0
Модератор
8679 / 4336 / 2976
Регистрация: 17.08.2012
Сообщений: 13,803
29.03.2015, 18:03 10
Цитата Сообщение от Catstail Посмотреть сообщение
тут еще важна методика измерения
Нет, Catstail, всё гораздо более плохо.

Да, 0x0152, через Milliseconds результат обязан быть более верным, поскольку используется системное время. Только всё равно все Ваши эти измерения некорректны, ввиду того, что современные операционные системы многозадачные, и будет посчитано в том числе и время, которое отводится операционной системой под себя, любимую, и другие запущенные задачи. И прибавка эта - совершенно случайная величина. В трее у Вас как, чистенько, даже часиков и переключателя языка нету? А диспетчер задач запустить, что, неужто ни одного процесса не выполняется? То-то и оно. Для того, чтобы измерение было верным, в первую голову требуется, чтобы Ваша программа использовала аппаратные ресурсы компьютера монопольно. То есть, нужно запустить программу из-под DOS, к примеру. И безо всяких там интерпретаторов, то есть, Pascal ABC совершенно для измерения времени выполнения алгоритма не подходит.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
30461 / 16831 / 3464
Регистрация: 12.02.2012
Сообщений: 28,199
Записей в блоге: 5
29.03.2015, 18:11 11
Цитата Сообщение от Cyborg Drone Посмотреть сообщение
И безо всяких там интерпретаторов, то есть, Pascal ABC совершенно для измерения времени выполнения алгоритма не подходит.
- нужно четко разобраться... Не подходит почему? Если результаты разных измерений "пляшут", то их нужно усреднить.
0
Модератор
8679 / 4336 / 2976
Регистрация: 17.08.2012
Сообщений: 13,803
29.03.2015, 18:49 12
Catstail, Pascal ABC - интерпретатор, а не транслятор, я же написал. Он не создаёт исполняемого файла. То есть, запускаешь Pascal ABC, указываешь ему паскалевский файл, и Pascal ABC построчно его переводит даже не в ассемблер, а в свой, одному ему известный, псевдокод, и построчно интерпретирует, чего там надо делать, и это и делает. Грубо говоря, во всех остальных диалектах паскаля, кроме этого уродца ABC, у которого ещё и ампутированы многие возможности, происходит трансляция текста программы в машинные инструкции (создаётся исполняемый файл .exe, .com, .elf да мало ли какой, но запустить это дело уже можно без самого паскаля), а в ABC ничего такого нет, ни во что он текст программы не транслирует, а просто интерпретирует сам текст программы, и выполняет его построчно. Грубо говоря, ABC - это просто парсер такой.

Добавлено через 13 минут
В многозадачной среде результаты измерения обязаны быть завышенными, поскольку, как я писал, часть времени операционная система отдаёт другим запущенным задачам, которых, как правило, много. То есть, операционная система передаёт управление другой задаче, целевая программа останавливается, сколько там будет выполняться другая задача, только операционке и известно. А время тикает. А программа стоит. И исключить время простоя не удастся, поскольку в операционной системе это не предусмотрено, и даже ей не вполне известно, например, время переключения между задачами, и время, на сколько той или иной задаче удастся монопольно захватить аппаратные ресурсы. И о каком корректном измерении может идти речь? Хоть обусредняйся, результат будет завышен, возможно, в сотни или тысячи раз.

Добавлено через 6 минут
На самоь деле, можно вычислить точное время исполнения того или иного алгоритма. Получаем исполняемый файл (а лучше - ассемблерный листинг), и по известному времени выполнения ассемблерных инструкций можно вычислить скорости выполнения алгоритмов. Вот это уже будет корректно, с точностью до тактовой частоты процессора. Ну и, ещё раз повторюсь, ABC никак не подходит, поскольку никакого исполняемого файла или ассемблерного листинга породить не может.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
30461 / 16831 / 3464
Регистрация: 12.02.2012
Сообщений: 28,199
Записей в блоге: 5
29.03.2015, 19:01 13
Не хочется затевать длинный спор... Но какую роль играет то, что код интерпретируется? Да, интерпретация медленна. Но QickSort и в интерпретируемом виде будет работать быстрее "пузырька" на тех же данных. Производительность алгоритма зависит от числа необходимых операций. Для QickSort это в среднем n*log2n, а для "пузырька" - n2

Что же до того, что во время исполнения входят и затраты на многозадачность, то их можно учесть с помощью метода наименьших квадратов (многократно повторяя тесты).
0
Модератор
8679 / 4336 / 2976
Регистрация: 17.08.2012
Сообщений: 13,803
29.03.2015, 19:16 14
Catstail, не учесть многозадачность ну никак. Что можно намерить, если во время исполнения целевой программы в неё вклиниваются ещё несколько программ? Вот, к примеру, на моей весьма аскетичной системе сейчас запущено 3 программы и работают 35 процессов. И это у меня, старого кэмела. Судя по аватару, я немногим Вас моложе. А что говорить об компьютере юного студиозуса, у которого в трее не как у меня, только часы и антивирус, а ещё гора всяких ненужных фитюлек, да ещё и тяжеловесный рабочий стол с кучей гаджетов? Никакой метод усреднения не поможет. Для данного случая можно с уверенностью сказать, что время, отводимое операционкой на эти все фитюльки (даже если запустить на моём компьютере, с минимумом фитюлек), существенно превосходит время выполнения всей целевой программы.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
30461 / 16831 / 3464
Регистрация: 12.02.2012
Сообщений: 28,199
Записей в блоге: 5
29.03.2015, 20:01 15
Цитата Сообщение от Cyborg Drone Посмотреть сообщение
можно с уверенностью сказать, что время, отводимое операционкой на эти все фитюльки (даже если запустить на моём компьютере, с минимумом фитюлек), существенно превосходит время выполнения всей целевой программы.
- у меня XP. Полтора десятка процессов. Если не прикасаться к клавиатуре - загрузка ЦП 0%. Уж никак не превосходит время сортировки. Не понимаю, о чем Вы.
0
Модератор
8679 / 4336 / 2976
Регистрация: 17.08.2012
Сообщений: 13,803
29.03.2015, 20:31 16
Хорошо, почти согласен. И у меня 0%, хотя windows врёт, как всегда, конечно.

Помнится, давно писал программу с перебором пары миллионов вариантов, ну, насчёт ABC не знаю, никогда себе эту гадость не поставлю, однако, исполняемый файл (компилятор был Turbo Pascal) под виндами выполнялся секунд двадцать, а под досом - мгновенно. Ну, навскидку, четверть секунды.

Но всё ж Вы правы. Можно оценить время работы, только, думаю, не методом наименьших квадратов всё-таки, так время всё же может быть завышено, а многократным прогоном программы при одних и тех же данных, и считать за время исполнения минимальное время одного прогона. Потому что и код, и данные - одни и те же, следовательно, минимальное время с достаточной достоверностью можно принять за истинное время выполнения.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.03.2015, 20:31

Алгоритм сортировки одномерного массива по возрастанию
8. Алгоритм сортировки одномерного массива по возраста- нию.

Разработать процедуру сортировки одномерного массива по возрастанию
№4 Разработать процедуру сортировки одномерного массива по возрастанию. Разработать программу...

Нужны примеры сортировки одномерного и двумерного массива
Дайте лёгие примеры сортировки одномерного и двумерного массива

Разработать подпрограмму сортировки одномерного массива по убыванию
Ребят, помогите пожалуйста.. Кто чем может, заранее спасибо. Очень надо. 20. Задача на...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru