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

Сортировки (пузырек, быстрая, шелл, слияние) - C++

Восстановить пароль Регистрация
 
rawk
0 / 0 / 0
Регистрация: 21.01.2014
Сообщений: 7
21.01.2014, 12:51     Сортировки (пузырек, быстрая, шелл, слияние) #1
Доброго дня. Имеется программа сортировок пузырьком, быстрая, шеллом, слиянием.
Нужно расчитать время. Размеры массива 10, 100, 1000, 10000.
10, 100 - нет никаких проблем.
1000 (пришлось убрать слияние, тк. не работает)
10000 не получается посчитать вообще.
Вот сама программа.
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <iostream>
#include <locale.h> 
#include <conio.h>
#include <stdio.h>      /* printf */
#include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */
#include <math.h>       /* sqrt */
 
using namespace std; // Стандартные имена
 
//==================Cортировка пузырьком==================
void bubbleSort(int* arr, int size)   // сортировка пузырьком
{ 
    int temp = 0;   // временная переменная, хранящая элемент массива
    bool exit = false;   // болевая переменная для выхода из цикла, если массив отсортирован
    while (!exit) 
    {
        exit = true; 
        for (int k = 0; k < (size - 1); k++) 
 
            if (arr[k] > arr[k + 1])
            {
                temp = arr[k]; 
                arr[k] = arr[k + 1];
                arr[k + 1] = temp;
                exit = false; 
            } 
    } 
}
 
//==================== Сортировка вставками ==================================
void insertSort(int *arr, int size){
  for (int i = 0; i < size; i++)
    {
        int temp = arr[i];// запомним i-ый элемент
        int j =i-1;//будем идти начиная с i-1 элемента 
        while(j >= 0 && arr[j] > temp)
        // пока не достигли начала массива 
        // или не нашли элемент больше i-1-го
        // который храниться в переменной temp
        {
            arr[j + 1] = arr[j];
            //проталкиваем элемент вверх
            j--;
        }
        arr[j + 1] = temp;
        // возвращаем i-1 элемент 
    }   
}
 
void swap(int *x, int *y)   /// описываем функцию swap
{
    int z;
    z=*x;
    *x=*y;
    *y=z;
}
 
//==================Cортировка быстрая==================
void quickSort(int* arr, int first, int last)
{
    int i = first, j = last, x = arr[(first + last) / 2];
 
    do {
    while (arr[i] < x) i++;
    while (arr[j] > x) j--;
 
    if(i <= j) {
    if (i < j) swap(arr + i, arr + j);
    i++;
    j--;
    }
    } while (i <= j);
 
    if (i < last)
    quickSort(arr, i, last); 
    if (first < j) quickSort(arr, first,j); 
}
 
//==================Cортировка Шелла==================
void shellSort(int *arr, int size)
{
    int i,j,p,m,k;
    int min;
    for(m=size/2;m;m=m/2)//постоянно уменьшаем шаг от count/2 до 1(разбиваем массив на группы)
    {
    for(k=0;k<m;k++)//двигаемся внутри группы
        for(i=m+k;i<size;i+=m)//сортировка вставками с учётом шага
        {
            min=arr[i];
            for(j=k;j<i;j+=m)
            if(arr[j]>min) break;
            for(p=i-m;p>=j;p-=m)
            arr[p+m]=arr[p];
            arr[j]=min;
        }
    }
}
 
int main()
{
    srand(time(0));
    setlocale(LC_ALL, "Russian");
    // Считываем размер массива,
    // который необходимо отсортировать
    int size;
    cout << "Введите размер массива:";
    cin >> size;
 
    // Динамически выделяем память под
    // хранение массива размера size
    int *arr = new int[size];
    int *sorted = new int[size];
    // Считываем массив
    //cout << "Введите элементы массива:\n";
    for (int i = 0; i < size; i++)
    {
        //cin >> arr[i];
        arr[i] = rand() % 200;  
    }
 
    int sort_iter_count = 1000; //количество проходов сортировки.
    //если делать только один проход, то время работы оочень маленькое и просто можно его не "уловить"
    clock_t t;
    
    t = clock();
    int s = sizeof(int)*size;
    for (int i=0; i < sort_iter_count; i++) {
        memcpy(sorted, arr, sizeof(int)*size);
        shellSort(sorted, size);
    }
    t = clock() - t;
    cout << "Время сортировки Шелла:" << t << "(тика)" << ((float)t) / CLOCKS_PER_SEC << "(секунд)\nРезультат:";
    for (int i = 0; i < size; i++) 
        cout << sorted[i] << ' ';
    cout << endl << endl;
/*-----------------------------------------*/
    t = clock();
    for (int i=0; i < sort_iter_count; i++) {
        memcpy(sorted, arr, sizeof(int)*size);
        quickSort(sorted, 0, size-1);
    }
    t = clock() - t;
    cout << "\nВремя быстрой сортировки:" << t << "(тика)" << ((float)t) / CLOCKS_PER_SEC << "(секунд)\nРезультат:";
    for (int i = 0; i < size; i++) 
        cout << sorted[i] << ' ';
    cout << endl << endl;
/*-----------------------------------------*/
    t = clock();
    for (int i=0; i < sort_iter_count; i++) {
        memcpy(sorted, arr, sizeof(int)*size);
        insertSort(sorted, size);
    }
    t = clock() - t;
    cout << "\nВремя сортировки вставками:" << t << "(тика)" << ((float)t) / CLOCKS_PER_SEC << "(секунд)\nРезультат:";
    for (int i = 0; i < size; i++) 
        cout << sorted[i] << ' ';
    cout << endl << endl;
/*-----------------------------------------*/
    t = clock();
    for (int i=0; i < sort_iter_count; i++) {
        memcpy(sorted, arr, sizeof(int)*size);
        bubbleSort(sorted, size);
    }
    t = clock() - t;
    cout << "\nВремя пузырьковой сортировки:" << t << "(тика)" << ((float)t) / CLOCKS_PER_SEC << "(секунд)\nРезультат:";
    for (int i = 0; i < size; i++) 
        cout << sorted[i] << ' ';
    cout << endl << endl;
/*-----------------------------------------*/
    
    getch();
 
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
21.01.2014, 13:22     Сортировки (пузырек, быстрая, шелл, слияние) #2
Цитата Сообщение от rawk Посмотреть сообщение
10000 не получается посчитать вообще.
Может все получается, просто долго?
rawk
0 / 0 / 0
Регистрация: 21.01.2014
Сообщений: 7
21.01.2014, 13:24  [ТС]     Сортировки (пузырек, быстрая, шелл, слияние) #3
Цитата Сообщение от _script_ Посмотреть сообщение
Может все получается, просто долго?
Ждал около 3х, 4х часов..
Enotniy
 Аватар для Enotniy
96 / 95 / 14
Регистрация: 15.01.2014
Сообщений: 283
21.01.2014, 13:26     Сортировки (пузырек, быстрая, шелл, слияние) #4
Цитата Сообщение от rawk Посмотреть сообщение
int sort_iter_count = 1000; //количество проходов сортировки.
вот от этого для начала избавитесь
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
21.01.2014, 13:27     Сортировки (пузырек, быстрая, шелл, слияние) #5
Цитата Сообщение от rawk Посмотреть сообщение
int sort_iter_count = 1000; //количество проходов сортировки.
* * //если делать только один проход, то время работы оочень маленькое и просто можно его не "уловить"
При большом размере массива один проход занимает много времени, а у вас тут тысяча проходов
rawk
0 / 0 / 0
Регистрация: 21.01.2014
Сообщений: 7
21.01.2014, 13:35  [ТС]     Сортировки (пузырек, быстрая, шелл, слияние) #6
Поставил 1, но 10000ый все равно не считает...

Добавлено через 3 минуты

Сортировки (пузырек, быстрая, шелл, слияние)

Вот такая песня (при 1, секунд за 20 такая картина)
При 1000 (минут 10)

Добавлено через 31 секунду
на 199 заканчивается, и не идет дальше.
Enotniy
 Аватар для Enotniy
96 / 95 / 14
Регистрация: 15.01.2014
Сообщений: 283
21.01.2014, 13:38     Сортировки (пузырек, быстрая, шелл, слияние) #7
rawk, не выводите на экран результаты - только мешают

Добавлено через 1 минуту
Цитата Сообщение от rawk Посмотреть сообщение
на 199 заканчивается, и не идет дальше.
это значит отсортировалось
C++
1
   arr[i] = rand() % 200;
вот работает
Сортировки (пузырек, быстрая, шелл, слияние)
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
21.01.2014, 13:40     Сортировки (пузырек, быстрая, шелл, слияние) #8
Цитата Сообщение от rawk Посмотреть сообщение
на 199 заканчивается, и не идет дальше.
У тебя в конце getch();
надо ENTER нажать и программа завершиться.
rawk
0 / 0 / 0
Регистрация: 21.01.2014
Сообщений: 7
21.01.2014, 13:41  [ТС]     Сортировки (пузырек, быстрая, шелл, слияние) #9
Цитата Сообщение от _script_ Посмотреть сообщение
У тебя в конце getch();
надо ENTER нажать и программа завершиться.
Это понятно. Как узнать результаты? Вот в чем моя проблема. Оказывается, что прога считает все как надо. Но не могу получить результаты при 10000ой сортировке.
Enotniy
 Аватар для Enotniy
96 / 95 / 14
Регистрация: 15.01.2014
Сообщений: 283
21.01.2014, 13:42     Сортировки (пузырек, быстрая, шелл, слияние) #10
rawk, я вам посоветую перемешивать массив после каждой сортировки, потому как некоторые сортировки показывают результат лучше на отсортированных массивах
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,337
Завершенные тесты: 1
21.01.2014, 13:43     Сортировки (пузырек, быстрая, шелл, слияние) #11
Цитата Сообщение от rawk Посмотреть сообщение
Как узнать результаты? Вот в чем моя проблема. Оказывается, что прога считает все как надо. Но не могу получить результаты при 10000ой сортировке.
Выводите в файл.

И кстати, выкладывайте изображения прямо на форум (кнопка Расширенный режим -> Управление вложениями ).
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
21.01.2014, 13:47     Сортировки (пузырек, быстрая, шелл, слияние) #12
Цитата Сообщение от rawk Посмотреть сообщение
Но не могу получить результаты при 10000ой сортировке.
По чему не можешь?
результат выводит перед выводом массива)
Убери вывод массивов и будет выводить только время)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.01.2014, 18:22     Сортировки (пузырек, быстрая, шелл, слияние)
Еще ссылки по теме:

C++ Внешние сортировки. Сортировка слиянием. Простое слияние
Внешние сортировки. Сортировка слиянием. Естественное слияние C++

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

Или воспользуйтесь поиском по форуму:
rawk
0 / 0 / 0
Регистрация: 21.01.2014
Сообщений: 7
21.01.2014, 18:22  [ТС]     Сортировки (пузырек, быстрая, шелл, слияние) #13
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Выводите в файл.

И кстати, выкладывайте изображения прямо на форум (кнопка Расширенный режим -> Управление вложениями ).
Простите, не знал. Учту на будущее.
Ребят, всем спасибо за помощь.

Добавлено через 4 часа 34 минуты
Теперь. Препод требует от меня следующее.
Я абсолютно не понимаю, о чем речь.
Можете подсказать, господа знатоки?
(он велел сделать теор. анализ, я спросил как его делать, в ответ получил (текст ниже))

Теоретический анализ - это формулы вычисления времени для каждого алгоритма. Мы их на лекциях записывали. Там, правда, речь шла о порядке количества действий (например, О(n^2) для пузырька.
У Вас же надо будет найти коэффициент, который стоит в этой формуле для получения точного значения времени. Для этого надо построить экспериментальные точки, которые у Вас получились, а потом - семейство теоретических кривых времени выполнения алгоритма (например, C*n^2, для разных С - это для пузырька), и подобрать наиболее близкую к Вашим данным, полученным на практике.
Далее надо написать коэффициент С и подумать, от чего он может зависеть, то есть, объяснить его значение. Если же эксперимент и теория не совпадают, то надо объяснить, в чем причина расхождения.
Yandex
Объявления
21.01.2014, 18:22     Сортировки (пузырек, быстрая, шелл, слияние)
Ответ Создать тему
Опции темы

Текущее время: 19:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru