Всем доброе время суток!
Меня заинтересовали методы сортировка элементов, пусть даже массивов. Я знаю только один метод "метод пузырька", где мы в цикле сравниваем какой из элементов больше или меньше и в соответствии условием переставляем их местами. Мне кажется, что такая сортировка очень долгая, будут замечаться тормоза, если будет большое количества элементов.
Какие бывают еще методы и как они работают? Какие методы считаются быстрыми?

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%B2%D0%BA%D0%B8


Такого понятия как "самый быстрый алгоритм сортировки" не существует, их сравнивают по разным критериям. Например сложность алгоритма в худшем случае (worst-case). Некоторые алгоритмы хорошо подходят для параллельного выполнения.. в общем все зависит.

Метод пузырька далеко не самый медленный и не самый простой. Проще и, как правило, медленнее метод попарной перестановки.

Вообще же скорость сортировки больше всего зависит от исходной расстановки элементов. В каком-то варианте та же попарная перестановка сработает быстрее всех.

Метод пузырька (камня) в одной из двух возможных реализаций и есть метод попарной перестановки.


http://algolist.manual.ru/sort/index.php

Отнюдь. 

Метод попарной перестановки, в его классическом варианте, заключается в тупом проходе по всему массиву данных с последовательной проверкой каждой пары соседей. При необходимости пара соседей меняется местами. Цикл прерывается после прохода, в котором ни одна пара местами поменена не была. При всей своей тупости, алгоритм обладает неоспоримым преимуществом: у программы самый простой код: один цикл, один флаг, одна дополнительная переменная. Его легко объяснять студентам нетехнических специальностей  

В методе пузырька каждый элемент по очереди "всплывает" в массиве до того, как найдет свое место. Осуществлено всплывание может быть как попарными перестановками (что не есть хорошо), так и сдвигом блока элементов в массиве: поэлементно или всем блоком (конечно, если синтаксис конкретного языка допускает такой  сдвиг блока). 

Это сообщение отредактировал(а) _Y_ - 13.2.2011, 00:08

Вы забываете, что на каждом проходе длина прохождения уменьшается на 1. Или это уж слишком тупая реализация. Так что получается тот же камень-пузырёк.

Сначала хотел написать "ну Вы меня удивляете!". Потом подумал "а не дурак ли я?". Или неправильно алгоритм простейший расписал? Действительно, в описании пузырькового алгоритма написал "...всплывание может быть как попарными перестановками (что не есть хорошо)..." думал так будет понятнее. Надо понимать этим все и запутал.
 
Вот блок-схема алгоритма попарной перестановки:

Действительно, последний элемент в нем гарантированно занимает свое место с первого прохода, со второго прохода - два последних элемента, и т.д. Т.е. вполне логично укорачивать цикл по ходу дела.

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

В результате сдвиг элемента на M позиций требует в одном варианте 3*M присвоений (попарная перестановка), а в другом только M+2 (камень/пузырек). А если язык позволяет двигать блоки в массиве, то и того лучше - два присвоения и сдвиг блока.

Однако, здесь есть один нюанс. Начальная расстановка элементов в сортируемом массиве определяет сколь велик выигрыш от применения пузырька. Чем короче сдвигаемые за один раз блоки, тем меньше выигрыш.

Это сообщение отредактировал(а) _Y_ - 13.2.2011, 19:04

Обалдеть, я уже думал, что об этом никто не помнит...

А дырки в перфокартах глазами читать слабо?  

C перфокартами не работал. А вот перфоленты - ещё как...