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

@0x0152 · Регистрация: 23.03.2015

Author24 — интернет-сервис помощи студентам

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

Знаю что самая быстрая "Быстрая сортировка",а "Пузырьковая медленная" но тут проблема:
Пузырьковая сортировка работающая из тела программа(без функции/процедуры) занимает в среднем 0000700 мск.
Быстрая сортировка т.к она работает через рекурсию и без функции ее не напишешь. Занимает 0004500 мск (вызов даже пустой функции занимает много времени).
Так какую сортировку использовать?

@Catstail · 28.03.2015, 20:54

Сообщение от 0x0152

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

- а что известно про эти числа? Их тип и величина? И есть ли в массиве какой-либо порядок?

@Cyborg Drone · 28.03.2015, 22:11

Сообщение от 0x0152

Быстрая сортировка т.к она работает через рекурсию и без функции ее не напишешь

Это почему ещё обязательно через рекурсию? Есть и итерационная реализация этого алгоритма. Числа какие? Может, поразрядную сортировку применить? В зависимости от вида чисел и размера массива поразрядная сортировка может быть быстрее быстрой.

@0x0152 · 29.03.2015, 10:07 **[ТС]**

Числа случайные.

@Catstail · 29.03.2015, 10:12

Сообщение от 0x0152

Числа случайные.

- из какого диапазона? Чтобы получить случайное целое, обычно умножают rnd на некое N. Тогда все числа будут в диапазоне [0,N]. Если N << 1000, то самый быстрый способ - сортировка подсчетом!

@Cyborg Drone · 29.03.2015, 10:31

Я не корректно выразился, а Вы немного не поняли. Это всё равно, какова природа чисел, по мне их пусть хоть гоблин наколдовал. Интересует формат чисел, их машинное представление: integfer, real, double, extended... Вообще говоря, количество двоичных разрядов каждого числа и назначение этих разрядов.

Добавлено через 11 минут
Catstail, это я не Вам. И да, для перечисляемых типов - подсчётом самая быстрая сортировка. А при современных объёмах RAM самое главное, чтобы массив для подсчёта в память влез. Так что N - хоть миллион. Ну, если компилятор только позволит такого калибра динамический массив создать...

@0x0152 · 29.03.2015, 11:45 **[ТС]**

Тип чисел integer;

Странно но если замерять через

Pascal

 var t:=new stopwatch();
  t.Start); 
  t.stop(); 
 console.WriteLine(t.elapsed);

То пузырек сортирует быстрее
А если замерять через функцию
Milliseconds
То быстрая сортировка показывает лучший результат.
Почему они показывают разный результат?

@Cyborg Drone · 29.03.2015, 11:57

Ага, уже кое-что. В Pascal ABC integer занимает 4 байта. То есть, понадобится всего 32 прохода поразрядной сортировки по массиву. Ну а, если диапазон чисел ограничен, так и вовсе 2 прохода сортировки подсчётом. Быстрая сортировка нервно курит в сторонке.

Сообщение от 0x0152

Почему они показывают разный результат?

Не знаю. Все вопросы к создателям pascal ABC.

@Catstail · 29.03.2015, 17:15

Сообщение от 0x0152

Тип чисел integer;

- а диапазон? Из тебя информацию приходится как на допросе вытягивать...

Сообщение от 0x0152

То пузырек сортирует быстрее. А если замерять через функцию Milliseconds, То быстрая сортировка показывает лучший результат. Почему они показывают разный результат?

- тут еще важна методика измерения. Если однократная сортировка, то это ненадежно. Лучше отсортировать в цикле 200-300 раз.

@Cyborg Drone · 29.03.2015, 18:03

Сообщение от Catstail

тут еще важна методика измерения

Нет, Catstail, всё гораздо более плохо.

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

@Catstail · 29.03.2015, 18:11

Сообщение от Cyborg Drone

И безо всяких там интерпретаторов, то есть, Pascal ABC совершенно для измерения времени выполнения алгоритма не подходит.

- нужно четко разобраться... Не подходит почему? Если результаты разных измерений "пляшут", то их нужно усреднить.

@Cyborg Drone · 29.03.2015, 18:49

Catstail, Pascal ABC - интерпретатор, а не транслятор, я же написал. Он не создаёт исполняемого файла. То есть, запускаешь Pascal ABC, указываешь ему паскалевский файл, и Pascal ABC построчно его переводит даже не в ассемблер, а в свой, одному ему известный, псевдокод, и построчно интерпретирует, чего там надо делать, и это и делает. Грубо говоря, во всех остальных диалектах паскаля, кроме этого уродца ABC, у которого ещё и ампутированы многие возможности, происходит трансляция текста программы в машинные инструкции (создаётся исполняемый файл .exe, .com, .elf да мало ли какой, но запустить это дело уже можно без самого паскаля), а в ABC ничего такого нет, ни во что он текст программы не транслирует, а просто интерпретирует сам текст программы, и выполняет его построчно. Грубо говоря, ABC - это просто парсер такой.

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

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

@Catstail · 29.03.2015, 19:01

Не хочется затевать длинный спор... Но какую роль играет то, что код интерпретируется? Да, интерпретация медленна. Но QickSort и в интерпретируемом виде будет работать быстрее "пузырька" на тех же данных. Производительность алгоритма зависит от числа необходимых операций. Для QickSort это в среднем n*log₂n, а для "пузырька" - n²

Что же до того, что во время исполнения входят и затраты на многозадачность, то их можно учесть с помощью метода наименьших квадратов (многократно повторяя тесты).

@Cyborg Drone · 29.03.2015, 19:16

Catstail, не учесть многозадачность ну никак. Что можно намерить, если во время исполнения целевой программы в неё вклиниваются ещё несколько программ? Вот, к примеру, на моей весьма аскетичной системе сейчас запущено 3 программы и работают 35 процессов. И это у меня, старого кэмела. Судя по аватару, я немногим Вас моложе. А что говорить об компьютере юного студиозуса, у которого в трее не как у меня, только часы и антивирус, а ещё гора всяких ненужных фитюлек, да ещё и тяжеловесный рабочий стол с кучей гаджетов? Никакой метод усреднения не поможет. Для данного случая можно с уверенностью сказать, что время, отводимое операционкой на эти все фитюльки (даже если запустить на моём компьютере, с минимумом фитюлек), существенно превосходит время выполнения всей целевой программы.

@Catstail · 29.03.2015, 20:01

Сообщение от Cyborg Drone

можно с уверенностью сказать, что время, отводимое операционкой на эти все фитюльки (даже если запустить на моём компьютере, с минимумом фитюлек), существенно превосходит время выполнения всей целевой программы.

- у меня XP. Полтора десятка процессов. Если не прикасаться к клавиатуре - загрузка ЦП 0%. Уж никак не превосходит время сортировки. Не понимаю, о чем Вы.

@Cyborg Drone · 29.03.2015, 20:31

Хорошо, почти согласен. И у меня 0%, хотя windows врёт, как всегда, конечно.

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

Но всё ж Вы правы. Можно оценить время работы, только, думаю, не методом наименьших квадратов всё-таки, так время всё же может быть завышено, а многократным прогоном программы при одних и тех же данных, и считать за время исполнения минимальное время одного прогона. Потому что и код, и данные - одни и те же, следовательно, минимальное время с достаточной достоверностью можно принять за истинное время выполнения.

@Cyborg Drone Модератор 9871 / 5239 / 3306 Регистрация: 17.08.2012 Сообщений: 16,007
	29.03.2015, 19:16	14
	Catstail, не учесть многозадачность ну никак. Что можно намерить, если во время исполнения целевой программы в неё вклиниваются ещё несколько программ? Вот, к примеру, на моей весьма аскетичной системе сейчас запущено 3 программы и работают 35 процессов. И это у меня, старого кэмела. Судя по аватару, я немногим Вас моложе. А что говорить об компьютере юного студиозуса, у которого в трее не как у меня, только часы и антивирус, а ещё гора всяких ненужных фитюлек, да ещё и тяжеловесный рабочий стол с кучей гаджетов? Никакой метод усреднения не поможет. Для данного случая можно с уверенностью сказать, что время, отводимое операционкой на эти все фитюльки (даже если запустить на моём компьютере, с минимумом фитюлек), существенно превосходит время выполнения всей целевой программы. 0

@0x0152 31 / 31 / 23 Регистрация: 23.03.2015 Сообщений: 210
		1
	Какой способ сортировки одномерного массива самый быстрый? 28.03.2015, 18:14. Показов 6169. Ответов 15 Метки нет (Все метки) Нужно написать программу как можно очень быстро сортирующую одномерный массив из 1000 элементов Какой способ сортировки одномерного массива самый быстрый? Знаю что самая быстрая "Быстрая сортировка",а "Пузырьковая медленная" но тут проблема: Пузырьковая сортировка работающая из тела программа(без функции/процедуры) занимает в среднем 0000700 мск. Быстрая сортировка т.к она работает через рекурсию и без функции ее не напишешь. Занимает 0004500 мск (вызов даже пустой функции занимает много времени). Так какую сортировку использовать? 0

@Catstail Модератор 36601 / 20330 / 4220 Регистрация: 12.02.2012 Сообщений: 33,644 Записей в блоге: 13
	28.03.2015, 20:54	2
	Сообщение от 0x0152 Нужно написать программу как можно очень быстро сортирующую одномерный массив из 1000 элементов - а что известно про эти числа? Их тип и величина? И есть ли в массиве какой-либо порядок? 0

@Cyborg Drone Модератор 9871 / 5239 / 3306 Регистрация: 17.08.2012 Сообщений: 16,007
	28.03.2015, 22:11	3
	Сообщение от 0x0152 Быстрая сортировка т.к она работает через рекурсию и без функции ее не напишешь Это почему ещё обязательно через рекурсию? Есть и итерационная реализация этого алгоритма. Числа какие? Может, поразрядную сортировку применить? В зависимости от вида чисел и размера массива поразрядная сортировка может быть быстрее быстрой. 0

@0x0152 31 / 31 / 23 Регистрация: 23.03.2015 Сообщений: 210
	29.03.2015, 10:07 [ТС]	4
	Числа случайные. 0

@Catstail Модератор 36601 / 20330 / 4220 Регистрация: 12.02.2012 Сообщений: 33,644 Записей в блоге: 13
	29.03.2015, 10:12	5
	Сообщение от 0x0152 Числа случайные. - из какого диапазона? Чтобы получить случайное целое, обычно умножают rnd на некое N. Тогда все числа будут в диапазоне [0,N]. Если N << 1000, то самый быстрый способ - сортировка подсчетом! 0

@Cyborg Drone Модератор 9871 / 5239 / 3306 Регистрация: 17.08.2012 Сообщений: 16,007
	29.03.2015, 10:31	6
	Я не корректно выразился, а Вы немного не поняли. Это всё равно, какова природа чисел, по мне их пусть хоть гоблин наколдовал. Интересует формат чисел, их машинное представление: integfer, real, double, extended... Вообще говоря, количество двоичных разрядов каждого числа и назначение этих разрядов. Добавлено через 11 минут Catstail, это я не Вам. И да, для перечисляемых типов - подсчётом самая быстрая сортировка. А при современных объёмах RAM самое главное, чтобы массив для подсчёта в память влез. Так что N - хоть миллион. Ну, если компилятор только позволит такого калибра динамический массив создать... 0

@Cyborg Drone Модератор 9871 / 5239 / 3306 Регистрация: 17.08.2012 Сообщений: 16,007
	29.03.2015, 11:57	8
	Ага, уже кое-что. В Pascal ABC integer занимает 4 байта. То есть, понадобится всего 32 прохода поразрядной сортировки по массиву. Ну а, если диапазон чисел ограничен, так и вовсе 2 прохода сортировки подсчётом. Быстрая сортировка нервно курит в сторонке. Сообщение от 0x0152 Почему они показывают разный результат? Не знаю. Все вопросы к создателям pascal ABC. 0

@Catstail Модератор 36601 / 20330 / 4220 Регистрация: 12.02.2012 Сообщений: 33,644 Записей в блоге: 13
	29.03.2015, 17:15	9
	Сообщение от 0x0152 Тип чисел integer; - а диапазон? Из тебя информацию приходится как на допросе вытягивать... Сообщение от 0x0152 То пузырек сортирует быстрее. А если замерять через функцию Milliseconds, То быстрая сортировка показывает лучший результат. Почему они показывают разный результат? - тут еще важна методика измерения. Если однократная сортировка, то это ненадежно. Лучше отсортировать в цикле 200-300 раз. 0

@Cyborg Drone Модератор 9871 / 5239 / 3306 Регистрация: 17.08.2012 Сообщений: 16,007
	29.03.2015, 18:03	10
	Сообщение от Catstail тут еще важна методика измерения Нет, Catstail, всё гораздо более плохо. Да, 0x0152, через Milliseconds результат обязан быть более верным, поскольку используется системное время. Только всё равно все Ваши эти измерения некорректны, ввиду того, что современные операционные системы многозадачные, и будет посчитано в том числе и время, которое отводится операционной системой под себя, любимую, и другие запущенные задачи. И прибавка эта - совершенно случайная величина. В трее у Вас как, чистенько, даже часиков и переключателя языка нету? А диспетчер задач запустить, что, неужто ни одного процесса не выполняется? То-то и оно. Для того, чтобы измерение было верным, в первую голову требуется, чтобы Ваша программа использовала аппаратные ресурсы компьютера монопольно. То есть, нужно запустить программу из-под DOS, к примеру. И безо всяких там интерпретаторов, то есть, Pascal ABC совершенно для измерения времени выполнения алгоритма не подходит. 0

@Catstail Модератор 36601 / 20330 / 4220 Регистрация: 12.02.2012 Сообщений: 33,644 Записей в блоге: 13
	29.03.2015, 18:11	11
	Сообщение от Cyborg Drone И безо всяких там интерпретаторов, то есть, Pascal ABC совершенно для измерения времени выполнения алгоритма не подходит. - нужно четко разобраться... Не подходит почему? Если результаты разных измерений "пляшут", то их нужно усреднить. 0

	29.03.2015, 20:31

@Cyborg Drone Модератор 9871 / 5239 / 3306 Регистрация: 17.08.2012 Сообщений: 16,007
	29.03.2015, 18:49	12
	Catstail, Pascal ABC - интерпретатор, а не транслятор, я же написал. Он не создаёт исполняемого файла. То есть, запускаешь Pascal ABC, указываешь ему паскалевский файл, и Pascal ABC построчно его переводит даже не в ассемблер, а в свой, одному ему известный, псевдокод, и построчно интерпретирует, чего там надо делать, и это и делает. Грубо говоря, во всех остальных диалектах паскаля, кроме этого уродца ABC, у которого ещё и ампутированы многие возможности, происходит трансляция текста программы в машинные инструкции (создаётся исполняемый файл .exe, .com, .elf да мало ли какой, но запустить это дело уже можно без самого паскаля), а в ABC ничего такого нет, ни во что он текст программы не транслирует, а просто интерпретирует сам текст программы, и выполняет его построчно. Грубо говоря, ABC - это просто парсер такой. Добавлено через 13 минут В многозадачной среде результаты измерения обязаны быть завышенными, поскольку, как я писал, часть времени операционная система отдаёт другим запущенным задачам, которых, как правило, много. То есть, операционная система передаёт управление другой задаче, целевая программа останавливается, сколько там будет выполняться другая задача, только операционке и известно. А время тикает. А программа стоит. И исключить время простоя не удастся, поскольку в операционной системе это не предусмотрено, и даже ей не вполне известно, например, время переключения между задачами, и время, на сколько той или иной задаче удастся монопольно захватить аппаратные ресурсы. И о каком корректном измерении может идти речь? Хоть обусредняйся, результат будет завышен, возможно, в сотни или тысячи раз. Добавлено через 6 минут На самоь деле, можно вычислить точное время исполнения того или иного алгоритма. Получаем исполняемый файл (а лучше - ассемблерный листинг), и по известному времени выполнения ассемблерных инструкций можно вычислить скорости выполнения алгоритмов. Вот это уже будет корректно, с точностью до тактовой частоты процессора. Ну и, ещё раз повторюсь, ABC никак не подходит, поскольку никакого исполняемого файла или ассемблерного листинга породить не может. 0

@Catstail Модератор 36601 / 20330 / 4220 Регистрация: 12.02.2012 Сообщений: 33,644 Записей в блоге: 13
	29.03.2015, 19:01	13
	Не хочется затевать длинный спор... Но какую роль играет то, что код интерпретируется? Да, интерпретация медленна. Но QickSort и в интерпретируемом виде будет работать быстрее "пузырька" на тех же данных. Производительность алгоритма зависит от числа необходимых операций. Для QickSort это в среднем n*log₂n, а для "пузырька" - n² Что же до того, что во время исполнения входят и затраты на многозадачность, то их можно учесть с помощью метода наименьших квадратов (многократно повторяя тесты). 0

@Catstail Модератор 36601 / 20330 / 4220 Регистрация: 12.02.2012 Сообщений: 33,644 Записей в блоге: 13
	29.03.2015, 20:01	15
	Сообщение от Cyborg Drone можно с уверенностью сказать, что время, отводимое операционкой на эти все фитюльки (даже если запустить на моём компьютере, с минимумом фитюлек), существенно превосходит время выполнения всей целевой программы. - у меня XP. Полтора десятка процессов. Если не прикасаться к клавиатуре - загрузка ЦП 0%. Уж никак не превосходит время сортировки. Не понимаю, о чем Вы. 0