 |
|
Модераторы: LSD |
 
|
|
Устойчивость алгоритма сортировки 
| Lacoste1024 |
|
|||
|
Шустрый  Профиль Группа: Участник Сообщений: 69 Регистрация: 20.3.2011 |
Дайте мне пожалуйста толковое объяснение устойчивости алгоритма сортировки. Пока я знаю только 2 определения:
1. Сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. Но я не совсем понимаю что это значит. 2. Устойчивый алгоритм - тот, у которого время работы и в худшем и в лучшем случае одинаково. Помогите разобраться |
|||
|
||||
Загрузка ...
| spin2 |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 598 Регистрация: 15.12.2005 Где: Москва-Одесса |
По мне так скорее вариант 2.
И суть в том, что разные алгоритмы по разному работают на разных входных данных. Если тебе нужно отсортировать "1 2 3 4 5", "5 4 3 2 1" и "2 5 1 4 3" каждым из алгоритмов, то у разных алгоритмов это может занять разное время. И у кого время будет близким для всех случаев - тот и устойчивый алгоритм. -------------------- |
|||
|
||||
| bems |
|
|||
 Эксперт Профиль Группа: Комодератор Сообщений: 3400 Регистрация: 5.1.2006 |
первый. Сортируем список
key = 2 value = 'two' key = 1 value = 'one' key = 2 value = 'vsdihnrvgsdfhgnv' в отсортированном списке вторая запись всегда становится первой, потому что у неё минимальный ключ. порядок записей с ключом 2 у устойчивого алгоритма сохраняется, у неустойчивого вообще говоря может быть любым, то есть заранее не известно будет ли two предшествовать vsdihnrvgsdfhgnv или нет Это сообщение отредактировал(а) bems - 27.4.2012, 04:14 -------------------- Обижено школьников: 8 |
|||
|
||||
| Lacoste1024 |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 69 Регистрация: 20.3.2011 |
bems, а если даны только числа?
|
|||
|
||||
| bems |
|
|||
|
Эксперт Профиль Группа: Комодератор Сообщений: 3400 Регистрация: 5.1.2006 |
Если есть только ключи то устойчивый алгоритм неотличим от неустойчивого, но это же частность. И ключ это не обязательно число.
-------------------- Обижено школьников: 8 |
|||
|
||||
|
|
| Правила раздела «Флейм» | |
|
|
Добро пожаловать в «Флейм». В разделе не действуют многие правила:
Строго запрещено:
Напоминаем о существовании волшебной кнопочки "Репорт". Если вы увидели сообщение, несовместимое с жизнью, просьба подвести на нее курсор и клацнуть левой клавишей мышки. Тем самым вы сможете призвать злого, но жутко справедливого джина-модератора, который нашлет порчу на злостного нарушителя. Кстати - счётчик сообщений здесь не растёт. Глас Винграда:
Глас Философии:
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Sneg0k |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Флейм | Следующая тема » |
[ Время генерации скрипта: 0.1015 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |