Стабильная сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка. Нестабильная сортировка - сортировка, которая не гарантирует относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.
Приведем пример:
| Key |
Value |
|
Key |
Value |
|
Key |
Value |
| 3 |
Blue |
|
1 |
Red |
|
1 |
Red |
| 2 |
Green |
|
2 |
Yellow |
|
2 |
Green |
| 1 |
Red |
|
2 |
Green |
|
2 |
Yellow |
| 2 |
Yellow |
|
3 |
Blue |
|
3 |
Blue |
| Исходный порядок объектов |
|
Объекты отсортированы по ключу Key по возрастанию нестабильной сортировкой. Относительный порядок элементов с ключом 2 изменился. |
|
Объекты отсортированы по ключу Key по возрастанию стабильной сортировкой. Относительный порядок элементов с ключом 2 остался прежним. |
В магазине рюкзаков составили сравнительную таблицу по четырем параметрам: цвет, материал, число карманов и размер. Получили следующий набор данных:
| gray |
waterproof canvas |
1 |
M |
| white |
smooth leather |
3 |
L |
| red |
textured leather |
2 |
M |
| white |
waterproof canvas |
3 |
M |
| green |
textured leather |
1 |
M |
| black |
textured leather |
2 |
L |
| brown |
canvas |
3 |
S |
| black |
textured leather |
1 |
S |
| green |
canvas |
1 |
M |
| blue |
smooth leather |
3 |
L |
| gray |
smooth leather |
3 |
L |
| gray |
waterproof canvas |
1 |
M |
| gray |
smooth leather |
1 |
S |
| brown |
textured leather |
3 |
L |
| yellow |
textured leather |
2 |
M |
После чего строки данной таблицы отсортировали нестабильной сортировкой сначала по цвету (в алфавитном порядке, по возрастанию), а затем по числу карманов (по убыванию). В результате этого таблица приобрела следующий вид:
| black |
textured leather |
2 |
L |
| black |
textured leather |
1 |
S |
| blue |
smooth leather |
3 |
L |
| brown |
canvas |
3 |
S |
| brown |
textured leather |
3 |
L |
| gray |
smooth leather |
3 |
L |
| gray |
smooth leather |
1 |
S |
| gray |
waterproof canvas |
1 |
M |
| gray |
waterproof canvas |
1 |
M |
| green |
canvas |
1 |
M |
| green |
textured leather |
1 |
M |
| red |
textured leather |
2 |
M |
| white |
smooth leather |
3 |
L |
| white |
waterproof canvas |
3 |
M |
| yellow |
textured leather |
2 |
M |
Сколько строк не совпало бы, если бы таблицу отсортировали по тем же критериям (сначала по цвету (в алфавитном порядке, по возрастанию), а затем по числу карманов (по убыванию)), но стабильной сортировкой?
В ответ напишите одно число — количество строк таких, что их содержимое различно в приведенном результате нестабильной сортировки и результате стабильной сортировки этой же таблицы.