|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
18.03.2013, 11:16 | #1 |
Новичок
Джуниор
Регистрация: 01.06.2011
Сообщений: 2
|
визуализация быстрой сортировки (С++)
Добрый день! Нужно написать программу, которая иллюстрирует работу быстрой сортировки.
В частности должно присутствовать: *вывод пояснения к каждому шагу алгоритма *работа в пошаговом и автоматическом режиме, *регулировка скорости автоматического выполнения *возможность отката на любое количество шагов назад, *работа как с предварительно заданными, так и со случайными и введёнными пользователем данными Не подскажите, как можно реализовать пошаговый режим для быстрой сортировки и возврат на любое количество шагов назад? Буду очень признательна за помощь! |
18.03.2013, 11:55 | #2 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Не очень понятно, что считать "шагом" в быстрой сортировке.
"Возврат на любое количество шагов назад" = (если не усложнять) "сохранение состояния массива после каждого шага". "Пошаговый режим" = "сохранение состояния алгоритма после каждого шага и возврат управления 'наверх'". Сразу обозначу, что все способы, которые мне приходят в голову для решения этой задачи, весьма корявы и чреваты логическими ошибками. Можете посмотреть в сторону макросов setjmp/longjmp. |
18.03.2013, 12:32 | #3 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Если начать со второго вопроса, то только протоколированием всех изменений.
А изменение - выполнение практически любого оператора (вызов подпрограммы, возвращение из нее, перестановка элементов, изменение границ...). Альтернативный вариант с запоминанием на каждом шаге полного состояния мне представляется неоправданно ресурсремким. А раз так, то мы приходим и к пониманию того, что следует взять за шаг: уже упомянутое выше любое изменение. Т.е. шаг получается довольно мелким. |
18.03.2013, 12:47 | #4 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
Кроме того, перестановок - O(N*lnN), вызовов QuickSort в классическом варианте - O(lnN), так что если считать шагом интервал от вызова QuickSort до рекурсивных вызовов, памяти понадобится те же O(N*lnN). Если запоминать результат каждой перестановки - будет O(N^2*lnN), при N~1000 проблем не будет, а массивы большего размера поди нормально визуализируй. |
|
18.03.2013, 12:56 | #5 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Пожалуй, согласен насчет ресурсоемкости.
Тем более, как мне кажется, максимальный размер массивов с точки зрения их визуализации вообще нужно ограничить несколькими десятками - для иллюстрации вполне достаточно. Но продолжаю придерживаться мнения, что шаг от вызова до вызова - слишком крупный, т.к. не иллюстрирует работу алгоритма. |
18.03.2013, 13:08 | #6 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Цитата:
|
|
18.03.2013, 13:47 | #7 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Там картинка, если мне не изменяет память, в формате gif. Одно это диктует очень жесткие ограничения.
|
18.03.2013, 14:39 | #8 |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Вот тот вариант что s-andriano назвал альтернативный и используй - он проще и визуализировать сортировку даже тыщи элементов никто не будет (ну тыкать пошагово точно, т.к. состарица раньше)
|
18.03.2013, 19:21 | #9 |
Новичок
Джуниор
Регистрация: 01.06.2011
Сообщений: 2
|
s-andriano, насчет шага вы правы, за него следует считать любое изменение (сравнение элементов, перестановка, изменение границ), а массив состоит из 10 целых чисел.
Нашла визуализатор (http://rain.ifmo.ru/cat/view.php/vis...quicksort-2004), нечто подобное требуется реализовать мне. |
19.03.2013, 10:59 | #10 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Сравнение элементов и "изменение границ" изменяют внутреннее состояние алгоритма, но никак не сказываются на состоянии массива. Вам что, нужно визуализировать и внутреннее состояние алгоритма тоже?
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритмы сортировки пирамидальный(кучей) и быстрой сортировки (с++) | 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 |