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

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

Войти
Регистрация
Восстановить пароль
 
rawk
0 / 0 / 0
Регистрация: 21.01.2014
Сообщений: 7
#1

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

21.01.2014, 12:51. Просмотров 872. Ответов 12
Метки нет (Все метки)

Доброго дня. Имеется программа сортировок пузырьком, быстрая, шеллом, слиянием.
Нужно расчитать время. Размеры массива 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.01.2014, 12:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировки (пузырек, быстрая, шелл, слияние) (C++):

Демонстрационная программа сортировки методом «пузырек» - C++
Демонстрационная программа сортировки методом «пузырек» Размер массива не превышает 40 и задается с клавиатуры. Заполнение массива с...

Исследование сортировки метода "пузырек" для большого массива - C++
Нужно реализовать сортировку большого массива методом &quot;пузырек&quot; (для 100, 1.000 и 10.000 элементов). Должен присутствовать ввод...

Н-ленточное слияние с метод сортировки - C++
Осуществить программную реализацию сортировки информации заданного вида сбаланси-рованным N-ленточным слиянием (в оперативной памяти),...

Н-ленточное слияние с метод сортировки - C++
Осуществить программную реализацию сортировки информации заданного вида сбаланси-рованным N-ленточным слиянием (в оперативной памяти),...

Задача на Метод сортировки (Слияние) - C++
Здравствуйте! Прошу пожалуйста помочь сделать зачетную работу на С++. Задание: Ввести массив А. В массив В перенести все элементы...

Внешние сортировки. Сортировка слиянием. Простое слияние - C++
Пом-гите решить, заранее благодарен.)) Билет 8 1 .Внешние сортировки. Сортировка слиянием. Простое слияние. 2 Решить задачу: ...

12
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
21.01.2014, 13:22 #2
Цитата Сообщение от rawk Посмотреть сообщение
10000 не получается посчитать вообще.
Может все получается, просто долго?
0
rawk
0 / 0 / 0
Регистрация: 21.01.2014
Сообщений: 7
21.01.2014, 13:24  [ТС] #3
Цитата Сообщение от _script_ Посмотреть сообщение
Может все получается, просто долго?
Ждал около 3х, 4х часов..
0
Enotniy
96 / 95 / 14
Регистрация: 15.01.2014
Сообщений: 283
21.01.2014, 13:26 #4
Цитата Сообщение от rawk Посмотреть сообщение
int sort_iter_count = 1000; //количество проходов сортировки.
вот от этого для начала избавитесь
0
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
21.01.2014, 13:27 #5
Цитата Сообщение от rawk Посмотреть сообщение
int sort_iter_count = 1000; //количество проходов сортировки.
* * //если делать только один проход, то время работы оочень маленькое и просто можно его не "уловить"
При большом размере массива один проход занимает много времени, а у вас тут тысяча проходов
1
rawk
0 / 0 / 0
Регистрация: 21.01.2014
Сообщений: 7
21.01.2014, 13:35  [ТС] #6
Поставил 1, но 10000ый все равно не считает...

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

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

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

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

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

И кстати, выкладывайте изображения прямо на форум (кнопка Расширенный режим -> Управление вложениями ).
1
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
21.01.2014, 13:47 #12
Цитата Сообщение от rawk Посмотреть сообщение
Но не могу получить результаты при 10000ой сортировке.
По чему не можешь?
результат выводит перед выводом массива)
Убери вывод массивов и будет выводить только время)
1
rawk
0 / 0 / 0
Регистрация: 21.01.2014
Сообщений: 7
21.01.2014, 18:22  [ТС] #13
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Выводите в файл.

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

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

Теоретический анализ - это формулы вычисления времени для каждого алгоритма. Мы их на лекциях записывали. Там, правда, речь шла о порядке количества действий (например, О(n^2) для пузырька.
У Вас же надо будет найти коэффициент, который стоит в этой формуле для получения точного значения времени. Для этого надо построить экспериментальные точки, которые у Вас получились, а потом - семейство теоретических кривых времени выполнения алгоритма (например, C*n^2, для разных С - это для пузырька), и подобрать наиболее близкую к Вашим данным, полученным на практике.
Далее надо написать коэффициент С и подумать, от чего он может зависеть, то есть, объяснить его значение. Если же эксперимент и теория не совпадают, то надо объяснить, в чем причина расхождения.
0
21.01.2014, 18:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.01.2014, 18:22
Привет! Вот еще темы с ответами:

Внешние сортировки. Сортировка слиянием. Естественное слияние - C++
Пом-гите решить, заранее благодарен.)) Билет 9 1 .Внешние сортировки. Сортировка слиянием. Естественное слияние. 2 Решить...

Отсортировать каждый из 4 массивов 4 способами сортировки (пузырьковая, вставками, пирамидальная, быстрая ) - C++
Собственно задание на скрине #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &quot;math.h&quot; using namespace std; class...

Пузырек - C++
Задать массив А.Состоящий из 8 элементов отсортировать с помощью пузырьковой сортировки.

Шелл.сортировка - C++
Упорядочить по ключу массив записей методом Шелла. Ключом в записи является название фильма на видеокасете, а информационное...


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

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

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