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

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

21.01.2014, 12:51. Показов 1918. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.01.2014, 12:51
Ответы с готовыми решениями:

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

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

Подсчет времени сортировки (пузырек)
Прошу исправить проблему с вызовом подпрограммы + объяснение. Заранее благодарен. import...

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

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

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

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


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

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

Добавлено через 1 минуту
Цитата Сообщение от rawk Посмотреть сообщение
на 199 заканчиваетс­я, и не идет дальше.
это значит отсортировал­ось
C++
1
   arr[i] = rand() % 200;
вот работает
Сортировки (пузырек, быстрая, шелл, слияние)
1
176 / 144 / 70
Регистрация: 01.05.2012
Сообщений: 414
21.01.2014, 13:40 8
Цитата Сообщение от rawk Посмотреть сообщение
на 199 заканчиваетс­я, и не идет дальше.
У тебя в конце getch();
надо ENTER нажать и программа завершиться.
0
0 / 0 / 0
Регистрация: 21.01.2014
Сообщений: 7
21.01.2014, 13:41  [ТС] 9
Цитата Сообщение от _script_ Посмотреть сообщение
У тебя в конце getch();
надо ENTER нажать и программа завершиться.
Это понятно. Как узнать результаты? Вот в чем моя проблема. Оказывается, что прога считает все как надо. Но не могу получить результаты при 10000ой сортировке.
0
101 / 102 / 31
Регистрация: 15.01.2014
Сообщений: 283
21.01.2014, 13:42 10
rawk, я вам посоветую перемешивать массив после каждой сортировки, потому как некоторые сортировки показывают результат лучше на отсортирован­ных массивах
1
Почетный модератор
Эксперт С++
5848 / 2859 / 392
Регистрация: 01.11.2011
Сообщений: 6,905
21.01.2014, 13:43 11
Цитата Сообщение от rawk Посмотреть сообщение
Как узнать результаты? Вот в чем моя проблема. Оказывается, что прога считает все как надо. Но не могу получить результаты при 10000ой сортировке.
Выводите в файл.

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

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

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

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

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

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

Сортировки с рекурсией: быстрая сортировка
Написать программу Сортировки с рекурсией: Быстрая сортировка массива.

Сортировки Шейкером. Быстрая сортировка
Сделать программу по этой блок схеме


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru