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

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

Войти
Регистрация
Восстановить пароль
 
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
#1

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

03.04.2012, 23:19. Просмотров 790. Ответов 4
Метки нет (Все метки)

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

C++ Посчитать число сравнений в QuickSort
stdlib.h - quicksort C++
C++ QuickSort
QuickSort найдите ошибку C++
quicksort выдает "чужое" число C++
C++ Прокомментировать код. QuickSort
C++ Cравнить число перестановок для различных сортировок
По заданному числу N найти число Х путем перестановок цифр C++
C++ Сортировка методом QuickSort
Реализация QuickSort C++
C++ Для заданных чисел найти число соединений и перестановок воспользовавшись функцией вычисления факториала
QuickSort на C++11 C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
03.04.2012, 23:24     Число перестановок QuickSort #2
Завести переменную счетчик и инкрементировать ее при каждой перестановке.
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
03.04.2012, 23:27  [ТС]     Число перестановок QuickSort #3
я так и сделал)) может есть какая нибудь формула, которая выведет приближенное число... Я понимаю что ответ будет разным, зависит от того какие кривые руки это писало))) но все же, на какой диапазон примерно рассчитывать? просто охота свои расчеты проверить
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
03.04.2012, 23:50     Число перестановок QuickSort #4
Зависит от состояния изначального массива, ведь если в нем уже какие то элементы находятся на своих местах, то перестановки для них не нужны.
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,917
Записей в блоге: 1
04.04.2012, 00:32     Число перестановок QuickSort #5
Цитата Сообщение от jambas92 Посмотреть сообщение
я так и сделал)) может есть какая нибудь формула, которая выведет приближенное число... Я понимаю что ответ будет разным, зависит от того какие кривые руки это писало))) но все же, на какой диапазон примерно рассчитывать? просто охота свои расчеты проверить
формула известна: асимптотические оценки скорости
O(n log n) в среднем случае.
O(n квадрат) в самом худшем,
Yandex
Объявления
04.04.2012, 00:32     Число перестановок QuickSort
Ответ Создать тему
Опции темы

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