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

Число перестановок QuickSort - C++

Восстановить пароль Регистрация
 
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
03.04.2012, 23:19     Число перестановок QuickSort #1
Здравствуйте! Подскажите пожалуйста, как можно посчитать число перестановок QuickSort. Имеется массив на 10,000 элементов
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2012, 23:19     Число перестановок QuickSort
Посмотрите здесь:

stdlib.h - quicksort C++
C++ QuickSort
QuickSort найдите ошибку C++
quicksort выдает "чужое" число C++
QUICKsort и MERGEsort недостатки и преимущества C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
03.04.2012, 23:24     Число перестановок QuickSort #2
Завести переменную счетчик и инкрементировать ее при каждой перестановке.
jambas92
 Аватар для jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
03.04.2012, 23:27  [ТС]     Число перестановок QuickSort #3
я так и сделал)) может есть какая нибудь формула, которая выведет приближенное число... Я понимаю что ответ будет разным, зависит от того какие кривые руки это писало))) но все же, на какой диапазон примерно рассчитывать? просто охота свои расчеты проверить
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
03.04.2012, 23:50     Число перестановок QuickSort #4
Зависит от состояния изначального массива, ведь если в нем уже какие то элементы находятся на своих местах, то перестановки для них не нужны.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
04.04.2012, 00:32     Число перестановок QuickSort #5
Цитата Сообщение от jambas92 Посмотреть сообщение
я так и сделал)) может есть какая нибудь формула, которая выведет приближенное число... Я понимаю что ответ будет разным, зависит от того какие кривые руки это писало))) но все же, на какой диапазон примерно рассчитывать? просто охота свои расчеты проверить
формула известна: асимптотические оценки скорости
O(n log n) в среднем случае.
O(n квадрат) в самом худшем,
Yandex
Объявления
04.04.2012, 00:32     Число перестановок QuickSort
Ответ Создать тему
Опции темы

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