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

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

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

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

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

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

Ошибка на этапе выполнения быстрой сортировки - 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++
Излазил кучу мест в сети. Нашел массу этих алгоритмов, но на поверку практически каждый не совсем работающий. Представляется, что в этой...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Raali
623 / 327 / 34
Регистрация: 06.07.2013
Сообщений: 1,061
Завершенные тесты: 1
07.11.2013, 11:58 #2
а что за алгоритм, там есть условие выхода из цикла?
0
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);  
    }
}
0
Raali
623 / 327 / 34
Регистрация: 06.07.2013
Сообщений: 1,061
Завершенные тесты: 1
07.11.2013, 12:11 #4
ну вот и привязать можно к (i / j) * 100%
черт, рекурсию не увидел)

ну судя по этому
Цитата Сообщение от alisteas Посмотреть сообщение
if ( tail > i ) sort(a + i, tail - i);
надо привязывать к i
0
ПерС
371 / 287 / 89
Регистрация: 05.11.2013
Сообщений: 820
Записей в блоге: 5
Завершенные тесты: 1
07.11.2013, 12:17 #5
У алгоритма обработки массива, как правило, есть "мощность" - число операций, зависящее от его размерности n. Например, обработка всех элементов квадратной матрицы имеет мощность n2, а у "пузырька" или иного метода сравнения "каждый с каждым" мощность (n2-n)/2, вот к этому я бы и привязывался.
Рекурсия ничего не меняет, факториал хоть рекурсивно считай, хоть в цикле, но это n умножений для n!
0
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% прогресс?
0
Raali
623 / 327 / 34
Регистрация: 06.07.2013
Сообщений: 1,061
Завершенные тесты: 1
07.11.2013, 12:32 #7
мне кажется с каждой новой рекурсией после цикла i будет все больше и больше
0
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
Результаты само собой +- т.к. число разбиений (и вызовов) всегда разное
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2013, 14:06
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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