void merge(int A[],int p,int q,int r)
{
int j = p ,k = q + 1 ,i = p;
while ((j <= q)&&(k <= r)) {
if ( A[j]<A[k] ) {
B=A[j];
j++;
}
else{
B=A[k];
k++;
}
i++;
}
if (j==q+1) {
for (j=k;j<=r;++j){
B[i++]=A[j];
}
}
else {
for (j=j;j<=q;++j){
B[i++]=A[j];
}
}
for (int d=p;d<=r;++d)
A[d]=B[d];
}
void merge_sort(int A[],int p,int r)
{
if (p<r) {
int q = (p+r)/2;
merge_sort(A,p,q);
merge_sort(A,q+1,r);
merge(A,p,q,r);
}
}
Алгоритмы сортировки
Привет!
Кто знает, какой метод сортировки одномерного массива целых чисел самый быстрый?
Кто знает, какой метод сортировки одномерного массива целых чисел самый быстрый?
Цитата:
Originally posted by inspector_jul
Привет!
Кто знает, какой метод сортировки одномерного массива целых чисел самый быстрый?
Привет!
Кто знает, какой метод сортировки одномерного массива целых чисел самый быстрый?
qsort() из стандартной библиотеки C.
А ещё почитайте Кнута. Он обещает приз тому, кто придумает алгоритм, не описанный в его книге :D
qsort() как сказано выше, но у него проблема - в худшем случае сложность а-ля "пузырек" еще есть "пирамидальная" сортировка, она вобщем менее быстрая, но более устойчивая.
лучшие результаты у быстрой сортировки Хоара, в 1,5 раза медленнее сортировка пирамидой, метод Шелла в 2 раза хуже. Прямые методы сортировки хуже в 100 и более раз. <Б. С. Хусаинов>
Для данного массива лучше всего сортировка Хоара. Хотя qsort - это какой-то улучшенный метод сортировки! При равновероятном распределении чисел общее число сравнений равно n*log2n, общее число обменов (n*log2n)/6. Удачи!
Для данного массива лучше всего сортировка Хоара. Хотя qsort - это какой-то улучшенный метод сортировки! При равновероятном распределении чисел общее число сравнений равно n*log2n, общее число обменов (n*log2n)/6. Удачи!
Все это - полный бред. Скорость зависит от упорядоченности масива до сортировки, поэтому в одних случаях сортировка Хоара оказывается быстрее, в других - пирамидальная. По-моему для целых чисел, если речь идет не про длинную арифметику лучше использовать поразрядную сортировку (если есть лишняя память, конечно :)).
2 MIKE247: вот в том то и проблема, что в критической ситуации Хоара (она же qsort, она же быстрая) даст n^2, зависит от конкретной задачи... имхо сабж надо конкретизировать... если надо сортировать гектар чисел, то юзаем пирамидку - и стабильно и быстро, если маленький массив то и правда поразрядную надо делать. быстрая где-то посередине. все это конечно имхо, но вроде не подводило.
а еще вопрос по теме: нужна хорошая сортировка для структур со строковыми полями, размер структур порядка сотни байт, естеснно отдельная функция сравнения (с указанием поля по которому сравниваем). Количество структур - де-то миллион - полмиллиона... тут же ставится вопрос - чего быстрее: сравнить две строки или просваппить 2 пары строк в памяти?
а еще вопрос по теме: нужна хорошая сортировка для структур со строковыми полями, размер структур порядка сотни байт, естеснно отдельная функция сравнения (с указанием поля по которому сравниваем). Количество структур - де-то миллион - полмиллиона... тут же ставится вопрос - чего быстрее: сравнить две строки или просваппить 2 пары строк в памяти?
Цитата:
Originally posted by stoman
2 MIKE247: вот в том то и проблема, что в критической ситуации Хоара (она же qsort, она же быстрая) даст n^2, зависит от конкретной задачи... имхо сабж надо конкретизировать... если надо сортировать гектар чисел, то юзаем пирамидку - и стабильно и быстро, если маленький массив то и правда поразрядную надо делать. быстрая где-то посередине. все это конечно имхо, но вроде не подводило.
а еще вопрос по теме: нужна хорошая сортировка для структур со строковыми полями, размер структур порядка сотни байт, естеснно отдельная функция сравнения (с указанием поля по которому сравниваем). Количество структур - де-то миллион - полмиллиона... тут же ставится вопрос - чего быстрее: сравнить две строки или просваппить 2 пары строк в памяти?
2 MIKE247: вот в том то и проблема, что в критической ситуации Хоара (она же qsort, она же быстрая) даст n^2, зависит от конкретной задачи... имхо сабж надо конкретизировать... если надо сортировать гектар чисел, то юзаем пирамидку - и стабильно и быстро, если маленький массив то и правда поразрядную надо делать. быстрая где-то посередине. все это конечно имхо, но вроде не подводило.
а еще вопрос по теме: нужна хорошая сортировка для структур со строковыми полями, размер структур порядка сотни байт, естеснно отдельная функция сравнения (с указанием поля по которому сравниваем). Количество структур - де-то миллион - полмиллиона... тут же ставится вопрос - чего быстрее: сравнить две строки или просваппить 2 пары строк в памяти?
Реализация qsort оставляет желать лучшего. Собственная реализация метода даже рекурсивным алгоритмом будет работать в 2 раза быстрее.
Цитата:
Originally posted by Envel
Реализация qsort оставляет желать лучшего.
Реализация qsort оставляет желать лучшего.
Вы знакомы с реализацией qsort() на всех распростаненных компиляторах?
Что-то я сильно сомневаюсь в этом.
Цитата:
Originally posted by pacific_7
Вы знакомы с реализацией qsort() на всех распростаненных компиляторах?
Что-то я сильно сомневаюсь в этом.
Вы знакомы с реализацией qsort() на всех распростаненных компиляторах?
Что-то я сильно сомневаюсь в этом.
Что-то по-моему компиляторы сортировкой не занимаются.
Цитата:
Originally posted by Dart Bobr
Что-то по-моему компиляторы сортировкой не занимаются.
Что-то по-моему компиляторы сортировкой не занимаются.
Гы-гы! Пошутил?! :)
Занимаются, если ковыряться глубже, но это не по теме.
Стандартные функции (напр. qsort()) присутствуют во всех компиляторах, и выполняют они одни и те же действия - согласно стандарту которому соответсвует компилер, а возможно и сверх его. Да только вот во всех софтовых компаниях работают абсолютно разные люди, которые абсолютно по разному решают одну и ту же задачу, например - реализацию алгоритма сортировки Хоара. Отсюда и разница в эффективности работы одной и той же функции (и программы вообще) при сборке на различных компиляторах.
Цитата:
Originally posted by pacific_7
Гы-гы! Пошутил?! :)
Гы-гы! Пошутил?! :)
Абсолютно согласен с pacific_7! Просто потому что столкнулся. Применял быструю сортировку (рекурсия, самая простенькая реализация), так вот условия: 100000 элементов, сортировка по строкам (есть еще по int'ам, но там ужо очен бодро ;)))
1) стандартный компилятор Cи Visual Studio .NET на полной оптимизации ~ 2:05 мин
2) Intel CPP Compiler 8.1.024 на полной же оптимизации (SSE естесно не включал) ~ 1:40 мин
Как видите разница все-таки есть - 20%, а ведь при сортировке поллимона структур (для VC.NET это где то будет 30 минут) это составит 6 минут, вообще даже в количественном выражении нехило.
Гм, а зачем собственно компилятору сортировка? По-моему можно и без нее. Задача компилятора - преобразование в машинный код (вроде и без сортировки обойтись). Стоп, стоп, стоп. Этапы компиляции -
-лексический анализ
-синтаксический анализ
-генерация промежуточного кода
-оптимизация кода
На каком этапе интересно же нужна сортировка целых чисел? И для чего?
Вся разница во времени выполнения скорее всего из-за плохой (или хорошей) оптимизации кода. Это мое ИМХО, поэтому поправьте если где-то не прав.
-лексический анализ
-синтаксический анализ
-генерация промежуточного кода
-оптимизация кода
На каком этапе интересно же нужна сортировка целых чисел? И для чего?
Вся разница во времени выполнения скорее всего из-за плохой (или хорошей) оптимизации кода. Это мое ИМХО, поэтому поправьте если где-то не прав.
Цитата:
Originally posted by stoman
Абсолютно согласен с pacific_7!
Абсолютно согласен с pacific_7!
"Прежде чем начинать разговор, нужно договориться о терминологии" (С)
Стандартная библиотека (stdlib) может быть написанан даже на ассемблере и поставляться отдельно от компилятора. Тут дело в самой реализации qsort, где необходимо передавать указатель на функцию, осуществляющую сравнение. Если убрать этот вызов, должно получиться быстрее. Данные по большей части взяты из книги "Теория и практика С++" (Г. Шилдт) и собственного опыта.
p.s. в книге используются компиляторы vc++5 и bc++5 (не уверен точно) и поставляемые с ними stdlib.
Цитата:
Originally posted by Envel
Тут дело в самой реализации qsort, где необходимо передавать указатель на функцию, осуществляющую сравнение. Если убрать этот вызов, должно получиться быстрее.
Тут дело в самой реализации qsort, где необходимо передавать указатель на функцию, осуществляющую сравнение. Если убрать этот вызов, должно получиться быстрее.
Согласен, но тогда теряем универсальность.
Для частного случая это конечно будет лучше, при одном не маленьком "но" - нужно суметь написать действительно быстрый код. Т.е. посоревноваться с программистами MS и Borland к примеру. При наличии сободного времени - вперед и с песней ;)
Цитата:
Originally posted by Dart Bobr
Гм, а зачем собственно компилятору сортировка?
На каком этапе интересно же нужна сортировка целых чисел? И для чего?
Гм, а зачем собственно компилятору сортировка?
На каком этапе интересно же нужна сортировка целых чисел? И для чего?
Про сортировку целых чисел в компиляторе, никто и не говорил. Имелась ввиду сортировка в общем.
При оптимизации кода точно применяется, но я думаю, что это не единственный случай.
Цитата:
Originally posted by pacific_7
Согласен, но тогда теряем универсальность.
Для частного случая это конечно будет лучше, при одном не маленьком "но" - нужно суметь написать действительно быстрый код.
Согласен, но тогда теряем универсальность.
Для частного случая это конечно будет лучше, при одном не маленьком "но" - нужно суметь написать действительно быстрый код.
Универсальность не теряется. Уточню, что в книге используются шаблоны (template, средство языка С++).
О том, какой плохой код пишут программисты MS я слышал, а о том, какой плохой код написал Г. Шилдт - думаю, даже вы не слышали. Он привел код с использованием шаблонов и сравнил время его выполнения, разница была примерно до 2-х раз. Вот и все. Что вы спорит? Лучше возьмите первоисточник и прочитайте (глава "Шаблоны") или сами попробуйте.
Цитата:
Originally posted by Envel
(template, средство языка С++).
(template, средство языка С++).
Спабибо, без вас я бы никогда не узнал, как называются шаблоны в С++ :)
Цитата:
Originally posted by Envel
О том, какой плохой код пишут программисты MS я слышал,
О том, какой плохой код пишут программисты MS я слышал,
Ну, это тема избитая и многосторонняя.
Цитата:
Originally posted by Envel
а о том, какой плохой код написал Г. Шилдт - думаю, даже вы не слышали. Он привел код с использованием шаблонов и сравнил время его выполнения, разница была примерно до 2-х раз. Вот и все. Что вы спорит?
а о том, какой плохой код написал Г. Шилдт - думаю, даже вы не слышали. Он привел код с использованием шаблонов и сравнил время его выполнения, разница была примерно до 2-х раз. Вот и все. Что вы спорит?
Да ни кто собственно и не спорит. Просто выражаю свое мнение.
Можно поподробнее про сравнения - я чего-то не понял: с чем Шилдт сравнил код использующий шаблоны - этой книжки Шилдта у меня нет, есть только по Си (понятно, что там шаблонов быть не может). Буду очень благодарен, если разъясните - интересно.
Цитата:
Originally posted by pacific_7
Спабибо, без вас я бы никогда не узнал, как называются шаблоны в С++ :)
Ну, это тема избитая и многосторонняя.
Да ни кто собственно и не спорит. Просто выражаю свое мнение.
Можно поподробнее про сравнения - я чего-то не понял: с чем Шилдт сравнил код использующий шаблоны - этой книжки Шилдта у меня нет, есть только по Си (понятно, что там шаблонов быть не может). Буду очень благодарен, если разъясните - интересно.
Спабибо, без вас я бы никогда не узнал, как называются шаблоны в С++ :)
Ну, это тема избитая и многосторонняя.
Да ни кто собственно и не спорит. Просто выражаю свое мнение.
Можно поподробнее про сравнения - я чего-то не понял: с чем Шилдт сравнил код использующий шаблоны - этой книжки Шилдта у меня нет, есть только по Си (понятно, что там шаблонов быть не может). Буду очень благодарен, если разъясните - интересно.
Брррр... найдите первоисточник и прочитайте. Он сравнивает работу qsort (стандартную библиотечную функцию) по сортировке массива целых (10000) с работой собственно написанной функции, реализации того же алгоритма быстрой сортировки, но с использованием механизма шаблонов. Предлагает небольшую тестовую программку сортировки этих 10000 случайно сгенерированных одинаковых массивов, пишет, что время выполнения с использованием qsort почти в 2 раза больше, чем при использовании собственной функции.
насколько я помню, неплохая была сортировка рекурсией... для 100000 элементов работала быстрее стандартной, при этом со стеком всё в порядке было..
принцип основан на том что массив считается отсортированным (не важно как), если он не отсортирован, то разбивается на 2 и для каждой части выполняется последующая проверка на отсортированность, а потом функция слияния двух отсортированных массивов в один... на последних шагах рекурсии очевидно что сливаются в один массив из 2х значений два некоторых значения, потом рекурсия возвращается вверх, и сливаются уже такие пары и т. д... сложность алгоритма насколько я помню была nlogn...
з.ы. готовый код есть...
з.з.ы. я не претендую что это самый оптимальный метод.. просто даю тему для размышлений )))))
принцип основан на том что массив считается отсортированным (не важно как), если он не отсортирован, то разбивается на 2 и для каждой части выполняется последующая проверка на отсортированность, а потом функция слияния двух отсортированных массивов в один... на последних шагах рекурсии очевидно что сливаются в один массив из 2х значений два некоторых значения, потом рекурсия возвращается вверх, и сливаются уже такие пары и т. д... сложность алгоритма насколько я помню была nlogn...
з.ы. готовый код есть...
з.з.ы. я не претендую что это самый оптимальный метод.. просто даю тему для размышлений )))))
В таком случае нецелесообразно измерять скорость роботы алгоритма в секундах, а только в количествах сравнений и перемещений (по крайней мере Кнут делает так :)). А про быстрый код так это - чистый асм с оптимизацией соответствующей.
И вот,.. в очередной раз мы наблюдаем как некто изобретает велосипед, но сперва пару вопросов:
Цитата:
Originally posted by Mr.Hacker
принцип основан на том что массив считается отсортированным (не важно как), если он не отсортирован, то разбивается на 2
принцип основан на том что массив считается отсортированным (не важно как), если он не отсортирован, то разбивается на 2
Каким интересно образом? От балды?
Цитата:
Originally posted by Mr.Hacker
и для каждой части выполняется последующая проверка на отсортированность,
и для каждой части выполняется последующая проверка на отсортированность,
Каким методом?
Цитата:
Originally posted by Mr.Hacker
сложность алгоритма насколько я помню была nlogn...
сложность алгоритма насколько я помню была nlogn...
Ага, верно. А еще наверно, среднее количество обменов равно n/6 log n?
И наконец, собственно велосипед:
Цитата:
Originally posted by Mr.Hacker
з.з.ы. я не претендую что это самый оптимальный метод.. просто даю тему для размышлений )))))
з.з.ы. я не претендую что это самый оптимальный метод.. просто даю тему для размышлений )))))
Боюсь, что Чарьльз Хоар немого опередил вас в размышлениях (на нескольо десятков лет ;)) Именно его агоритм описан выше (правда довольно-таки коряво), эта сортировка реализуется в большинстве случаев через рекурсию и именно она реализована во всех Си компиляторах в виде библиотечной функции qsort().
ЗЫ:
Цитата:
Originally posted by Mr.Hacker
насколько я помню, неплохая была сортировка рекурсией
насколько я помню, неплохая была сортировка рекурсией
Впервые слышу, что рекурсия - это вид сортировки.
ЗЫЗЫ: если я где-то неправ, или что-то не так понял, то исправьте, всегда готов извиниться.
рекурсия здесь не метод сортировки, а метод, при помощи которого сортировка выполняется... рабочий код:
merge сливается 2 отсортированных массива в один.. merge_sort сама сортировка... вызывается она как merge_sort(A, 0, n-1) где n-1 размерность... рабочий откомпиленный вариант так же имеется...
з.ы. палками не бейте... я реализация стандартной сортировки не знаю, так что если она такая же - не бить )))
Код:
merge сливается 2 отсортированных массива в один.. merge_sort сама сортировка... вызывается она как merge_sort(A, 0, n-1) где n-1 размерность... рабочий откомпиленный вариант так же имеется...
з.ы. палками не бейте... я реализация стандартной сортировки не знаю, так что если она такая же - не бить )))