Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Стабильная и нестабильная сортировка

Автор: Bison 25.8.2010, 20:46

Что такое стабильная и нестабильная сортировка?
"Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. Большинство простых методов сортировки устойчивы, большинство сложных — нет." - из определения ничего не понятно о каких ключах идет речь.

Можете на примере (например, Quicksort-а или пузырька) объяснить что такое? И как превращать из стаб.->нестаб.?

Автор: Akina 25.8.2010, 21:27

Представь, что перед тобой стоИт пять человек:
Андрей (рост 175 см) - Борис(рост 182 см) - Виктор (рост 185 см) - Георгий (рост 192 см) - Дмитрий (рост 182 см)
Тебе дано задание - построить их по росту. Ты можешь построить их двумя вариантами:
1) Георгий - Виктор - Борис - Дмитрий - Андрей
1) Георгий - Виктор -Дмитрий - Борис - Андрей
Видишь? в первом варианте одинаковые по росту Борис и Дмитрий стоят в том же порядке, что и сначала - Борис левее, Дмитрий правее. Во втором варианте - они поменялись местами друг относительно друга.
Так вот - стабильная сортировка гарантирует, что будет получена расстановка 1. А нестабильная может дать любую из двух расстановок.

В случае, например, пузырька:

Код


For i = 1 to N-1
  For j = i+1 to N
    If X(i) > X(j) Then ' Строгая сортировка - равные не обмениваются
      SWAP X(i), X(j)
    End If
  Next j
Next i

Код


For i = 1 to N-1
  For j = i+1 to N
    If X(i) >= X(j) Then ' Нестрогая сортировка - равные обмениваются
      SWAP X(i), X(j)
    End If
  Next j
Next i

Код


For i = 1 to N-1
  For j = i+1 to N
    If X(i) >= X(j) Then ' Нестрогая сортировка - равные обмениваются
      If RND() > 0.5 Then SWAP X(i), X(j) ' с вероятностью 50% (интересно, нахрена?)
    End If
  Next j
Next i

Автор: Bison 25.8.2010, 22:05

Спасибо за объяснение. Значит, разница только в учете: менять одинаковые данные при сортировке или оставить прежним. Прописывается через условия, и на время выполнения соответственно тоже влияет? В чём практическая ценность?
В случае нестабильной сортировки обязательно меняются одинаковые данные?

Автор: Akina 25.8.2010, 23:05

Цитата(Bison @ 25.8.2010, 23:05

)

В чём практическая ценность?

Стабильная сортировка бывает нужна. Фактически она аналогична сортировке по двум признакам, второй из которых - предыдущий порядок. Скажем покупаем мы товар... Конечно выбираем подешевле (основная сортировка), но продавец тоже не дурак, и среди самых дешёвых будет продавать нам самые старые (предыдущий порядок). Стабильная сортировка позволяет продавцу минимизировать потери от истечения сроков годности. Однако алгоритмы стабильных сортировок обычно не столь эффективны...

Цитата(Bison @ 25.8.2010, 23:05

)

В случае нестабильной сортировки обязательно меняются одинаковые данные?

Вот ещё! третий пример кода я зачем писАл? Как фишка ляжет...

Автор: skyboy 25.8.2010, 23:08

на всякий случай - уточню, что ключом в приведенной цитате называется параметр, определяющий порядок - то, "по чем сортируем".

Цитата(Bison @ 25.8.2010, 21:05

)

В чём практическая ценность?

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

Автор: Bison 25.8.2010, 23:32

Цитата(Akina @ 25.8.2010, 23:05)

Вот ещё! третий пример кода я зачем писАл? Как фишка ляжет...

Касательно 3-го примере, наверно, предполагается что, одинаковые числа могут поменяться или нет с вероятностью 0,5.

2 skyboy
В примере ключ - рост людей?

Можно также другой встречный вопрос: при изменении типа (стаб., нестаб.) сортировки это влияет на сложность алгоритма? Например, если обычный Quicksort не стабильный алгоритм, то сделав его стабильным, можно ухудшить оценку, скажем до О(n)?

или я совсем не правильно понимаю?

Автор: skyboy 25.8.2010, 23:58

Цитата(Bison @ 25.8.2010, 22:32

)

В примере ключ - рост людей?

да.

Цитата(Bison @ 25.8.2010, 22:32

)

при изменении типа (стаб., нестаб.) сортировки

любая сортировка будет стабильной, если добавить в сравнение учет позиции в исходном списке. на сложность алгоритма дополнительное сравнение никак не повлияет. потому что O(n) означает не N операций сравнения, а линейную зависимость(3N+2, 7N-5). Следовательно, добавив ещё одно сравнение и увеличив вдвое количество сравнений, мы останемся с прежним порядком операций(что N+1, что 2N+1 суть линейная зависимость от количества элементов).

Добавлено через 46 секунд

Цитата(skyboy @ 25.8.2010, 22:58

)

любая сортировка будет стабильной, если добавить в сравнение учет позиции в исходном списке.

сорри, Akina уже говорил об этом:

Цитата(Akina @ 25.8.2010, 22:05

)

Фактически она аналогична сортировке по двум признакам, второй из которых - предыдущий порядок.

Автор: Akina 26.8.2010, 08:27

Цитата(Bison @ 26.8.2010, 00:32

)

Касательно 3-го примере, наверно, предполагается что, одинаковые числа могут поменяться или нет с вероятностью 0,5.

Но не вообще, а в конкретном сравнении. Если, к примеру, равных по ключу элементов - 4 штуки, то будет аж 6 сравнений, и в каждом порядок или поменяется, или нет.

Цитата(Bison @ 26.8.2010, 00:32

)

при изменении типа (стаб., нестаб.) сортировки это влияет на сложность алгоритма?

Как сказано выше - на сложнось нет. А вот на скорость - ещё как да. А поскольку сортировка - не сферический конь, а вполне прикладушка, это важнее. Ибо от сложности никуда не деться, а оптимизация рулез.

Автор: esperanto 27.8.2010, 22:09

Цитата(skyboy @ 25.8.2010, 23:58)

потому что O(n) означает не N операций сравнения, а линейную зависимость(3N+2, 7N-5).

Ничего подобного.

Автор: Polesinskij 1.11.2013, 17:25

Модератор: Сообщение скрыто.