Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Logovas
9 / 9 / 7
Регистрация: 07.11.2015
Сообщений: 115
Завершенные тесты: 1
1

Рекурсия выводит значение счетчика не один раз, а столько, сколько было рекурсивных вызовов

22.03.2016, 21:47. Просмотров 861. Ответов 6
Метки нет (Все метки)

Задача состоит в том, чтобы определить, какой метод сортировки быстрее. В одну функцию (SortBalb) я отправляю массив, и он сортируется пузырьком, в другую (QuickSort) отправляю такой же массив, где он сортируется методом быстрой сортировки(Хоара).
Вывожу время сортировки и количество перестановок. Время выводит нормально, тк это просто.
Вот количество итераций - для пузырька - просто, для QuickSort - получается, что срабатывает printf каждый вызов(что тоже естественно и понятно тк имеем рекурсию). Но не красиво.
Как вывести суммарное количество перестановок для рекурсивной функции QuickSort?

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
#include <stdio.h>
#include <math.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include<Windows.h>
#include<time.h>
 
void PrintArray(int*,int);
void SortBalb(int*,int);
void QuickSort(int*,int);
 
void main()
{
    int n,*arr,*arrForBalb,*arrForQuick;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    srand(time(NULL));
    //puts("Введите размерность массива: ");
    //scanf("%d",&n);
    n=10000;
    arr=new int[n];
    arrForBalb=new int[n];
    arrForQuick=new int[n];
    for(int i=0;i<n;i++)
    {
        *(arr+i)=rand()%100;
        *(arrForBalb+i)=*(arr+i);       //Сразу сохраню сгенеренный массив в массивы, над которыми будем издеваться 
        *(arrForQuick+i)=*(arr+i);
    }
    
    //printf("Сгенерированный массив: \n");
    //PrintArray(arr,n);
    printf("\n");
    SortBalb(arrForQuick,n);            //Издеваемся методом пузырька
    //printf("Отсортированный массив: \n");
    //PrintArray(arrForModify,n);
    printf("\n");
    clock_t timeQuickSort=clock();
    QuickSort(arrForQuick,n-1);         //Издеваемся методом Хоара
    timeQuickSort=clock()-timeQuickSort;
    printf("\nВремя перестановок сортировкой Хоара: %lf секунд \n",(float)timeQuickSort/CLOCKS_PER_SEC);
 
 
    _getch();
}
 
void PrintArray(int*a,int n)
{
for(int i=0;i<n;i++)
    printf("%d, ",*(a+i));
}
 
void SortBalb(int*a,int n)
{
    int temp,countChange=0;
    clock_t timeBalb=clock();
    for(int i=0;i<n;i++)
        for(int j=0;j<n-1;j++)
            if(*(a+j)>*(a+j+1))
            {
                temp=*(a+j+1);
                *(a+j+1)=*(a+j);
                *(a+j)=temp;
                countChange++;
            }
    timeBalb=clock()-timeBalb;
    printf("\nВремя перестановок сортировкой обмена: %lf секунд \n",(float)timeBalb/CLOCKS_PER_SEC);
    //printf("\nКолличество перестановок: %d\n",countChange);
}
 
void QuickSort(int*a,int n)
{   
    int countChangeQuick=0,countChangeQuickTemp=0;
    int sizeForChange=n,left=0,temp;    
    int pivot=*(a+(int)(n/2));
    do
    {
    while(*(a+left)<pivot)
        left++;
    while(*(a+n)>pivot)
        n--;
    if(left<=n)
    {
        temp=*(a+left);
        *(a+left)=*(a+n);
        *(a+n)=temp;
        left++;
        n--;
        
        countChangeQuick++;
    }
    }while(left<=n);
    if(n>0)
        QuickSort(a,n);
    if(sizeForChange>left)
        QuickSort(a+left,sizeForChange-left);   
    printf("\nКолличество перестановок: %d\n",countChangeQuick);
}
Спасибо.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2016, 21:47
Ответы с готовыми решениями:

Файл: Записать max значение в конец файла столько раз, сколько положительных чисел было в исходном файле.
Задача: а) Дан файл f, компоненты- действительными числами. Найти: Наибольшее значение в файле....

Рекурсия, ряд Фибоначчи (определить количество рекурсивных вызовов функции)
Здравствуйте, уважаемые форумчане ! Подскажите, пожалуйста, как определить количество...

Сколько раз нажимаем на кнопку, столько раз выходит картинка
Как реализовать действие: сколько раз нажимаем на кнопку,столько раз выходит картинка. C#

Вывести запись столько раз, сколько требуется
Приветствую! Допустим, есть таблица: ID|TITLE 1|Иванов 2|Петров 3|Сидоров Есть перечень id....

Запуск thread столько раз сколько нужно
Здравствуйте дорогие форумчане!:scratch: Нужно мне реализовать один thread внутри того же класса...

6
liv
1144 / 929 / 196
Регистрация: 07.10.2015
Сообщений: 3,010
Завершенные тесты: 1
22.03.2016, 21:52 2
При вызове QuickSort добавить еще один параметр: адрес заранее обнуленного целого - счетчика перестановок.
При каждой перестановке инкрементировать счетчик по указателю.
Затем, вместе со временем, вывести и значение счетчика
1
Logovas
9 / 9 / 7
Регистрация: 07.11.2015
Сообщений: 115
Завершенные тесты: 1
22.03.2016, 22:00  [ТС] 3
Я сразу об этом подумал.
Так и сделал, единственное, что у меня через условие:
C
1
2
3
4
    if(n>0)
        QuickSort(a,n);
    if(sizeForChange>left)
        QuickSort(a+left,sizeForChange-left);
Я добавил еще один аргумент в QuickSort и туда и туда, стал его выводить, получается еще эпичнее.
Короче не получилось и я решил попросить помощи.
А где тогда писать printf для счетчика, надо же в мэйн, но мэйн не видит счетчика.
0
liv
1144 / 929 / 196
Регистрация: 07.10.2015
Сообщений: 3,010
Завершенные тесты: 1
23.03.2016, 11:24 4
Именно в main задать обнуленный счетчик и вызвать QuickSort с параметром - адресом этой переменной.
Дальше, по рекурсии передавать этот адрес дальше. Т.о., будет инкрементироваться одна и та же переменная, заданная в main-е.
После завершения останется только ее вывести
1
Logovas
9 / 9 / 7
Регистрация: 07.11.2015
Сообщений: 115
Завершенные тесты: 1
23.03.2016, 17:16  [ТС] 5
Сделал, как Вы сказали.
Объявил переменную countChangeQuick - счетчик в main. Ее же передаю в качестве аргумента.
Но на консоль печатает: 2 перестановки при 10 элементах в массиве(что не реально).
Ставлю точку останова перед работой функции и прохожу F10 и вижу, как счетчик countChangeQuick увеличивается. Но когда рекурсия начинает "возвращаться", наблюдаю, как countChangeQuick уменьшается, уменьшается и в итоге возвращается к двум. Двойка и возвращается ретерном.
Скорее всего я не правильно отправляю countChangeQuick в функцию. Пробую по адресу, но тогда начинает ругаться линковщик. Уже просто перепробовал все сочетания & и *.

Помогите пожалуйста правильно передать счетчик в функцию QuickSort.

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
#include <stdio.h>
#include <math.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include<Windows.h>
#include<time.h>
 
void PrintArray(int*,int);
void SortBalb(int*,int);
int QuickSort(int*,int,int);
 
void main()
{
    int n,*arr,*arrForBalb,*arrForQuick;
    int countChangeQuick=0,countChangeQuickTemp=0;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    srand(time(NULL));
    //puts("Введите размерность массива: ");
    //scanf("%d",&n);
    n=10;
    arr=new int[n];
    arrForBalb=new int[n];
    arrForQuick=new int[n];
    for(int i=0;i<n;i++)
    {
        *(arr+i)=rand()%100;
        *(arrForBalb+i)=*(arr+i);       //Сразу сохраню сгенеренный массив в массивы, над которыми будем издеваться 
        *(arrForQuick+i)=*(arr+i);
    }
    
    //printf("Сгенерированный массив: \n");
    //PrintArray(arr,n);
    printf("\n");
    SortBalb(arrForQuick,n);            //Издеваемся методом пузырька
    //printf("Отсортированный массив: \n");
    //PrintArray(arrForModify,n);
    printf("\n");
    clock_t timeQuickSort=clock();
    QuickSort(arrForQuick,n-1,countChangeQuick);            //Издеваемся методом Хоара
    timeQuickSort=clock()-timeQuickSort;
    printf("\nВремя перестановок сортировкой Хоара: %lf секунд \n",(float)timeQuickSort/CLOCKS_PER_SEC);
    printf("\nКолличество перестановок быстрой сортировкой: %d\n",QuickSort(arrForQuick,n-1,countChangeQuick));
 
    _getch();
}
 
void PrintArray(int*a,int n)
{
for(int i=0;i<n;i++)
    printf("%d, ",*(a+i));
}
 
void SortBalb(int*a,int n)
{
    int temp,countChange=0;
    clock_t timeBalb=clock();
    for(int i=0;i<n;i++)
        for(int j=0;j<n-1;j++)
            if(*(a+j)>*(a+j+1))
            {
                temp=*(a+j+1);
                *(a+j+1)=*(a+j);
                *(a+j)=temp;
                countChange++;
            }
    timeBalb=clock()-timeBalb;
    printf("\nВремя перестановок сортировкой обмена: %lf секунд \n",(float)timeBalb/CLOCKS_PER_SEC);
    //printf("\nКолличество перестановок: %d\n",countChange);
}
 
int QuickSort(int*a,int n,int countChangeQuick)
{   
    
    int sizeForChange=n,left=0,temp;    
    int pivot=*(a+(int)(n/2));
    do
    {
    while(*(a+left)<pivot)
        left++;
    while(*(a+n)>pivot)
        n--;
    if(left<=n)
    {
        temp=*(a+left);
        *(a+left)=*(a+n);
        *(a+n)=temp;
        left++;
        n--;        
    }
    }while(left<=n);
 
    if(n>0)
        QuickSort(a,n,++countChangeQuick);
    if(sizeForChange>left)
        QuickSort(a+left,sizeForChange-left,++countChangeQuick);    
 
    return countChangeQuick;
}
0
liv
1144 / 929 / 196
Регистрация: 07.10.2015
Сообщений: 3,010
Завершенные тесты: 1
23.03.2016, 17:47 6
Лучший ответ Сообщение было отмечено Logovas как решение

Решение

Ну смотри
Я добавил необходимые h-ки, они у тебя, наверное, в stdafx.h
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
#include<windows.h>
#include<time.h>
#include<stdio.h>
#include<conio.h> 
 
void PrintArray(int*,int);
void SortBalb(int*,int);
void QuickSort(int*,int,int*);
 
void main()
{
    int n,*arr,*arrForBalb,*arrForQuick;
    int countChangeQuick=0,countChangeQuickTemp=0;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    srand(time(NULL));
//    puts("Введите размерность массива: ");
//    scanf("%d",&n);
    n=10;
    arr=new int[n];
    arrForBalb=new int[n];
    arrForQuick=new int[n];
    for(int i=0;i<n;i++)
    {
        *(arr+i)=rand()%100;
        *(arrForBalb+i)=*(arr+i);       //Сразу сохраню сгенерированный массив в массивы, над которыми будем издеваться 
        *(arrForQuick+i)=*(arr+i);
    }
    
    //printf("Сгенерированный массив: \n");
    //PrintArray(arr,n);
    printf("\n");
    SortBalb(arrForQuick,n);            //Издеваемся методом пузырька
    //printf("Отсортированный массив: \n");
    //PrintArray(arrForModify,n);
    printf("\n");
    clock_t timeQuickSort=clock();
    QuickSort(arrForQuick,n-1,&countChangeQuick);            //Издеваемся методом Хоара
    timeQuickSort=clock()-timeQuickSort;
    printf("\nВремя перестановок сортировкой Хоара: %lf секунд \n",(float)timeQuickSort/CLOCKS_PER_SEC);
    printf("\nКоличество перестановок быстрой сортировкой: %d\n",countChangeQuick);
 
    _getch();
}
 
void PrintArray(int*a,int n)
{
for(int i=0;i<n;i++)
    printf("%d, ",*(a+i));
}
 
void SortBalb(int*a,int n)
{
    int temp,countChange=0;
    clock_t timeBalb=clock();
    for(int i=0;i<n;i++)
        for(int j=0;j<n-1;j++)
            if(*(a+j)>*(a+j+1))
            {
                temp=*(a+j+1);
                *(a+j+1)=*(a+j);
                *(a+j)=temp;
                countChange++;
            }
    timeBalb=clock()-timeBalb;
    printf("\nВремя перестановок сортировкой обмена: %lf секунд \n",(float)timeBalb/CLOCKS_PER_SEC);
    printf("\nКоличество перестановок: %d\n",countChange);
}
 
void QuickSort(int*a,int n,int *pcountChangeQuick)
{   
    
    int sizeForChange=n,left=0,temp;    
    int pivot=*(a+(int)(n/2));
    do
    {
    while(*(a+left)<pivot)
        left++;
    while(*(a+n)>pivot)
        n--;
    if(left<=n)
    {
        temp=*(a+left);
        *(a+left)=*(a+n);
        *(a+n)=temp;
        left++;
        n--;
        ++(*pcountChangeQuick);
    }
    }while(left<=n);
 
    if(n>0)
        QuickSort(a,n,pcountChangeQuick);
    if(sizeForChange>left)
        QuickSort(a+left,sizeForChange-left,pcountChangeQuick);    
}
Добавлено через 1 минуту
Я ж говорил: передавать адрес счетчика, а не сам счетчик
1
Logovas
9 / 9 / 7
Регистрация: 07.11.2015
Сообщений: 115
Завершенные тесты: 1
23.03.2016, 18:16  [ТС] 7
Теперь мне понятно и все работает.
+1 к моим скилам по рекурсии
Огромное спасибо за помощь!!!
0
23.03.2016, 18:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.03.2016, 18:16

Определить вероятность того, что в 1-ом ящике осталось столько же белых шаров, сколько было вначале
В 1-ом ящике 10 белых и 12 черных шаров; во втором 10 белых и 16 черных шаров. Одновременно из 1-го...

Вывести символ столько раз, сколько введет пользователь
Ребят, подскажите, пожалуйста как вывести символ (любой) столько раз, сколько введет пользователь?...

Вывести надпись в строке столько раз, сколько выведено строк
Мне нужно сделать что то на подобии прогрессии. Объясняю: Ставится цикл на for(int i=1; i...


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

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

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