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

← →
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]

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

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.

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

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

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

> 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 (16.09.2007 14:42:32) [32]

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

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

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

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

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

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

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

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