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

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

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

C++ Поиск самой быстрой сортировки
Вопросы насчёт быстрой сортировки C++
Реализовать алгоритм быстрой сортировки C++
C++ Тонкости быстрой сортировки
C++ Алгорим быстрой сортировки
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Raali
572 / 276 / 12
Регистрация: 06.07.2013
Сообщений: 917
Завершенные тесты: 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
572 / 276 / 12
Регистрация: 06.07.2013
Сообщений: 917
Завершенные тесты: 1
07.11.2013, 12:11     прогресс выполнения быстрой сортировки #4
ну вот и привязать можно к (i / j) * 100%
черт, рекурсию не увидел)

ну судя по этому
Цитата Сообщение от alisteas Посмотреть сообщение
if ( tail > i ) sort(a + i, tail - i);
надо привязывать к i
ПерС
366 / 282 / 84
Регистрация: 05.11.2013
Сообщений: 806
Записей в блоге: 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
572 / 276 / 12
Регистрация: 06.07.2013
Сообщений: 917
Завершенные тесты: 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++

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

Или воспользуйтесь поиском по форуму:
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     прогресс выполнения быстрой сортировки
Ответ Создать тему
Опции темы

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