Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
m1namoto
0 / 0 / 0
Регистрация: 23.06.2012
Сообщений: 51
#1

Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки

17.12.2012, 00:48. Просмотров 1283. Ответов 5
Метки нет (Все метки)

Почему вот это :
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
void sort(int *ar, int L, int R){
    int i, j, x, buf;
    x = ar[(L+R)/2];
    i = L;
    j = R;
    do
    {
        while(ar[i]<x)
            i++;
        while(ar[j]>x)
            j--;
        if(i<=j){
            buf = ar[i];
            ar[i] = ar[j];
            ar[j] = buf;
            i++;
            j--;
        }
    }
        while(i<=j);
 
        if(j>L)
            sort(ar, L, j);
        if(i<R)
            sort(ar, i, R);
    }
 
void sortQuick(int *ar, int cnt){
    int L, R;
    L = 0;
    R = cnt - 1;
    sort(ar, L, R);
}
выполняется быстрее чем вот это:
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
void Quick(int *arr, int cnt) {
      int base, left, right, i, j;
      base = left = right = i = j = 0;
      stack<int> st;
 
      st.push(cnt - 1);
      st.push(0);
 
      do {
 
          left = st.top();
          st.pop();
 
          right = st.top();
          st.pop();
 
 
              base = arr[(left + right) / 2];
              i = left;
              j = right;
 
              do {
                  while(base > arr[i])
                      ++i;
                  while(arr[j] > base)
                      --j;
                  if (i <= j) {
                      swap(arr, i++, j--);
                  }
              } while (i <= j);
 
          if (left < j) {
              st.push(j);
              st.push(left);
          }
          if (i < right) {
              st.push(right);
              st.push(i);
          }
      } while(!st.empty());
  }
Рекурсия ведь должна медленнее работать. Или нет ?
Проверяю таким образом :
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(){
srand(time(NULL));
int ar[100000];
for(int i=0; i<100000; i++){
    ar[i] = rand() % 1000;
}
cout << "Start:" << endl;
 
for(int i=0; i<100000; i++){
    cout << ar[i] << " ";
}
 
cout << endl;
cout << "Result:" << endl;
unsigned int start_time =  clock(); // начальное время
Quick(ar, 100000);
//sortQuick(ar, 100000);
unsigned int end_time = clock(); // конечное время
unsigned int search_time = end_time - start_time; // искомое время
for(int i=0; i<100000; i++){
    cout << ar[i] << " ";
}
cout << endl <<  "TIME = " << search_time;
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.12.2012, 00:48
Ответы с готовыми решениями:

Сравнение рекурсивного параллелизма и последовательной рекурсивной программы для реализации алгоритма быстрой
Добрый вечер, есть задача и код: Напишите последовательную рекурсивную...

Реализация алгоритма быстрой сортировки quickSort
это алгоритм быстрой сортировки quickSort прошу напишите значение строк ...

Прогресс выполнения быстрой сортировки
хочу написать простой консольный прогресс бар, отображающий ход выполнения...

Ошибка на этапе выполнения быстрой сортировки
Ошибка а не пойму в чем,код здеясь:#include&lt;iostream&gt; using namespace std;...

Время выполнения алгоритма
#include &lt;iostream&gt; #include &lt;cstdlib&gt; #include &lt;time.h&gt; using namespace...

5
lemegeton
2933 / 1362 / 467
Регистрация: 29.11.2010
Сообщений: 2,725
17.12.2012, 09:15 #2
Цитата Сообщение от m1namoto Посмотреть сообщение
Рекурсия ведь должна медленнее работать. Или нет ?
Рекурсия будет быстрее работать за счет более быстрого "стека".

В не-рекурсивном варианте у вас используется довольно "тяжелая" структура данных, которая, в общем-то, и просаживает производительность.

Не уверен, что упрощение стэка поможет, так как рекурсия -- суть то же помещение переменных в стек, только самим компилятором.
0
m1namoto
0 / 0 / 0
Регистрация: 23.06.2012
Сообщений: 51
17.12.2012, 15:39  [ТС] #3
Только кроме помещения переменных еще адреса возвратов, передача управления по этим адресам...
Получается STL не особо производительная ? Скорее универсальная ?
0
lemegeton
2933 / 1362 / 467
Регистрация: 29.11.2010
Сообщений: 2,725
17.12.2012, 16:37 #4
Цитата Сообщение от m1namoto Посмотреть сообщение
Получается STL не особо производительная ? Скорее универсальная ?
Конечно. Производительность помещения значений в стек вызова гораздо дешевле, чем работа с STL стеком.
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.12.2012, 17:04 #5
У вас не студия случаем? По умолчанию стек реализован через дек, а в студии он дико тормозит. Попробуйте поставить вектор.
0
m1namoto
0 / 0 / 0
Регистрация: 23.06.2012
Сообщений: 51
17.12.2012, 18:15  [ТС] #6
Сделал на базе массива стек, разница результатов рекурсивной и итерационной реализации колеблется в районе 1 мс) То есть, можно говорить об одинаковом результате ... Где же тот прирост быстродействия в итерационной реализации, описанный в n-ом количестве источников ?
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
struct my_stack{
    int l, r;
};
 
void QuickA(int *arr, int cnt) {
      int top, base, left, right, i, j;
      base = left = right = i = j = 0;
      my_stack st[1000];
      top = 0;
 
 
 
      st[0].r = (cnt - 1);
      st[0].l = 0;
 
      do {
 
          left = st[top].l;
 
 
          right = st[top].r;
          top--;
 
 
 
              base = arr[(left + right) / 2];
              i = left;
              j = right;
 
              do {
                  while(base > arr[i])
                      ++i;
                  while(arr[j] > base)
                      --j;
                  if (i <= j) {
                      swap(arr, i++, j--);
                  }
              } while (i <= j);
 
          if (left < j) {
              top++;
              st[top].r = j;
              st[top].l = left;
          }
          if (i < right) {
              top++;
              st[top].r = right;
              st[top].l = i;
          }
      } while(top!=-1);
  }
А выполняю в Qt Creator, а не в студии.
0
17.12.2012, 18:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.12.2012, 18:15

Рассчитать время выполнения алгоритма
рассчитать время выполнения алгоритма со сложностью О (n^2) для n=10000 если...

Время выполнения сортировки
Всем доброго времени суток. Дело такое: задача стоит оценить сортировки по...

Подсчёт время работы алгоритма сортировки
Пытаюсь посчитать время работы алгоритма в миллисекундах, но постоянно выходит...


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

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

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