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

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

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

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

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

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


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

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

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

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

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

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

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

да.

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

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

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

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


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

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