0 / 0 / 0
Регистрация: 23.06.2012
Сообщений: 51
1

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

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

Author24 — интернет-сервис помощи студентам
Почему вот это :
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
17.12.2012, 00:48
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
17.12.2012, 00:48
Ответы с готовыми решениями:

Определение времени выполнения алгоритма быстрой сортировки
Доброго времени суток всем, прошу помощи, не могу понять в чем проблема и как ее решить. Нужно определить время выполнения алгоритма, оно...

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

Создать программу реализующую два алгоритма сортировки одномерного массива: методом Шелла и быстрой сортировки
ЗАДАЧА. Создать программу реализующую два алгоритма сортировки одномерного массива: сортировка методом Шелла и быстрой сортировки (Хоара)....

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

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

Не уверен, что упрощение стэка поможет, так как рекурсия -- суть то же помещение переменных в стек, только самим компилятором.
0
0 / 0 / 0
Регистрация: 23.06.2012
Сообщений: 51
17.12.2012, 15:39  [ТС] 3
Только кроме помещения переменных еще адреса возвратов, передача управления по этим адресам...
Получается STL не особо производительная ? Скорее универсальная ?
0
 Аватар для lemegeton
4873 / 2670 / 916
Регистрация: 29.11.2010
Сообщений: 5,757
17.12.2012, 16:37 4
Цитата Сообщение от m1namoto Посмотреть сообщение
Получается STL не особо производительная ? Скорее универсальная ?
Конечно. Производительность помещения значений в стек вызова гораздо дешевле, чем работа с STL стеком.
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.12.2012, 17:04 5
У вас не студия случаем? По умолчанию стек реализован через дек, а в студии он дико тормозит. Попробуйте поставить вектор.
0
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
17.12.2012, 18:15
Помогаю со студенческими работами здесь

Реализация рекурсивного алгоритма сортировки пузырьком
Реализовать сортировку пузырьком с помощью рекурсивных функций. Вот моя пузырьком без рекурсии: public void BubbleSort(int a, ref int...

Реализация рекурсивного алгоритма сортировки выбором
Реализуйте рекурсивный алгоритм упорядочения по возрастанию заданного массива из n различных целых чисел методом сортировки выбором. ...

Сравнить число перестановок при использовании сортировки "пузырьком", методом выбора и алгоритма быстрой сортировки
Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки &quot;пузырьком&quot;, методом выбора и...

Реализация алгоритма быстрой сортировки quickSort
это алгоритм быстрой сортировки quickSort прошу напишите значение строк файл исходного кода qs.cpp : #include...

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


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

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

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Опции темы

Новые блоги и статьи
Использование кэша Laravel - полный гайд
bytestream 18.02.2025
Кэширование - один из наиболее эффективных способов повышения производительности веб-приложений. В современном мире, где скорость загрузки страниц напрямую влияет на удержание пользователей и. . .
Создаем REST API в Laravel с аутентификацией через Passport
bytestream 18.02.2025
Разработка современных веб-приложений все чаще требует создания надежного и хорошо структурированного API. REST API стал стандартом де-факто для построения взаимодействия между клиентской и серверной. . .
Пайплайны в Laravel - полный гайд
bytestream 18.02.2025
Разработка современных веб-приложений часто требует обработки сложных процессов, состоящих из множества последовательных шагов. Например, при создании системы комментариев может потребоваться. . .
Как правильно использовать @required в Symfony
bytestream 18.02.2025
При разработке приложений на Symfony мы часто сталкиваемся с необходимостью внедрения зависимостей. Фреймворк предоставляет несколько способов управления этим процессом, и одним из таких инструментов. . .
Система безопасности в Laravel: возможности и примеры
Wired 18.02.2025
Каждый день появляются новые виды атак и уязвимостей, которые могут поставить под угрозу конфиденциальные данные пользователей и функционирование всей системы. В этом контексте выбор надежного. . .
Давайте сравним Django и Laravel
Wired 18.02.2025
Django и Laravel - два мощных инструмента, которые часто сравнивают между собой. Оба фреймворка предлагают разработчикам богатый набор возможностей для создания масштабируемых веб-приложений, но. . .
Laravel или React - что лучше?
Wired 18.02.2025
В разработке веб выбор правильного инструмента часто определяет успех всего проекта. Особенно интересным представляется сравнение Laravel и React - двух популярных технологий, которые часто. . .
Laravel 11: новые возможности, гайд по обновлению
Wired 18.02.2025
Laravel 11 - это новая масштабная версия одного из самых популярных PHP-фреймворков, выпущенная в марте 2024 года. Эта версия продолжает традицию внедрения передовых технологий и методологий. . .
Миграции в Laravel
Wired 18.02.2025
Разработка веб-приложений на Laravel неразрывно связана с управлением структурой базы данных. При работе над проектом часто возникает необходимость вносить изменения в схему базы данных - добавлять. . .
Аутентификация в Laravel
Wired 18.02.2025
В современном мире веб-разработки безопасность пользовательских данных становится критически важным аспектом любого приложения. Laravel, как один из самых популярных PHP-фреймворков, предоставляет. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru