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

← →
me (2007-09-16 01:34) [0]

вычитал такое в одной книге, но это же полная ерунда?!

← →
Johnmen © (2007-09-16 01:38) [1]

Название, автор, год издания, ISN?

← →
me (2007-09-16 01:41) [2]

Джулиан Баккнелл Алгоритмы и структуры данных на Delphi

← →
Johnmen © (2007-09-16 01:42) [3]

Неустойчивость в чём?

← →
me (2007-09-16 01:45) [4]

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

← →
Kerk © (2007-09-16 01:47) [5]

> [4] me (16.09.07 01:45)

Какая разница, если они одинаковые?

← →
Johnmen © (2007-09-16 01:47) [6]

> me (16.09.07 01:45) [4]

Это абсолюно, я подчёркиваю, АБСОЛЮТНО, не имеет никакого значения!

← →
me (2007-09-16 01:48) [7]

я не про это
я про то что пузырьковая сортировка устойчива!
а уж нужна это устойчивость кому-то или нет сейчас не обсуждается)

← →
DrPass © (2007-09-16 01:49) [8]

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

Ну, допустим. Если это мы назовем "неустойчивость сортировки", тогда да, метод пузырька будет "неустойчивым". Если бы мы это назвали "заковыристость сортировки", тогда метод пузырька был бы заковыристым. С этим немеренно полезным знанием можешь ложиться спать :)

← →
Германн © (2007-09-16 01:53) [9]

Ну вот ещё одна белиберда свалилась на форум. :)
Один ляпнул или его "так перевели Промптом", другой зацепился взглядом за ляп и вынес его в форум.
Бред, одним словом :(

← →
me (2007-09-16 01:53) [10]

DrPass © (16.09.07 01:49) [8]
почему неустойчивый-то?
вот есть элементы 1 1
будет одно сравнение и (а оно строгое) не будет переставлены элементы
приведите пример где будет изменение расположение

← →
me (2007-09-16 01:54) [11]

Германн © (16.09.07 01:53) [9]
просто книга авторитетная...и я даже в себе засомневался)

← →
DrPass © (2007-09-16 01:54) [12]

> я про то что пузырьковая сортировка устойчива!

А вот это не факт

← →
Германн © (2007-09-16 01:55) [13]

> приведите пример где будет изменение расположение
>

А какая, блин, разница будет изменено или нет? См. Kerk © (16.09.07 01:47) [5]

← →
me (2007-09-16 01:56) [14]

DrPass © (16.09.07 01:54) [12]
факт факт)

причины реально в книге, я ей так доверял....

← →
Германн © (2007-09-16 02:34) [15]

> причины реально в книге, я ей так доверял....
>

Попробуй, если сможешь, прочитать её в оригинале. Если сможешь, может и вопросов не будет?
:)

← →
wicked © (2007-09-16 04:07) [16]

такое понятие, как "устойчивость сортировки", ИМЕЕТ ЗНАЧЕНИЕ
поскольку функция сортировки можеть сортировать элементы массива/списка по одному из признаков и не принимать в внимание другие свойства

соответственно, БУДУТ случаи, когда нам может понадобиться именно стабильность сортировки - "одинаковые" с т. з. алгоритма сортировки элементы НЕ ДОЛЖНЫ переставляться
в STL для этого есть, соответственно, sort и stable_sort

насколько мне кажется, стабильность "классического" пузырька будет зависеть от условия сравнения элементов - при строгом "меньше" он будет стабильным, при "меньше или равно" - гарантированно нестабильным
хотя здесь я могу ошибаться

← →
iZEN © (2007-09-16 04:57) [17]

> wicked © (16.09.07 04:07) [16]
>
> насколько мне кажется, стабильность "классического" пузырька
> будет зависеть от условия сравнения элементов - при строгом
> "меньше" он будет стабильным, при "меньше или равно" - гарантированно
> нестабильным
> хотя здесь я могу ошибаться

В таком случае можно рассмотреть "оптимизированную" версию алгоритма "пузырька", когда внешний цикл досрочно прерывается, если во внутреннем цикле не было ни одной перестановки -- все элементы отсортированы ДО полного сравнения пар.

Но и в этом случае я не вижу "нестабильности". В чём она выражается, можете объяснить?

← →
me (2007-09-16 05:00) [18]

насколько мне кажется, стабильность "классического" пузырька будет зависеть от условия сравнения элементов - при строгом "меньше" он будет стабильным, при "меньше или равно" - гарантированно нестабильным
хотя здесь я могу ошибаться

вот именно
а в книге ровно наоборот

← →
me (2007-09-16 05:05) [19]

iZEN © (16.09.07 04:57) [17]
ну если сравнение нестрогое то будут переставляться и одинаковые элементы
тогда и оптимизация будет невыполнима

← →
jack128_ (2007-09-16 11:30) [20]

Вариант ошибки переводчика не рассматриваем??

← →
Sha © (2007-09-16 11:43) [21]

У автора на сайте, помнится, был спмсок неточностей.
Проверь, есть ли там твой случай. Если нет - пиши автору.
Любой человек имеет право на ашипку.

← →
Anatoly Podgoretsky © (2007-09-16 12:05) [22]

> me (16.09.2007 01:48:07) [7]

Есть реализации устойчивые и нет.

← →
Anatoly Podgoretsky © (2007-09-16 12:06) [23]

> Kerk (16.09.2007 01:47:05) [5]

С чего ты взял, что одинаковые, одинаковый только ключ сортировки.

← →
Anatoly Podgoretsky © (2007-09-16 12:06) [24]

> me (16.09.2007 01:53:10) [10]

if B >= A then

← →
Anatoly Podgoretsky © (2007-09-16 12:07) [25]

> me (16.09.2007 01:54:11) [11]

А переводчик авторитетный и с какого языка он переводил с английского или американского.

← →
Anatoly Podgoretsky © (2007-09-16 12:07) [26]

> Германн (16.09.2007 01:55:13) [13]

Бальшая

← →
Sha © (2007-09-16 14:08) [27]

> Anatoly Podgoretsky © (16.09.07 12:07) [25]
> А переводчик авторитетный и с какого языка он переводил с английского или американского.

Сверил перевод и оригинал.
Перевод верный. Похоже ошибка в оригинале.

← →
Anatoly Podgoretsky © (2007-09-16 14:16) [28]

> Sha (16.09.2007 14:08:27) [27]

Приведи выписку из оригинала.

← →
Sha © (2007-09-16 14:24) [29]

Listing 5.4: Bubble sort

procedure TDBubbleSort(aList : TList; aFirst : integer; aLast : integer; aCompare : TtdCompareFunc); var i, j : integer; Temp : pointer; Done : boolean; begin TDValidateListRange(aList, aFirst, aLast, "TDBubbleSort"); for i := aFirst to pred(aLast) do begin Done := true; for j := aLast downto succ(i) do if (aCompare(aList.List^[j], aList.List^[j-1]) < 0) then begin {swap jth and (j-1)th elements} Temp := aList.List^[j]; aList.List^[j] := aList.List^[j-1]; aList.List^[j-1] := Temp; Done := false; end; if Done then Exit; end; end;

Bubble sort is a O(n2) algorithm. There are two loops in the algorithm, one
inside the other, and the length of each depends on the number of items. The
first cycle through the first loop will do n-1 comparisons, the second n-2, the
third n-3, and so on. There are n-1 cycles in all, so the total number of comparisons
is
(n-1) + (n-2) + : + 1
which simplifies to n(n-1)/2, or (n2-n)/2. In other words, O(n2). The number
of swaps is a little more difficult to calculate, but in the worst case (the items
were originally in reverse order), there will be the same number of swaps as
comparisons, so again O(n2).
The small optimization mentioned above does mean that if the original list
was sorted, bubble sort is very fast: it just makes one pass through the list,
finds out that no swaps are needed, and stops. (n-1) comparisons and no
swaps indicate a O(n) algorithm in this case.
One big problem with bubble sort, and, admittedly, with a lot of others, is
that items are only swapped with their immediate neighbors. If the smallest
item happens to find itself at the end of the list, it will have to be swapped
with every item in the list before it gets to its final resting place.
Bubble sort is not stable, since the sweeping will snag the final one of a set of
equal items and hence equal items will appear in reverse order in the sorted
list than they appeared in the original list. If the comparison was changed to
a less than or equal test instead of a pure less than test, the sort would
become stable, but the number of swaps would increase, and the little optimization
we did would no longer work.

← →
Sha © (2007-09-16 14:28) [30]

На сайте автора http://www.boyet.com/FixedArticles/DADSBook.html
в спмске опечаток данная ошибка не упомянута.

← →
Anatoly Podgoretsky © (2007-09-16 14:35) [31]

> Sha (16.09.2007 14:28:30) [30]

Автор пишет о двух алгоритмах, а фраза относится к конкретной реализации, которая неустойчива.

← →
Sha © (2007-09-16 14:42) [32]

> Anatoly Podgoretsky © (16.09.07 14:35) [31]
> Автор пишет о двух алгоритмах...

Нет. У автора никакого другого алготма бабл-сорт в книге нет.
If the comparison was changed to
a less than or equal test instead of a pure less than test, the sort would
become stable, but the number of swaps would increase, and the little optimization
we did would no longer work.

Дословно: если бы сравнеине (связанное с перестановкой - мое)
было изменено на "less than or equal" вместо чистого "less than", то данная сортировка стала бы стабильной...

← →
Sha © (2007-09-16 14:48) [33]

И подглавка, из которой я все это выкусил, посвящена исключительно
одному приведенному выше алгоритму.

← →
Anatoly Podgoretsky © (2007-09-16 14:49) [34]

> Sha (16.09.2007 14:42:32) [32]

Вот здесь он и говорит о другом алгоритме, в котором другое сравнение. Код его он не приводит.

← →
Anatoly Podgoretsky © (2007-09-16 14:55) [35]

> Sha (16.09.2007 14:48:33) [33]

Он и предупреждает, что данный алгоритм неустойчивый и говорит, какой будет устойчивым.

← →
Sha © (2007-09-16 14:56) [36]

> Anatoly Podgoretsky © (16.09.07 14:49) [34]
Ты имеешь ввиду, что другой - это тот, в котором он предагает
if (aCompare(aList.List^[j], aList.List^[j-1]) < 0) then begin
заменить на
if (aCompare(aList.List^[j], aList.List^[j-1]) <= 0) then begin
?

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

> Sha (16.09.2007 14:56:36) [36]

Может быть, но он по крайней мере честен, говоря что есть два алгоритма устойчивый и нет.
А вот некоторые сделали из этого неверный вывод, что пузырек неустойчив.
Я именно об этом говорю.

Я не стал анализировать какой устойчив, а какой нет. Это же зависит только от двух вещей от направления сортировки и от примененого оператора отношения.

Как это устойчивость неважна?

TMyClass = class
public
x, y: Integer;
end;

Есть список, в котором будет два экземпляра с одинаковыми y ( по которому проводится сортировка и разными x.

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

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

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

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

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

TMyClass = class
public
x: Integer;
end;

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

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

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

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

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

> 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.

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

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

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

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

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

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

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

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