Стабильная сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка. Нестабильная сортировка - сортировка, которая не гарантирует относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.
Приведем пример:
| Key |
Value |
| 3 |
Blue |
| 2 |
Green |
| 1 |
Red |
| 2 |
Yellow |
Исходный порядок объектов
| Key |
Value |
| 1 |
Red |
| 2 |
Yellow |
| 2 |
Green |
| 3 |
Blue |
Объекты отсортированы по ключу Key по возрастанию нестабильной сортировкой. Относительный порядок элементов с ключом 2 изменился.
| Key |
Value |
| 1 |
Red |
| 2 |
Green |
| 2 |
Yellow |
| 3 |
Blue |
Объекты отсортированы по ключу Key по возрастанию стабильной сортировкой. Относительный порядок элементов с ключом 2 остался прежним.
В магазине рюкзаков составили сравнительную таблицу по четырем параметрам: цвет, материал, число карманов и размер. Получили следующий набор данных:
После чего строки данной таблицы отсортировали нестабильной сортировкой сначала по цвету (в алфавитном порядке, по возрастанию), а затем по числу карманов (по убыванию). В результате этого таблица приобрела следующий вид:
Сколько строк не совпало бы, если бы таблицу отсортировали по тем же критериям (сначала по цвету (в алфавитном порядке, по возрастанию), а затем по числу карманов (по убыванию)), но стабильной сортировкой?
В ответ напишите одно число – количество строк таких, что их содержимое различно в приведенном результате нестабильной сортировки и результате стабильной сортировки этой же таблицы.