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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
WriterMix
1 / 1 / 0
Регистрация: 06.11.2011
Сообщений: 68
#1

Сравнение алгоритмов сортировок - C++

20.09.2012, 19:55. Просмотров 1164. Ответов 4
Метки нет (Все метки)

Добрый день всем!
Интересует вопрос об оптимизации алгоритмов сортировки: пузирька, пузирька оптимиз. и Шейкера. Подскажите:
1) Как сделать так, чтоб обрабативались одни и те же генерируемие числа? (Сортировка возрастает в 2 раза (данный код) когда в каждом case генерируються числа. Например, сортировка 50.000 елементов должна происходить чуть больше 5 сек, а у меня больше 10 сек.)
2) Правильно ли написан код сортировки Пузирька-оптимизация и Шейкера?
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
138
139
140
141
142
//PZAS-21-2012
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
using namespace std;
 
void bubbleSortS(int* m, int n)
{
 
     for(int i = n - 1; i >= 1; i--)
       for(int j = 0; j < i; j++)
       {
               if(m[j] > m[j+1])
               {
                       int foo = m[j];
                       m[j] = m[j+1];
                       m[j+1] = foo;
               }
       }
 
}
 
void bubbleSortM(int *m, int n)
    {
        for(int i=0; i<n; i++)
        {  
          bool flag = false;
           for(int j=0; j<n-i-1; j++)
           {
              if(m[j]>m[j+1])
              {
                flag = true;
                 int temp = m[j+1];
                 m[j+1] = m[j];
                 m[j] = temp;
              }
           }
          
          if(!flag){ 
             return; 
          } 
       }
}
 
void Shaker(int *m, int n)
{
int i,left,right,b;
int t;
for(right=n-1,left=0,b=-1;b!=0;)//устанавливаем правую и левую границу
{
b=0;
    for(i=left;i<right;i++)//двигаемся с лева на право
    {
        if(m[i]>m[i+1])
        {t=m[i];m[i]=m[i+1];m[i+1]=t;b=i;}
    }
    right=b;
    for(i=right;i>left;i--)//двигаемся с права на лево
    {
        if(m[i-1]>m[i])
        {t=m[i];m[i]=m[i-1];m[i-1]=t;b=i;}
    }
    left=b;
 
}
}
 
int main ()
{
    //cout << "Cin Numer of Elements: ";
    int choise, choise2;
    int n = 50000;
    //cin >> n;
do 
{
cout<<"Choose: Bubble Sort Standart (1), Modify (2), Shaker (3): ";
cin>>choise;
switch(choise)
{
case 1:
{
    int* m;
    m = new int[n];
    srand(time(NULL));
    for(int i=0;i!=n;i++)
    m[i] = rand()%(n+1);
    cout << endl;
clock_t time;
time = clock();
bubbleSortS (m, n);
time = clock() - time;
cout<<endl<<endl<<endl;
printf("%f", (double)time/CLOCKS_PER_SEC); //время выполнения "каких-то действий"
cout<<endl<<endl<<endl; 
break;
}
case 2:
{
    int* m;
    m = new int[n];
    srand(time(NULL));
    for(int i=0;i!=n;i++)
    m[i] = rand()%(n+1);
    cout << endl;
clock_t time;
time = clock();
bubbleSortM (m, n);
time = clock() - time;
cout<<endl<<endl<<endl;
printf("%f", (double)time/CLOCKS_PER_SEC); //время выполнения "каких-то действий"
cout<<endl<<endl<<endl;
break;
}
case 3:
{
    int* m;
    m = new int[n];
    srand(time(NULL));
    for(int i=0;i!=n;i++)
    m[i] = rand()%(n+1);
    cout << endl;
clock_t time;
time = clock();
Shaker(m, n);
time = clock() - time;
cout<<endl<<endl<<endl;
printf("%f", (double)time/CLOCKS_PER_SEC); //время выполнения "каких-то действий"
cout<<endl<<endl<<endl;
break;
} 
}
cout<<"Do you want to choose other algorithm? (Yes - 1; No - 0) ";
cin>>choise2;
}
while (choise2 == 1);
    //cout << "After sort" << endl;
    //for(int i = 0; i < n; i++)
    //cout << m[i] << ' ';
    cin.get();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.09.2012, 19:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сравнение алгоритмов сортировок (C++):

Сравнение алгоритмов сортировок - C++
Помогите пожалуйста! Очень надо написать программу. Задание такое: Разработать программу на языке «Си», реализующую четыре различных...

Нужны примеры алгоритмов сортировок - C++
срочно нужна помощь!!! нужны легкие и понятные примеры на данные алгоритмы: selection sort merge sort bubble sort quick sort

почему так много алгоритмов сортировок - C++
почему так много алгоритмов сортировок?

Сравнение сортировок - C++
Помогите с подсчетом количества сравнений в сортировках. Проблема заключается в том, что количество операций у сортировок практически...

ЛР: Сравнение сортировок - C++
нужно экспериментально сравнить временную сложность и провести качественный анализ трех сортировок: выбором шейкерная слиянием...

Сравнение 2-х сортировок массива - C++
Есть два метода сортировки массива Вставки и Пузырька. Как их сравнить, что бы узнать, который из них лучше сортирует. Если я не ошибаюсь,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
DiffEreD
1430 / 767 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
20.09.2012, 20:51 #2
Ну а теперь сравните с алгоритмом sort из STL:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
case  4:
            {
                int* m;
                m = new int[n];
                srand(time(NULL));
                for(int i=0;i!=n;i++)
                    m[i] = rand()%(n+1);
                cout << endl;
                clock_t time;
                time = clock();
                sort(m, m+n);
                time = clock() - time;
                cout<<endl<<endl<<endl;
                printf("%f", (double)time/CLOCKS_PER_SEC); //время выполнения "каких-то действий"
                cout<<endl<<endl<<endl;
                break;
            }
WriterMix
1 / 1 / 0
Регистрация: 06.11.2011
Сообщений: 68
20.09.2012, 22:09  [ТС] #3
Цитата Сообщение от yuron_477 Посмотреть сообщение
Ну а теперь сравните с алгоритмом sort из STL:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
case  4:
            {
                int* m;
                m = new int[n];
                srand(time(NULL));
                for(int i=0;i!=n;i++)
                    m[i] = rand()%(n+1);
                cout << endl;
                clock_t time;
                time = clock();
                sort(m, m+n);
                time = clock() - time;
                cout<<endl<<endl<<endl;
                printf("%f", (double)time/CLOCKS_PER_SEC); //время выполнения "каких-то действий"
                cout<<endl<<endl<<endl;
                break;
            }
Спасибо, я попробую.
Но как мне сделать массив рандомних чисел для всех функций? А то получаеться так: либо для первой функции - но скорость сортировки больше 5 секунд. А остальные тогда не работают. Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main ()
{
    //cout << "Cin Numer of Elements: ";
    int choise, choise2;
    int n = 50000;
    //cin >> n;
do 
{
...
{
case 1:
{
    int* m;
    m = new int[n];
    
    for(int i=0;i!=n;i++)
    {srand(time(NULL)); m[i] = rand()%(n+1);}
    cout << endl;
Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
20.09.2012, 22:26 #4
непонятно что вы хотите... один массив отсортировать разными алгоритмами?
если так, то создайте и заполните массив вне case ветвей, сделайте 2 его копии и каждую копию отстортируйте нужным алгоритмом.
WriterMix
1 / 1 / 0
Регистрация: 06.11.2011
Сообщений: 68
21.09.2012, 00:06  [ТС] #5
Цитата Сообщение от ZoRT Посмотреть сообщение
непонятно что вы хотите... один массив отсортировать разными алгоритмами?
если так, то создайте и заполните массив вне case ветвей, сделайте 2 его копии и каждую копию отстортируйте нужным алгоритмом.
Всеравно не работает 2-й и 3-й алгоритм.
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
138
139
140
141
142
143
144
145
146
147
148
149
// Лабораторна робота №2.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
//#include <stdlib.h>
#include <string>
#include <time.h>
#include <conio.h>
using namespace std;
 
void bubbleSortS(int* m, int n)
{
 
     for(int i = n - 1; i >= 1; i--)
       for(int j = 0; j < i; j++)
       {
               if(m[j] > m[j+1])
               {
                       int foo = m[j];
                       m[j] = m[j+1];
                       m[j+1] = foo;
               }
       }
 
}
 
void bubbleSortM(int *m, int n)
    {
        for(int i=0; i<n; i++)
        {  
          bool flag = false;
           for(int j=0; j<n-i-1; j++)
           {
              if(m[j]>m[j+1])
              {
                flag = true;
                 int temp = m[j+1];
                 m[j+1] = m[j];
                 m[j] = temp;
              }
           }
          
          if(!flag){ 
             return; 
          } 
       }
}
 
void Shaker(int *m, int n)
{
int i,left,right,b;
int t;
for(right=n-1,left=0,b=-1;b!=0;)//устанавливаем правую и левую границу
{
b=0;
    for(i=left;i<right;i++)//двигаемся с лева на право
    {
        if(m[i]>m[i+1])
        {t=m[i];m[i]=m[i+1];m[i+1]=t;b=i;}
    }
    right=b;
    for(i=right;i>left;i--)//двигаемся с права на лево
    {
        if(m[i-1]>m[i])
        {t=m[i];m[i]=m[i-1];m[i-1]=t;b=i;}
    }
    left=b;
 
}
}
 
int main ()
{
    //cout << "Cin Numer of Elements: ";
    int choise, choise2;
    int n = 500;
    //cin >> n;
    int* m;
    int* m2;
    int* m3;
    m = new int[n];
    m2 = new int[n];
    m3 = new int[n];
        for(int i=0;i!=n;i++)
    {
        srand(time(NULL)); 
        m[i] = rand()%(n+1);
        memcpy(m2, m, sizeof(m));
        memcpy(m3, m, sizeof(m));
    }
do 
{
cout<<"Choose: Bubble Sort Standart (1), Modify (2), Shaker (3): ";
cin>>choise;
switch(choise)
{
case 1:
{
    //for(int i=0;i!=n;i++)
    //{srand(time(NULL)); m[i] = rand()%(n+1);}
    //cout << endl;
clock_t time;
time = clock();
bubbleSortS (m, n);
time = clock() - time;
cout<<endl<<endl<<endl;
printf("%f", (double)time/CLOCKS_PER_SEC); //время выполнения "каких-то действий"
cout<<endl<<endl<<endl; 
break;
}
case 2:
{
    /*for(int i=0;i!=n;i++)
    {srand(time(NULL)); m2[i] = rand()%(n+1);}
    cout << endl;*/
clock_t time;
time = clock();
bubbleSortM (m2, n);
time = clock() - time;
cout<<endl<<endl<<endl;
printf("%f", (double)time/CLOCKS_PER_SEC); //время выполнения "каких-то действий"
cout<<endl<<endl<<endl;
break;
}
case 3:
{
    //for(int i=0;i!=n;i++)
    //{srand(time(NULL)); m2[i] = rand()%(n+1);}
    //cout << endl;
clock_t time;
time = clock();
Shaker(m, n);
time = clock() - time;
cout<<endl<<endl<<endl;
printf("%f", (double)time/CLOCKS_PER_SEC); //время выполнения "каких-то действий"
cout<<endl<<endl<<endl;
break;
} 
}
cout<<"Do you want to choose other algorithm? (Yes - 1; No - 0) ";
cin>>choise2;
}
while (choise2 == 1);
    //cout << "After sort" << endl;
    //for(int i = 0; i < n; i++)
    //cout << m[i] << ' ';
    cin.get();
}
Добавлено через 39 минут
Все заработало! Скопировал массивы через цикли. Всем спасибо!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.09.2012, 00:06
Привет! Вот еще темы с ответами:

Сравнение методов сортировок массивов. Семестровая работа - C++
Пишу семестровую по методам сортировки массивов. В моем варианте метод прямого выбора и метод Шейкера. Надо сравнить количество...

Тема-обсуждение для "Алгоритмов сортировок" - C++
Сообщения выделены из закреплённой темы: http://www.cyberforum.ru/cpp-beginners/thread27084.html #include &lt;iostream&gt; #include...

Сравнение алгоритмов сортировки массива - C++
Всем доброго времени суток Получил задание в университете, выполнил его. Результатом не очень доволен, хотя явных ошибок не вижу... ...

Алгоритмы сортировки,сравнение алгоритмов - C++
Всем привет у меня такое задание Составить программы благоустройства первых N, N ≤12, элементов массива X. Вид сортировки, а также...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
21.09.2012, 00:06
Ответ Создать тему
Опции темы

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