Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 18.03.2013, 11:16   #1
FrauAja
Новичок
Джуниор
 
Регистрация: 01.06.2011
Сообщений: 2
По умолчанию визуализация быстрой сортировки (С++)

Добрый день! Нужно написать программу, которая иллюстрирует работу быстрой сортировки.
В частности должно присутствовать:
*вывод пояснения к каждому шагу алгоритма
*работа в пошаговом и автоматическом режиме,
*регулировка скорости автоматического выполнения
*возможность отката на любое количество шагов назад,
*работа как с предварительно заданными, так и со случайными и введёнными пользователем данными

Не подскажите, как можно реализовать пошаговый режим для быстрой сортировки и возврат на любое количество шагов назад?

Буду очень признательна за помощь!
FrauAja вне форума Ответить с цитированием
Старый 18.03.2013, 11:55   #2
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Не очень понятно, что считать "шагом" в быстрой сортировке.
"Возврат на любое количество шагов назад" = (если не усложнять) "сохранение состояния массива после каждого шага".
"Пошаговый режим" = "сохранение состояния алгоритма после каждого шага и возврат управления 'наверх'". Сразу обозначу, что все способы, которые мне приходят в голову для решения этой задачи, весьма корявы и чреваты логическими ошибками. Можете посмотреть в сторону макросов setjmp/longjmp.
Abstraction вне форума Ответить с цитированием
Старый 18.03.2013, 12:32   #3
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

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

А раз так, то мы приходим и к пониманию того, что следует взять за шаг: уже упомянутое выше любое изменение.
Т.е. шаг получается довольно мелким.
s-andriano вне форума Ответить с цитированием
Старый 18.03.2013, 12:47   #4
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
Альтернативный вариант с запоминанием на каждом шаге полного состояния мне представляется неоправданно ресурсремким.
Да ладно, какого размера те массивы?
Кроме того, перестановок - O(N*lnN), вызовов QuickSort в классическом варианте - O(lnN), так что если считать шагом интервал от вызова QuickSort до рекурсивных вызовов, памяти понадобится те же O(N*lnN). Если запоминать результат каждой перестановки - будет O(N^2*lnN), при N~1000 проблем не будет, а массивы большего размера поди нормально визуализируй.
Abstraction вне форума Ответить с цитированием
Старый 18.03.2013, 12:56   #5
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

Пожалуй, согласен насчет ресурсоемкости.
Тем более, как мне кажется, максимальный размер массивов с точки зрения их визуализации вообще нужно ограничить несколькими десятками - для иллюстрации вполне достаточно.
Но продолжаю придерживаться мнения, что шаг от вызова до вызова - слишком крупный, т.к. не иллюстрирует работу алгоритма.
s-andriano вне форума Ответить с цитированием
Старый 18.03.2013, 13:08   #6
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
Но продолжаю придерживаться мнения, что шаг от вызова до вызова - слишком крупный, т.к. не иллюстрирует работу алгоритма.
Ну, может. Мне просто запомнилась картинка в Вики, иллюстрирующая работу сортировки слиянием - она сделана именно так. А вообще - вопрос к ТС, конечно.
Abstraction вне форума Ответить с цитированием
Старый 18.03.2013, 13:47   #7
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

Там картинка, если мне не изменяет память, в формате gif. Одно это диктует очень жесткие ограничения.
s-andriano вне форума Ответить с цитированием
Старый 18.03.2013, 14:39   #8
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Вот тот вариант что s-andriano назвал альтернативный и используй - он проще и визуализировать сортировку даже тыщи элементов никто не будет (ну тыкать пошагово точно, т.к. состарица раньше)
rrrFer вне форума Ответить с цитированием
Старый 18.03.2013, 19:21   #9
FrauAja
Новичок
Джуниор
 
Регистрация: 01.06.2011
Сообщений: 2
По умолчанию

s-andriano, насчет шага вы правы, за него следует считать любое изменение (сравнение элементов, перестановка, изменение границ), а массив состоит из 10 целых чисел.
Нашла визуализатор (http://rain.ifmo.ru/cat/view.php/vis...quicksort-2004), нечто подобное требуется реализовать мне.
FrauAja вне форума Ответить с цитированием
Старый 19.03.2013, 10:59   #10
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Сравнение элементов и "изменение границ" изменяют внутреннее состояние алгоритма, но никак не сказываются на состоянии массива. Вам что, нужно визуализировать и внутреннее состояние алгоритма тоже?
Abstraction вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

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

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритмы сортировки пирамидальный(кучей) и быстрой сортировки (с++) mmd12 Помощь студентам 4 17.05.2012 14:14
Проблема с алгоритмом быстрой сортировки maryan.vetrov Общие вопросы C/C++ 2 31.08.2010 18:56
Вопросы насчёт быстрой сортировки(С++) Stopafilm Помощь студентам 2 01.08.2010 10:43
Метод быстрой сортировки Nord18 Паскаль, Turbo Pascal, PascalABC.NET 1 05.06.2010 11:24
Метод быстрой сортировки Хоора Pascal Бармалей Помощь студентам 8 18.11.2009 21:21