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

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

Войти
Регистрация
Восстановить пароль
 
alisteas
0 / 0 / 0
Регистрация: 07.10.2013
Сообщений: 13
#1

Прогресс выполнения быстрой сортировки - C++

07.11.2013, 11:38. Просмотров 489. Ответов 7
Метки нет (Все метки)

хочу написать простой консольный прогресс бар, отображающий ход выполнения быстрой сортировки, но не могу найти за что "зацепиться" то есть к чему привязать прогресс выполнения (т.к. к количеству посортированных елементов тут привязать не получится). есть ли у этого алгоритма какие то другие меры хода выполнения (например считать глубину рекурсии и т.п.)?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.11.2013, 11:38     Прогресс выполнения быстрой сортировки
Посмотрите здесь:

Ошибка на этапе выполнения быстрой сортировки - C++
Ошибка а не пойму в чем,код здеясь:#include<iostream> using namespace std; void main(){ setlocale(LC_ALL, "Ukrainian"); int ar; ...

Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки - C++
Почему вот это : void sort(int *ar, int L, int R){ int i, j, x, buf; x = ar; i = L; j = R; do { ...

Визуализатор быстрой сортировки - C++
Добрый день! Нужно написать программу, которая иллюстрирует работу быстрой сортировки. В частности должно присутствовать: *вывод...

Алгорим быстрой сортировки - C++
В одной из тем выложен алгоритм быстрой сортировки. Возник вопрос: если индексы i и j указывают на один элемент зачем нужен обмен? ...

Визуализация быстрой сортировки - C++
Ребят,может кто помочь с визуальной сортировкой массива.. Нужна быстрая сортировка,но буду рад любому примеру даже на пузырьковой... ...

Метод быстрой сортировки - C++
Доброго времени суток, форумчане. Вчера проходили метод быстрой сортировки. Во входном файле в первой строчке указывается кол-во...

Иллюстрация быстрой сортировки - C++
Ребят,необходимо написать программу похожую на ту,которая тут http://www.cyberforum.ru/csharp-beginners/thread874724.html Помогите...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Raali
623 / 327 / 34
Регистрация: 06.07.2013
Сообщений: 1,056
Завершенные тесты: 1
07.11.2013, 11:58     Прогресс выполнения быстрой сортировки #2
а что за алгоритм, там есть условие выхода из цикла?
alisteas
0 / 0 / 0
Регистрация: 07.10.2013
Сообщений: 13
07.11.2013, 12:06  [ТС]     Прогресс выполнения быстрой сортировки #3
алгоритм использовал вот этот
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void sort(int *a, int tail)
{
    if (a)
    {
        int i = 0;  
        int j = tail;   
        int middle = a[tail / 2];   
 
        do 
        {
            while (a[i] < middle) i++;  
            while (a[j] > middle) j--;  
 
            if (i <= j) 
            {
                int tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        while ( i <= j );   
        if ( j > 0 ) sort(a, j);    
        if ( tail > i ) sort(a + i, tail - i);  
    }
}
Raali
623 / 327 / 34
Регистрация: 06.07.2013
Сообщений: 1,056
Завершенные тесты: 1
07.11.2013, 12:11     Прогресс выполнения быстрой сортировки #4
ну вот и привязать можно к (i / j) * 100%
черт, рекурсию не увидел)

ну судя по этому
Цитата Сообщение от alisteas Посмотреть сообщение
if ( tail > i ) sort(a + i, tail - i);
надо привязывать к i
ПерС
371 / 287 / 89
Регистрация: 05.11.2013
Сообщений: 820
Записей в блоге: 5
Завершенные тесты: 1
07.11.2013, 12:17     Прогресс выполнения быстрой сортировки #5
У алгоритма обработки массива, как правило, есть "мощность" - число операций, зависящее от его размерности n. Например, обработка всех элементов квадратной матрицы имеет мощность n2, а у "пузырька" или иного метода сравнения "каждый с каждым" мощность (n2-n)/2, вот к этому я бы и привязывался.
Рекурсия ничего не меняет, факториал хоть рекурсивно считай, хоть в цикле, но это n умножений для n!
alisteas
0 / 0 / 0
Регистрация: 07.10.2013
Сообщений: 13
07.11.2013, 12:31  [ТС]     Прогресс выполнения быстрой сортировки #6
Цитата Сообщение от Raali Посмотреть сообщение
надо привязывать к i
но для каждого рекурсивного вызова i будет обнуляться, и у каждого рекурсивного вызова будет свое i.
или я не совсем понял как привязать прогресс к i.

Добавлено через 4 минуты
Цитата Сообщение от ПерС Посмотреть сообщение
У алгоритма обработки массива, как правило, есть "мощность" - число операций, зависящее от его размерности n. Например, обработка всех элементов квадратной матрицы имеет мощность n2, а у "пузырька" или иного метода сравнения "каждый с каждым" мощность (n2-n)/2, вот к этому я бы и привязывался.
Рекурсия ничего не меняет, факториал хоть рекурсивно считай, хоть в цикле, но это n умножений для n!
Текст из википедии:
..можно предположить что в среднем глубина рекурсии не превысит 2*log4/3(n) ...
то есть мне нужно сделать счетчик для рекурсивных вызовов и когда он дойдет до показателя 2*log4/3(n) это будет мой 100% прогресс?
Raali
623 / 327 / 34
Регистрация: 06.07.2013
Сообщений: 1,056
Завершенные тесты: 1
07.11.2013, 12:32     Прогресс выполнения быстрой сортировки #7
мне кажется с каждой новой рекурсией после цикла i будет все больше и больше
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2013, 14:06     Прогресс выполнения быстрой сортировки
Еще ссылки по теме:

Тонкости быстрой сортировки - C++
Излазил кучу мест в сети. Нашел массу этих алгоритмов, но на поверку практически каждый не совсем работающий. Представляется, что в этой...

Отображать прогресс выполнения программы - C++
Как построить в c++ чтобы на каждом шаге в окне внизу было видно что делает программа?

Поиск самой быстрой сортировки - C++
Ищу быструю реализацию быстрого алгоритма сортировки массива для среднего случая на С/С++ под Win32. Остальные параметры не имеют значения....

Вопросы насчёт быстрой сортировки - C++
Здравствуйте. Объясните, пожалуйста. Есть алгоритм быстрой сортировки: Код: int shag=1; void quickSort(int arr, int left, int...

Найти ошибку быстрой сортировки - C++
Пытался написать, помогите найти ошибки. Код должен вставит на первое место самое большое четное число из списка и дальше сортировать...


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

Или воспользуйтесь поиском по форуму:
alisteas
0 / 0 / 0
Регистрация: 07.10.2013
Сообщений: 13
07.11.2013, 14:06  [ТС]     Прогресс выполнения быстрой сортировки #8
Цитата Сообщение от Raali Посмотреть сообщение
мне кажется с каждой новой рекурсией после цикла i будет все больше и больше
да, если считать не само значение i а индекс елемента, на который он будет указывать (в общем масиве) то i будет постепенно увелич. пока не дойдет до последнего елемента, но это произойдет лиш в одной ветви рекурсии, то есть если например у нас есть массив на 10 елементов и после первого вызова сорт мы разделили массив на куски по 8 и 2, то во втором куске i дойдет до правого края, но левый кусок еще будет сортироватся

Добавлено через 1 час 28 минут
UPD: сделал счетчик вызовов функции,
100 элементов - примерно 180
1000 - примерно 1700
10000 - примерно 16000
10 000 000 - примерно 1 400 000
Результаты само собой +- т.к. число разбиений (и вызовов) всегда разное
Yandex
Объявления
07.11.2013, 14:06     Прогресс выполнения быстрой сортировки
Ответ Создать тему
Опции темы

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