3 / 3 / 4
Регистрация: 31.01.2013
Сообщений: 98
1

Посчитать число рекурсий

16.06.2014, 23:27. Показов 408. Ответов 0
Метки нет (Все метки)

Доброго времени суток.
Возникла такая проблема: Необходимо считать глубину рекурсии для quicksort. И, если, это число превышает log(n)(то есть наилучший случай), то сортировать массив heapsort-ом.
Сомневаюсь, что данный код правильно выполняет эту задачу.
Подскажите, правильно ли она работает? Если нет, то помогите исправить.
Спасибо.

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
double log(double a, double b)
{
    return log(a) / log(b);
}
 
void heapsort(int array[], int n)
{
    int i, t;
    Heapify(array, n);
    for (i = n - 1; i>0; i--)
    {
        t = array[0];
        array[0] = array[i];
        array[i] = t;
        adjust(array, i);
    }
}
 
void Heapify(int array[], int n)
{
    int item, i, j, k;
    for (k = 1; k < n; k++)
    {
        item = array[k];
        i = k;
        j = (i - 1) / 2;
        while ((i>0) && (item>array[j]))
        {
            array[i] = array[j];
            i = j;
            j = (i - 1) / 2;
        }
        array[i] = item;
    }
}
 
void adjust(int array[], int n)
{
    int item, i, j;
    j = 0;
    item = array[j];
    i = 2 * j + 1;
    while (i <= n - 1)
    {
        if (i + 1 <= n - 1)
        if (array[i] < array[i + 1])
            i++;
        if (item < array[i])
        {
            array[j] = array[i];
            j = i;
            i = 2 * j + 1;
        }
        else
            break;
    }
    array[j] = item;
}
 
void QuickSort(int* q, int low, int high, double depth, double _depth, int n)
{
    int A = low;
    int B = high;
    int mid;
 
    if (high > low)
    {
        mid = q[(high + low)/2]; 
        cout << mid << endl;
        while (A <= B)
        {
            while ((A < high) && (q[A] < mid))
                ++A;
            while ((B > low) && (q[B] > mid))
                --B;
            if (A <= B)
            {
                int temp;
                temp = q[A];
                q[A] = q[B];
                q[B] = temp;
                ++A;
                --B;
            }
        }
        if (low < B)
            _depth = log(B, 2);
        if (_depth > depth)
        {
            heapsort(q, n);
            cout << "HeapSort" << endl;
        }
        else
        {
            QuickSort(q, low, B, depth, _depth, n);
        }
        if (A < high)
            _depth = log(A, 2);
        if (_depth > depth)
        {
            heapsort(q, n);
            cout << "HeapSort" << endl;
        }
        else
        {
            QuickSort(q, A, high, depth, _depth, n);
        }
    }
}
 
int main()
{
    setlocale(LC_ALL, "Rus");
    int  i, q[10000];
    int n = 0;
    double depth, _depth;
 
    cout << "N" << endl;
    cin >> n;
 
    depth = log(n, 2);
    _depth = 0;
 
    for (i = 0; i <= n; i++)
    {
        q[i] = rand() % 100000;
        cout << "Massiv:" << q[i] << " " << endl;
    }
 
    QuickSort(q, 0, n - 1, depth, _depth, n);
    
    for (i = 0; i < n; i = i++)
    {
        cout << q[i] << " ";
    }
    system("pause");
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.06.2014, 23:27
Ответы с готовыми решениями:

Посчитать количество рекурсий
Здравствуйте. Как из функции вывести 2 значения? Или другим методом посчитать количество рекурсий?...

Посчитать количество рекурсий в программе
Всем привет, помогите посчитать количество рекурсий в программе. #include &lt;stdio.h&gt; #include...

Изменяя число i от 1 до n (без пробелов) получить число. Посчитать в нем количество каждых цифр. Посчитать общее число цифр
Дано число n меньше или равно 30 000. Изменяя число i от 1 до n будем записывать получившееся число...

Программирование рекурсий
Функция Аккермана. Даны неотрицательные целые числа n, m. Вычислить A(n,m), где (см рисунок) ...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.06.2014, 23:27
Помогаю со студенческими работами здесь

исключение рекурсий
Здравствуйте! у меня такая проблема(задача) запуск всех исполняемых файлов в указанном в...

Программирование рекурсий.
Здравствуйте) помогте кто знает? Задание.Числа Фибоначчи u0, u1, u2, … определяются следующим...

Ошибка - много рекурсий
Все что должны делать эти две функции - это просто переводить латинские цифры в римские. Но почему...

Максимальное количество рекурсий
Есть функция, которая вызывает саму себя, причем делает она это крайне много раз. Вопрос: какой...

Segmentation fault при рекурсий
Здравствуйте! Есть список продуктов $array_items, хочу вычислить все ветки категорий определенного...

Нужны примеры сложных рекурсий
Приведите Примеры сложных Рекурсий и с использованием сложный рекурсивных процедур !!!


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru