[Amicus Plato]

Дорогие участники сообщества!
Жизнь некоторые дневниковые глюки распорядились так, что многие участники помимо воли стали и постоянными читателями )))
Разрешите поприветствовать вас в этой ипостаси, а также, помимо этого, напомнить отписаться назад, если вы не хотите читать записи сообщества из френдленты.
А в качестве бонуса картинка.
Сегодня я об этом (в частности) рассказывала на лекции.
Сортировка массива методом пузырька.



И заодно вопрос.
Умом я понимаю, что сложность этого алгоритма О(n²).
Но он ведь работает быстрее метода простого перебора?
Так ведь?
А у перебора тоже О(n²)!
В чем тут собака зарыта?

@темы: Техническая запись, Вопросы

Comments

[Disprein]

Картинка хороша)
А что за метод простого перебора? Или это тот, который в нашем курсе называется методом простого выбора: ищем максимальный элемент и ставим в начало, затем ищем в оставшейся части максимальный и ставим на второе место, и так далее? Так он вроде бы не медленнее. Такой же.

Вообще простые методы сортировки (имеющие квадратичную сложность) работают примерно с одинаковой скоростью.
Могут быть различия из-за различий в реализации, но в целом количество сравнений и перестановок будет примерно одинаковым.

Хотя из равенства порядков сложности, конечно, не следует равенство самой сложности.

Кстати, «быстрая» сортировка, имеющая сложность О(n log n), на маленьких массивах работает медленнее, чем тот же «пузырек». Все за счет константы, которая прячется за это самое О.

[Dieter Zerium]

Amicus Plato
а что за упорядочивание элементов? Ранжирование(вариационный ряд) ?

[Amicus Plato]

Dieter Zerium
нет, не вариационный ряд )))
Просто есть одномерный массив (вектор).
Нужно упорядочить его элементы по возрастанию (убыванию).
Есть море разных алгоритмов для этого!

[Amicus Plato]

Disprein
Ну, да: простого выбора )))
Он и не медленнее, но ведь на картинке очень красиво видно, как все элементы стягиваются к "аттрактору". А при выборе никто никуда не стягивается. Просто один элемент ставится на место.
А выходит разницы никакой.
На самом-то деле они и отличаются всего-то другой направленностью внешнего цикла (и сравниваемыми элементами))

А вот еще одна красивая картинка:
Быстрый алгоритм с применением рекурсий.
Очень интересный!

вот он.

[Amicus Plato]

А для вариационного ряда (в смысле в промежуточном вычислении получается вар. ряд) есть алгоритм линейной сложности!!!
Это фантастика!

[Dieter Zerium]

Amicus Plato
наверное, простой перебор - это как типичная школьная задачка о сравнении трёх чисел (только тут больше трёх) ?

[Amicus Plato]

Dieter Zerium
из трех чисел обычно находят минимальное (максимальное), а здесь задача такая, что нужно все три расставить по местам))
То есть выполнить на одно действие больше (для случая трех чисел)

[Dieter Zerium]

Amicus Plato
Но тогда можно находить максимальные, минимальные, потом постепенно отсекать их, и заново провести процедуру определения макс/мин?))

[Amicus Plato]

Dieter Zerium
ну да, это и есть самый "базовый" алгоритм ))))

[Dieter Zerium]

Amicus Plato
)))))