| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Флейм > Устойчивость алгоритма сортировки |
| Автор: Lacoste1024 25.4.2012, 13:44 |
| Дайте мне пожалуйста толковое объяснение устойчивости алгоритма сортировки. Пока я знаю только 2 определения: 1. Сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. Но я не совсем понимаю что это значит. 2. Устойчивый алгоритм - тот, у которого время работы и в худшем и в лучшем случае одинаково. Помогите разобраться |
| Автор: spin2 25.4.2012, 18:12 |
| По мне так скорее вариант 2. И суть в том, что разные алгоритмы по разному работают на разных входных данных. Если тебе нужно отсортировать "1 2 3 4 5", "5 4 3 2 1" и "2 5 1 4 3" каждым из алгоритмов, то у разных алгоритмов это может занять разное время. И у кого время будет близким для всех случаев - тот и устойчивый алгоритм. |
| Автор: bems 27.4.2012, 04:13 |
| первый. Сортируем список key = 2 value = 'two' key = 1 value = 'one' key = 2 value = 'vsdihnrvgsdfhgnv' в отсортированном списке вторая запись всегда становится первой, потому что у неё минимальный ключ. порядок записей с ключом 2 у устойчивого алгоритма сохраняется, у неустойчивого вообще говоря может быть любым, то есть заранее не известно будет ли two предшествовать vsdihnrvgsdfhgnv или нет |
| Автор: Lacoste1024 27.4.2012, 13:21 |
| bems, а если даны только числа? |
| Автор: bems 27.4.2012, 14:44 |
| Если есть только ключи то устойчивый алгоритм неотличим от неустойчивого, но это же частность. И ключ это не обязательно число. |