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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Строки и функции http://www.cyberforum.ru/cpp-beginners/thread734706.html
Вот что я не так делаю? По моей логике есть Первая строка (задана в main). Есть функция, в которой есть Вторая строка. В первой строке есть символ, который ищется во второй строке и если символ найден, то должен произойти перевод на новую строку. НО перехода не происходит из-за моей какой-то ошибки. #include <iostream> using namespace std; bool func(char *P,char ch) { char *M="+-*/";...
C++ Указатель на функцию Делаю класс кнопки для проекта. Есть такой код: class CUIButton { public: CUIButton(); virtual ~CUIButton(); private: void (*)() m_callback; // <-ERROR :"..\src\UI\/UIButton.h:17: error: expected unqualified-id before ')' token" }; Однако проект не компилируется. Можете подсказать почему? http://www.cyberforum.ru/cpp-beginners/thread734684.html
Описать запись с именем MARSH C++
Описати запис з ім*ям MARSH, що містить наступні поля: Описать запись с именем MARSH, содержащий следующие поля: 1 имя начального пункта маршрута 2 Название конечного пункта маршрута 3 номер маршрута
Написать код для игры НИМ. проверьте пожалуйста тот ли это код C++
#include <string> using namespace std; int compChoose(int markers); int userChoose(int markers); int random() {
C++ Реклама языка С++ http://www.cyberforum.ru/cpp-beginners/thread734659.html
Всем привет. Такой вопрос возник! Задали доклад на тему "Реклама языка С++". 1) Если писать в MFC, то как вывести анимационный текст или анимацию. 2) Можно в консоли или в том же MFC. Вывести текст любой непосредственно на рабочий стол! Как то так. Кто сможет мне помочь??? Желательно примеры. Заранее спасибо!
C++ итератора для собственного вектора помогите пожалуйста сделать итератор для вектора template <class T> class myvector { private: int top;//сколько элементов в векторе T* arr; int sz;//максимальное количество элементов в векторе public: myvector(int=0);//конструктор по умолчанию подробнее

Показать сообщение отдельно
m1namoto
0 / 0 / 0
Регистрация: 23.06.2012
Сообщений: 51
17.12.2012, 00:48     Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки
Почему вот это :
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;
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 06:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru