Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 01.06.2007, 02:09
Новичок

Отправить личное сообщение для Warchief Посмотреть профиль Найти все сообщения от Warchief
 
Регистрация: 01.06.2007
Сообщений: 4

как можно доказать стабильность алгоритма?
Как можно доказать стабильность алгоритма? Например для bublesort ну или любого другого алгоритма? Можно конечно показать на примере, но как я думаю, есть и другие варианты. Подскажите пожалуйста!!!
  #2  
Старый 01.06.2007, 07:27
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

под стабильностью алгоритма что имеется в виду?
корректность алгоритма для любых наборов данных или устойчивость сортировки (сохранение относительного порядка при сортировке по разным ключам)?
  #3  
Старый 01.06.2007, 13:52
Новичок

Отправить личное сообщение для Warchief Посмотреть профиль Найти все сообщения от Warchief
 
Регистрация: 01.06.2007
Сообщений: 4

под стабильностью имеется в виду сохранение относительного порядка при сортировке по разным ключам, тоесть одинаковые элементы с одинаковым значением, во время сортировки не изменяют своей позиции.
  #4  
Старый 01.06.2007, 14:48
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Пузырьковая сортировка производит только обмены соседних элементов с разными ключами, так что если элементы A и B с одинаковым ключом шли в определенном порядке, то этот порядок не изменится.

Сортировка вставками - для очередного элемента ищется первая позиция справа, куда его можно вставить, после чего сдвигаются элементы, которые не меняются местам между собой, так что относительный порядок так же не нарушается.

Сортировка слиянием - на странице http://algolist.manual.ru/sort/merge_sort.php
в процедуре слияния сделано неаккуратно
while (pos1 <= split && pos2 <= ub) {
if (a[pos1] < a[pos2])
если знак "меньше" заменить на "меньше или равно", то в выходную последовательность при слиянии сначала будут записаны элементы с одинаковым ключом из левого подмассива, затем из правого, благодаря чему сортировка будет устойчивой, как ей и положено
  #5  
Старый 01.06.2007, 16:04
Новичок

Отправить личное сообщение для Warchief Посмотреть профиль Найти все сообщения от Warchief
 
Регистрация: 01.06.2007
Сообщений: 4

спасибо, это вроде понятно, но меня интересует, можно ли именно доказать(например с помощью индукции или инварианоов или ещё как-нибудь) стабильность любогосортирующего алгоритма?
  #6  
Старый 01.06.2007, 16:58
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Сообщение от Warchief Посмотреть сообщение
спасибо, это вроде понятно, но меня интересует, можно ли именно доказать(например с помощью индукции или инварианоов или ещё как-нибудь) стабильность любогосортирующего алгоритма?
Да, можно (для устойчивых сортировок, конечно). Примеры есть в книгах Кормена и Бентли.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
реализация алгоритма хаффмана на Php и си Саня Реализация, исходники, языки 5 19.05.2010 14:03
можно вставлять формулы в Tex Илья Кантор Новости 3 27.05.2007 19:52
реализация алгоритма ахо-корасик Straight Сортировка и поиск 0 28.04.2007 09:32
найти порядок, в котором можно соединить N точек, чтобы получился N-угольник †Virus† Вычислительная геометрия 3 27.02.2007 21:49
решение алгоритма логики предикатов paradoksovnet Математические алгоритмы 22 16.12.2006 15:48