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

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

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

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

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

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

Посчитать число сравнений в QuickSort - C++
приветствую всех любителей и профессионалов по С++. Изучаю Quicksort Мне нужно чтобы программа посчитала число сравнений сделанное при...

Cравнить число перестановок для различных сортировок - C++
Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма...

По заданному числу N найти число Х путем перестановок цифр - C++
В трехзначном числе Х зачеркнули его вторую цифру. Когда к образованному при этом двузначному числу слева приписали вторую цифру числа Х,...

quicksort выдает "чужое" число - C++
здравствуйте! ниже прилагаю код программы. суть программы в том, чтобы отсортировать числа по их кодам (код получается заменой младшего...

Для заданных чисел найти число соединений и перестановок воспользовавшись функцией вычисления факториала - C++
Для заданых m та n найти число соеденений и перестановок воспользововшись функцией обчислення факториала числа.(

QuickSort на C++11 - C++
Написал быструю сортировку, добился работоспособности и сразу захотелось улучшить сам код. #include <iostream> #include...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
03.04.2012, 23:24 #2
Завести переменную счетчик и инкрементировать ее при каждой перестановке.
1
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
03.04.2012, 23:27  [ТС] #3
я так и сделал)) может есть какая нибудь формула, которая выведет приближенное число... Я понимаю что ответ будет разным, зависит от того какие кривые руки это писало))) но все же, на какой диапазон примерно рассчитывать? просто охота свои расчеты проверить
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
03.04.2012, 23:50 #4
Зависит от состояния изначального массива, ведь если в нем уже какие то элементы находятся на своих местах, то перестановки для них не нужны.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
04.04.2012, 00:32 #5
Цитата Сообщение от jambas92 Посмотреть сообщение
я так и сделал)) может есть какая нибудь формула, которая выведет приближенное число... Я понимаю что ответ будет разным, зависит от того какие кривые руки это писало))) но все же, на какой диапазон примерно рассчитывать? просто охота свои расчеты проверить
формула известна: асимптотические оценки скорости
O(n log n) в среднем случае.
O(n квадрат) в самом худшем,
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2012, 00:32
Привет! Вот еще темы с ответами:

QuickSort - C++
Помогите с алгоритмом и кодом на C++ быстрой сортировки! Наработок вообще нет!

Quicksort - C++
Дан массив, необходимо отсортировать его в порядке возрастания. Использую квиксорт, но в одном из тестов не проходит по времени (2с). ...

Реализация QuickSort - C++
Ребят, есть нужда отсортировать массив структур по полю name (по алфавиту) реализовав алгоритм QuickSort. Написал вроде как черновой...

stdlib.h - quicksort - C++
Идея такова: отсортировать массив A очень быстрым методом Хоара. Пробовал в stdlib.h делать QuickSort - ничего не получилось. Все значения...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
04.04.2012, 00:32
Ответ Создать тему
Опции темы

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