Форум программистов, компьютерный форум CyberForum.ru

Устойчивость алгоритма сортировки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.85
MafoR
0 / 0 / 0
Регистрация: 25.01.2010
Сообщений: 15
07.01.2011, 21:59     Устойчивость алгоритма сортировки #1
Добрый вечер, всех с прошедшими праздниками. Может кто-нибудь подсказать (по возможности помочь реализовать) алгоритм проверки устойчивости алгоритма сортировки. Я понимаю, что нужно сортировать последовательности вида 1а 1в 1с, но как проверить результат сортировки (произошла перестановка или нет). Было бы не плохо организовать такой скриптик, который генерировал бы файл с последовательностями такого вида. Заранее благодарю за помощь.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Алексaндр
 Аватар для Алексaндр
131 / 108 / 5
Регистрация: 04.12.2010
Сообщений: 313
07.01.2011, 22:17     Устойчивость алгоритма сортировки #2
ну, похоже, этот скрипт будет являться простой сортировкой, но на каждом шагу нужно будет проверять будет ли перестановка нужна. если да - просто программа выведет элементы, которые подлягли перестановке...
да вроде как и всё... можно будет даже вывести сколько перестановок произошло и в каком ряду, какой строке )
MafoR
0 / 0 / 0
Регистрация: 25.01.2010
Сообщений: 15
07.01.2011, 22:26  [ТС]     Устойчивость алгоритма сортировки #3
Просто у меня уже есть набор сортировок (а именно 8 штук) и мне нужно каждую сортировку проверить на устойчивость. Т.е. надо придумать такую функцию, которая подавала бы сортировке на вход файл с элементами, а после их сортировки выводилось сообщение, является ли данная сортировка устойчивой или нет.
Алексaндр
 Аватар для Алексaндр
131 / 108 / 5
Регистрация: 04.12.2010
Сообщений: 313
07.01.2011, 22:29     Устойчивость алгоритма сортировки #4
Ну, так в каждой сортировке при замене элементов выведи элементы и шаг сортировки.
MafoR
0 / 0 / 0
Регистрация: 25.01.2010
Сообщений: 15
07.01.2011, 22:36  [ТС]     Устойчивость алгоритма сортировки #5
Хм,… а что если при перестановке элементов просто их между собой сравнивать и если один элемент равен другому, то выводить сообщение о неустойчивости данного алгоритма сортировки.
gr_8_zizu
13 / 8 / 2
Регистрация: 07.01.2011
Сообщений: 149
07.01.2011, 22:43     Устойчивость алгоритма сортировки #6
По моему так можно сделать только если в алгоритме сортировки не предусмотрена ситуация, когда 2 элемента ровны между собой.
MafoR
0 / 0 / 0
Регистрация: 25.01.2010
Сообщений: 15
07.01.2011, 22:55  [ТС]     Устойчивость алгоритма сортировки #7
Но в таком случае как проверить устойчивость встроенной сортировки sort. По-моему будет намного лучше подавать на вход последовательность вида 1а 1в 1с ну или что-то вроде этого. Но перебирая различные последовательности данного вида у меня результат каждый раз почему-то разный, в зависимости от последовательности. Вот мои наработки
Код
sub Stability{

	@M_Mas = @_;
	for($i = 0; $i < @M_Mas; ++$i){
		@massiv[$i] = chop($M_Mas[$i]);
	}
	
	$stroka = join('',@massiv);
	
	if($stroka eq 'abc'){		#1a 1b 1c
		print"Sorting stable =)\n";
	} 
	else{
		print"Sort unstable! =(\n";
	}
}
Просто я работаю над задачей сравнения и описания различных видов сортировок. Вот мне и нужно неким скриптом доказать устойчивость/неустойчивость того или иного алгоритма сортировки.
Mr.X
Эксперт С++
 Аватар для Mr.X
2800 / 1576 / 246
Регистрация: 03.05.2010
Сообщений: 3,658
07.01.2011, 23:36     Устойчивость алгоритма сортировки #8
Цитата Сообщение от MafoR Посмотреть сообщение
Но в таком случае как проверить устойчивость встроенной сортировки sort. По-моему будет намного лучше подавать на вход последовательность вида 1а 1в 1с ну или что-то вроде этого. Но перебирая различные последовательности данного вида у меня результат каждый раз почему-то разный, в зависимости от последовательности.
Правильный у вас результат, так как алгоритм std::sort является нестабильной сортировкой. Стабильной является std::stable_sort.
MafoR
0 / 0 / 0
Регистрация: 25.01.2010
Сообщений: 15
07.01.2011, 23:42  [ТС]     Устойчивость алгоритма сортировки #9
c sort все порядке, другие сортировки подкачивают. К примеру, сортировка включением на одном примере устойчивая, а на другом уже нет. И так каждая, на разных примерах по-разному себя ведет.
Mr.X
Эксперт С++
 Аватар для Mr.X
2800 / 1576 / 246
Регистрация: 03.05.2010
Сообщений: 3,658
07.01.2011, 23:52     Устойчивость алгоритма сортировки #10
Цитата Сообщение от MafoR Посмотреть сообщение
c sort все порядке, другие сортировки подкачивают. К примеру, сортировка включением на одном примере устойчивая, а на другом уже нет. И так каждая, на разных примерах по-разному себя ведет.
По-моему так нужно делать.
Взбалтываем тестовый массив с помощью std::random_shuffle, сортируем на своих местах одинаковые для сортировки и различные для нас элементы, запускаем сортировку. Сделать это в цикле раз миллион с выходом из цикла при первом же нестабильном результате. Хотя бы один нестабильный результат характеризует сортировку как нестабильную.
Имеется в виду, что в массиве много различных для сортировки значений помногу экземпляров, которые для нас различны.
Напильнег
480 / 120 / 10
Регистрация: 30.09.2010
Сообщений: 473
08.01.2011, 11:04     Устойчивость алгоритма сортировки #11
Цитата Сообщение от MafoR Посмотреть сообщение
Я понимаю, что нужно сортировать последовательности вида 1а 1в 1с,
Я один не вижу, что такое последовательности вида 1a, 1b, 1c?
MafoR
0 / 0 / 0
Регистрация: 25.01.2010
Сообщений: 15
08.01.2011, 11:39  [ТС]     Устойчивость алгоритма сортировки #12
Различные последовательности чисел с суффиксами виде букв, по которым собственно потом и можно будет определить были, переставлены одинаковые числа или нет.
Напильнег
480 / 120 / 10
Регистрация: 30.09.2010
Сообщений: 473
08.01.2011, 23:59     Устойчивость алгоритма сортировки #13
Понятно. А не проще ли сделать по другому. Сортировать будем структуры. Первое поле структуры - ключевое, по которому и осуществляется сортировка. Для того, чтобы были повторы, тупо для массива из n=10000 значений генерим их в интервале 1..2000, скажем. Второе поле типа long int заполняем перед сортировкой по порядку, от 0 до n-1. Тогда после сортировки для проверки устойчивости алгоритма надо проверить, что для структур с одинаковым значением ключевого поля значения второго поля остались отсортированы по возрастанию. Как-то так.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.01.2011, 18:01     Устойчивость алгоритма сортировки
Еще ссылки по теме:

C++ Провести исследования быстродействия алгоритма сортировки для различного числа элементов в массиве
Написать программу для реализации алгоритма сортировки методом пирамиды C++
C++ Реализация алгоритма быстрой сортировки quickSort

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
MafoR
0 / 0 / 0
Регистрация: 25.01.2010
Сообщений: 15
09.01.2011, 18:01  [ТС]     Устойчивость алгоритма сортировки #14
Напильнег
Большое спасибо! Ваш совет очень помог!=)
Yandex
Объявления
09.01.2011, 18:01     Устойчивость алгоритма сортировки
Ответ Создать тему
Опции темы

Текущее время: 23:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru