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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.85
MafoR
0 / 0 / 0
Регистрация: 25.01.2010
Сообщений: 15
#1

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

07.01.2011, 21:59. Просмотров 2598. Ответов 13
Метки нет (Все метки)

Добрый вечер, всех с прошедшими праздниками. Может кто-нибудь подсказать (по возможности помочь реализовать) алгоритм проверки устойчивости алгоритма сортировки. Я понимаю, что нужно сортировать последовательности вида 1а 1в 1с, но как проверить результат сортировки (произошла перестановка или нет). Было бы не плохо организовать такой скриптик, который генерировал бы файл с последовательностями такого вида. Заранее благодарю за помощь.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.01.2011, 21:59     Устойчивость алгоритма сортировки
Посмотрите здесь:

Устойчивость шейкерной сортировки - C++
Вчера в прикрепленной теме по сортировкам в пункте 2 наткнулся на следующее утверждение: Несмотря на то, что утверждение это довольно...

Выбор алгоритма сортировки - C++
Доброе время суток! В универе дали вот такое задание Предположим, что необходимо отсортировать массив, состоящий из нескольких...

Реализация алгоритма сортировки вставками - C++
Мне нужно сделать лабу тема вверху... перед этим прочитал тему http://www.cyberforum.ru/cpp-beginners/thread27084.html все равно не...

Выбор оптимального алгоритма сортировки. - C++
Характеристика массива:отсортирован в случайном порядке. Необходимо подобрать метод сортировки по возрастанию и обосновать выбор.

Реализация алгоритма быстрой сортировки quickSort - C++
это алгоритм быстрой сортировки quickSort прошу напишите значение строк файл исходного кода qs.cpp : #include "stdafx.h"...

Распараллеливание алгоритма сортировки - метод вставки - C++
Здравствуйте нужно осуществить распараллеливание алгоритма сортировки - метод вставки на N отдельных потоков. Есть идеи как это...

Подсчёт время работы алгоритма сортировки - C++
Пытаюсь посчитать время работы алгоритма в миллисекундах, но постоянно выходит минусовое число. Как написать правильно? start_time =...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Алекс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ндр
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
Эксперт С++
3048 / 1693 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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
Эксперт С++
3048 / 1693 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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++
Помогите пожалуйста переделать реализацию сортировки так, чтобы она могла работать с любыми типами данных(int, double, etc) Т.е. могла...

может кто представить схему алгоритма сортировки слиянием? - C++
пожалуйстаааааа:cry:

Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки - C++
Почему вот это : void sort(int *ar, int L, int R){ int i, j, x, buf; x = ar; i = L; j = R; do { ...

Написать программу для реализации алгоритма сортировки методом пирамиды - C++
Разработать программу для реализации алгоритма сортировки методом пирамиды. Вывести в диалоге столбчатую диаграмму зависимости времени...

Провести исследования быстродействия алгоритма сортировки для различного числа элементов в массиве - C++
Написать программу , в которой реализируется метод сортировки (пузырьковая , блочная или вставкой - не важно). Провести исследования...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru