Насчёт методов сортировки, может ли такое быть?

amdbodia, 398 просмотров

Я написал программу для измерения работы разных методов сортировки.
Проблема в том, что меня пугают результаты.
Если, к примеру, сортировка пузырьком 100000 элементов занимает 95 секунд, то сортировка методом Шелла занимает всего 0,1 секунды. Я запускал кучу проверок, все показывают что всё правильно. Могут ли такие результаты быть правильными?

Примечание:
Код пузырька:

int bubbles (long *a, long n, double &del)
{
long i,j,s;
double start, finish;
long long numbb=0; del=0;
start = (double) clock();
for (i=n;i>0;i--)
{
s=0;
for (j=0;j<i;j++)
{
if (a[j]>a[j+1])
{
SWAP (a[j],a[j+1]);
s++; numbb++;
}
}
if (!s)
break;
}
finish = (double) clock();
del = (double) (finish-start)/CLOCKS_PER_SEC;
cout<<"\nNumber of operations: "<<numbb;
return 0;
}

Дело в том, что и если сравнивать с улучшенным методом вставки, то всё-равно очень большая разница получается.

Примечание:
Да, при 100000 элементах так и получается. Просто дело в том, что если поделить 10 миллиардов на 30 миллионов, то получается 333. А у меня если разделить 2 времени - больше 700. Неожиданный результат, конечно..

Ответы:

Каракуль

А покажите код пузырька. Слишком много для 100000, кажется.

Максим Новиков

На 100000 элементах мне это видется вполне реально.
Попробуйте уменьшить кол-во элементов, и разница не станет столь ощутимой.

Каракуль

Так и есть.
У меня те же самые результаты.

Каракуль

По сложности алгоритмов получается так:
пузырёк 10млрд. проходов.
шелл 31 млн. в худшем случае.

Артёмка

Не понимаю, что странного?
Сложность пузырьковой сортировки - O(n^2), сортировки Шелла - О(nlogn). О(n^2) означает (утрированно), что существуют константы C1, C2 такие, что
С1 * n^2 < количество атомарных действий < C2 * n^2.
Аналогично для О(nlogn).
Не понимаю, откуда взяли числа 10 миллиардов и 30 миллионов. И смысл удивляться, что сортировка Шелла на больших массивах работает гораздо быстрее пузырьковой?

Каракуль

> Просто дело в том, что если поделить 10 миллиардов на 30 миллионов, то получается 333
30 миллионов - это худший случай. (n^1.5)
Лучший случай - 1.7 млн. (n^1.25)
Т.е. в среднем где-то (очень грубо) 16 млн., вот это соответствует вашему времени.
10млрд. / 16млн. = 625 раз.
95с. / 625 раз = 0.152 с.
Похоже? :)

Каракуль

Это, конечно же, просто грубый расчёт.
Он никак не соответствует действительности.
Просто я хотел показать, что 95с и 0.1с это нормальное время, чтобы не было сомнений.

16 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.