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

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

Восстановить пароль Регистрация
 
CMson
2 / 2 / 2
Регистрация: 31.01.2013
Сообщений: 96
16.06.2014, 23:27     Посчитать число рекурсий #1
Доброго времени суток.
Возникла такая проблема: Необходимо считать глубину рекурсии для 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");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.06.2014, 23:27     Посчитать число рекурсий
Посмотрите здесь:

C++ Посчитать число имени
C++ Программирование рекурсий
C++ Программирование рекурсий: отделить цифры данного числа и сложить межу собой
Программирование рекурсий. Преобразование числа в двоичное C++
C++ Программирование рекурсий. Преобразование числа в двоичное
C++ Программирование рекурсий.
Дано натуральное число, посчитать последовательность и т.д. C++
Дано натуральное число n. Посчитать S=1+1/2+1/3...+1/n C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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