Мастер кустарных методов
![]() 232 / 227 / 17
Регистрация: 09.11.2010
Сообщений: 680
|
|||||||||||
1 | |||||||||||
Алгоритм Быстрой сортировки (Quick Sort)25.11.2010, 17:27. Показов 135744. Ответов 16
Метки нет Все метки)
(
Всем доброго времени суток. Реализовал Быструю Сортировку на C++. Всё работает. Только препод требует доказать, что мой алгоритм правильный. Не знаю как это сделать... Помогите пожалуйста. Вот код:
Файл qs.cpp:
2
|
25.11.2010, 17:27 | |
25.11.2010, 17:27 | |
Ответы с готовыми решениями:
16
Qvick-sort алгоритм быстрой сортировки. Гляньте плс( Метод сортировки quick sort ведомость абитуриентов
|
Freelance
![]() ![]() 2891 / 1826 / 356
Регистрация: 09.09.2010
Сообщений: 3,841
|
|
25.11.2010, 18:16 | 2 |
0
|
Freelance
![]() ![]() 2891 / 1826 / 356
Регистрация: 09.09.2010
Сообщений: 3,841
|
|
25.11.2010, 18:49 | 4 |
LEQADA, зато там правильный алгоритм быстрой сортировки.
0
|
![]() 5057 / 3117 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
26.11.2010, 06:44 | 7 |
Да, вроде работает, мне условие сначала показалось неверным.
0
|
![]() ![]() |
|
26.11.2010, 07:10 | 8 |
LEQADA, во-первых докажите, что алгоритм справляется со своей задачей, то есть либо подготовьте данные заранее, либо напишите функцию, которая проверяет последовательность на неубывание/невозрастание, в общем докажите, что функция сортировки на самом деле сортирует.
во-вторых, если требуется доказать, что этой алгоритм действительно быстрой сортировки, подготовьте специальный набор данных и подсчитайте количество итераций, конечно для этого набора данных должно быть известно верное количество итераций.
1
|
![]() ![]() 476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
|
|
26.11.2010, 07:35 | 9 |
В Кормене, например, доказательство есть.
0
|
![]() 5057 / 3117 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
26.11.2010, 11:35 | 11 |
LEQADA, очевидно, фамилия.
0
|
![]() ![]() 3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
26.11.2010, 12:27 | 12 |
В худшем случае (при сортировке уже отсортированного массива) время работы быстрой сортировки пропорционально n^2. А ее среднее время работы пропорционально n*log2(n) (log2 здесь логарифм по основанию 2).
Т.е. для доказательства достаточно для некоторого фиксированного n сначала замерить время сортировки отсортированного массива, а затем вычислить среднее время сортировки одного массива из некоторого множества из m случайных массивов, и найти их отношение A. Если A при увеличении m стремится к n^2/n*log2(n), т.е. к величине B = n/log2(n) (например, при n = 256 B = 32), то сортировка является быстрой.
0
|
![]() ![]() |
|
26.11.2010, 15:38 | 13 |
![]() Решение
LEQADA, А вы читаете только не больше 10 слов из сообщений?
и далее, 1) Подготовьте данные заранее: Создайте заготовки данных, например, в файле. Где будут храниться начальная последовательность - несортированная, и эталонная - сортированная. Эти данные заведомо правильные. Подготовьте средние и крайние случаи. Применяете алгоритм к начальной последовательности и сравниваете ее с эталоном. 2) Напишите функцию, которая проверяет последовательность на неубывание или невозрастание: здесь даже никаких объяснений не надо. 3) Найдите математическое доказательство. Кормен - это не что, а автор, профессор компьютерных наук.
3
|
![]() 5057 / 3117 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
26.11.2010, 16:00 | 14 |
1
|
programina
|
14.11.2012, 11:37
#15
|
0
|
![]() 172 / 21 / 2
Регистрация: 11.09.2014
Сообщений: 235
|
||||||||||||||||
09.11.2015, 18:22 | 16 | |||||||||||||||
оживлю, пожалуй, мамонта, потому что есть как раз вопрос по данной выше ссылке
мне, собственно, непонятен только один момент:
Добавлено через 32 минуты сам нашёл ответ =)) з.ы. однако, данный алгоритм почему-то не работает ![]() Добавлено через 32 минуты нашёл почему не работает - пришлось расписывать все шаги компа на бумажке вот в этой строке ошибка:
1
|
0 / 0 / 0
Регистрация: 14.05.2016
Сообщений: 4
|
|
24.11.2016, 16:00 | 17 |
Твоя быстрая сортировка не работает- почитай википедию
0
|
24.11.2016, 16:00 | |
24.11.2016, 16:00 | |
Помогаю со студенческими работами здесь
17
Не алгоритм быстрой сортировки Алгоритм быстрой сортировки Реализовать алгоритм быстрой сортировки Алгоритм быстрой сортировки по убыванию Алгоритм быстрой сортировки против пузырька Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
![]() |
Опции темы | |
|
Новые блоги и статьи
![]() |
||||
Ошибка Docker "Got permission denied while trying to connect to the Docker daemon socket at"
hw_wired 14.02.2025
Разработка с использованием Docker может иногда преподносить неожиданные сюрпризы, и одним из самых распространенных камней преткновения становится ошибка с отказом в доступе к демону Docker. . . .
|
Ошибка "No 'Access-Control-Allow-Origin' header is present on the requested resource"
hw_wired 14.02.2025
При разработке современных веб-приложений нередко сталкиваешься с ошибкой "No 'Access-Control-Allow-Origin' header is present on the requested resource". Эта проблема возникает из-за политики. . .
|
Как закрыть порт в Linux
hw_wired 14.02.2025
Управление сетевыми портами в Linux - непростая, но важная задача для обеспечения безопасности системы. Каждый открытый порт - это потенциальная уязвимость, через которую злоумышленики могут. . .
|
Ошибка Angular "Can't bind to 'taskForm' since it isn't a known property of 'form'"
hw_wired 14.02.2025
При разработке веб-приложений на Angular можно столкнуться с ошибкой "Can't bind to '' since it isn't a known property of 'form'". Эта ошибка появляется в консоли браузера когда мы пытаемся. . .
|
Сообщение Git "Pulling without specifying how to reconcile divergent branches is discouraged"
hw_wired 14.02.2025
При работе с системой контроля версий Git многие разработчики сталкиваются с предупреждающим сообщением "Pulling without specifying how to reconcile divergent branches is discouraged". Это. . .
|
Как настроить количество пробелов в отступах табов в Visual Studio Code
hw_wired 14.02.2025
Visual Studio Code предоставляет несколько гибких способов настройки табуляции, каждый из которых имеет свои преимущества. Самый простой и наглядный метод - через графический интерфейс настроек, где. . .
|
Что означает знак восклицания в TypeScript
hw_wired 14.02.2025
TypeScript - удивительный язык программирования, который предоставляет множество возможностей для работы с типами данных. Особый интерес вызывает оператор утверждения ненулевого значения, который. . .
|
Как свернуть/скрыть секции кода в Visual Studio Code
hw_wired 14.02.2025
Ежедневно мы работам с файлами, содержащими сотни и тысячи строк кода. Навигация по такому объему становится настоящим испытанием, особенно когда нужно быстро найти нужный метод или переменную. . . .
|
Автоматическое создание файла requirements.txt в Python
hw_wired 14.02.2025
Дружелюбная среда для разработки на Python, один из самых широко используемых языков программирования, состоит не только из самого кода, но и целого ряда важных компонентов. И если вы когда-нибудь. . .
|
Передача переменных окружения в контейнер Docker
hw_wired 14.02.2025
При работе с Docker контейнерами возникает необходимость передать различные настройки и конфигурационные параметры - от строк подключения к базам данных до API ключей. И хотя можно жестко прописать. . .
|