Неустойчивость пузырьковой сортировки

← →
antonn © (2007-09-16 15:39) [40]

> Если в процессе сортировки два элемента будут оказываться
> вечно в разных местах, то это может повлиять на дальнейшие
> результаты

ну так и надо проводить с учетом вторичных данных, по нужному элементу то оно все верно делает. зачем себе проблему придумывать?

← →
boa_kaa © (2007-09-16 15:43) [41]

> antonn © (16.09.07 15:39) [40]

Хорошо. Изменяю пример.

TMyClass = class
public
x: Integer;
end;

TMyClass2 = class(TMyClass)
public
y: Integer;
end;

Сортировка реализована для TMyClass. Как теперь?

← →
antonn © (2007-09-16 15:47) [42]

без понятия. нужно выбрать тот метод сортировки, который удовлетворяет параметрам поиска, а не ругать пузырек за то, что он недопузырек %)

← →
boa_kaa © (2007-09-16 15:56) [43]

> antonn © (16.09.07 15:47) [42]
> без понятия. нужно выбрать тот метод сортировки, который
> удовлетворяет параметрам поиска, а не ругать пузырек за
> то, что он недопузырек %)

согласен. Но вот прошло мимо ушей и получаем трудноотлавливаемую багу.

← →
iZEN © (2007-09-16 18:02) [44]

> boa_kaa © (16.09.07 15:25) [39]
>
> Как это устойчивость неважна?
>
> TMyClass = class
> public
> x, y: Integer;
> end;
>
> Есть список, в котором будет два экземпляра с одинаковыми
> y ( по которому проводится сортировка и разными x.

Сортировка проводится по определённому ключу. Если в состав ключа (составной ключ по y&x) входит x, то оно будет учитываться. Если в состав ключа x не входит (ключ по y), то и не надо его учитывать при сортировке.

Нестабильность того или иного алгоритма сортировки означает, что операция обмена одинаковых элементов (элементов, имеющих одинаковый ключ) не исключается. Так я понял. Это лишнее машинное время. Поэтому и существуют два разных варианта алгоритма сортировки, вернее, даже три варианта:

1) оптимизированный, когда алгоритм прекращает свою работу сразу после того, как обнаружит, что не было произведено ни одного обмена элементов во внутреннем цикле;

2) общий алгоритм пузырьковой сортировки, когда алгоритм доконца выполняет внешний цикл, несмотря на то, что во внутреннем цикле операций обмена элементов не производилось -- это детерминированный алгоритм, время выполнения которого прямо зависит от количества элементов;

3) нестабильный алгоритм -- в нём во внутреннем цикле обмениваются даже одинаковые элементы; впрочем, он может так же быть оптимизированным, как алгоритм из п.1.

← →
iZEN © (2007-09-16 18:06) [45]

нестабильность == неустойчивость

← →
DillerXX © (2007-09-16 21:13) [46]

Когда-то давно, ещё во времена Делфи (для олимпиадников) в России, когда большинство людей ещё не знало, что такое STL, Станкевич на открытом кубке CBOSS дал задачу, где нужно было отсортировать массив по какому-то ключу, но не изменять расположение элементов при равном ключе. Так как задача была халявная, и по размерам данных проходила квадратичная сортировка, все быстро написали пузырёк, и быстро получили Wrong Answer. Короче, только пара "везунчиков" сдала эту задачу, остальные искали подвох в условии или в его понимании. Вот так... потом уже на разборе Станкевич сказал о том, что пузырёк то является нестабильным (по крайней мере его реализация, которую все написали), и именно это было использовано в задаче.

← →
Sha © (2007-09-16 21:34) [47]

> DillerXX © (16.09.07 21:13) [46]

Если не затруднит, приведи ту реализацию, которую все написали

← →
palva © (2007-09-17 12:02) [48]

DillerXX © (16.09.07 21:13) [46]
потом уже на разборе Станкевич сказал о том, что пузырёк то является нестабильным
А зачем вы это пишете? Для вас высказывание авторитета перевешивает ваш здравый смысл? Вы сами-то понимаете, что Станкевич сморозил глупость? Или вы считаете, что Станкевич прав?

в теории нету неустойчивости
А вот exe может работать неустойчиво :)

Нет, в эту ветку я больше не зайду. Опасаюсь за свой моск.

> palva (17.09.2007 12:40:50) [50]

Какой то ты слабо приспособленный, надо тренироваться, а для этого надо заходить

Неустойчивость пузырьковой сортировки Найти похожие ветки