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

устранить ошибки - C++

Восстановить пароль Регистрация
 
Belek
 Аватар для Belek
6 / 6 / 0
Регистрация: 15.12.2010
Сообщений: 200
08.01.2011, 04:53     устранить ошибки #1
Привет! Я уже обращался с подобной просьбой, но остался без ответа. помогите пожалуйста. срочно надо!
задача такова что нужно написать программу которая сортирует массивы из 1000, 5000 и 10000 элементов двумя видами сортировок и ввыводит время для каждой сортировки каждого массива.
вот код, но тут у меня выходит что сортировка пузырька сортирует массив из 1000 элементов быстрее чем сортировка втсавкой! пожалуйста помогите!

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
#include <iostream.h>
#include <time.h>
#include <fstream.h>
#include <stdlib.h>
 
void BUBBLE(int array[], int size)
{
             for(int i=0;i<size;i++)
            for(int j=0;j<(size-1);j++)
                       if (array[j]>array[j+1])
                       {
                             int b=array[j];
                         array[j]=array[j+1];
                             array[j+1]=b;
                       }
}
 
 
void INSERTION(int array[], int size)
{
        for(int i=1;i<size;i++)
           {
                int v=array[i];
                for(int j=i-1;(j>=0 && array[j]<v); j--)
                         {
                        v=array[j];
                        array[j+1]=array[j];
                        array[j+1]=v;
                         }
           }
}
 
void full(int array[],int size)
       {
             srand(time(0));
             for(int i=0;i<size;i++)
                      array[i] = 1+rand()%1000;
       }
 
main(){
 
 
 
int array_1[1000];
full(array_1,(sizeof(array_1)/4));
 
int array_2[5000];
full(array_2,(sizeof(array_2)/4));
 
int array_3[10000];
full(array_3,(sizeof(array_3)/4));
 
double xtime[1][2];
clock_t mytime=clock();
 
 
INSERTION(array_1,(sizeof(array_1)/4));
xtime[1][0]=(double)(clock()-mytime)/1000;
 
INSERTION(array_2,(sizeof(array_2)/4));
xtime[1][1]=(double)(clock()-mytime)/1000;
 
INSERTION(array_3,(sizeof(array_3)/4));
xtime[1][2]=(double)(clock()-mytime)/1000;
 
 
 
BUBBLE(array_1,(sizeof(array_1)/4));
xtime[0][0]=(double)(clock()-mytime)/1000;
 
BUBBLE(array_2,(sizeof(array_2)/4));
xtime[0][1]=(double)(clock()-mytime)/1000;
 
BUBBLE(array_3,(sizeof(array_3)/4));
xtime[0][2]=(double)(clock()-mytime)/1000;
 
 
cout<<"bubble: "<<endl;
cout<<(sizeof(array_1)/4)<<" : "<<xtime[0][0]<<endl;
cout<<(sizeof(array_2)/4)<<" : "<<xtime[0][1]<<endl;
cout<<(sizeof(array_3)/4)<<" : "<<xtime[0][2]<<endl<<endl;
 
 
cout<<"insertion: "<<endl;
cout<<(sizeof(array_1)/4)<<" : "<<xtime[1][0]<<endl;
cout<<(sizeof(array_2)/4)<<" : "<<xtime[1][1]<<endl;
cout<<(sizeof(array_3)/4)<<" : "<<xtime[1][2]<<endl<<endl;
 
 
return 0;}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
08.01.2011, 13:30     устранить ошибки #2
Я бы немного оптимизировал бы сортировку пузырьком
C++
1
2
3
4
5
6
7
8
9
10
11
12
void BUBBLE(int array[], int size)
{
    int i, j, tmp;
    for(i = 0; i < size; ++i)
        for(j = 0; j < size - i - 1; ++j)
            if (array[j] > array[j + 1])
            {
                tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
}
Цитата Сообщение от Belek Посмотреть сообщение
но тут у меня выходит что сортировка пузырька сортирует массив из 1000 элементов быстрее чем сортировка втсавкой
На самом деле, пузырьковая сортировка действительно эффективнее более сложных алгоритмов сортировки. Так что это вполне нормальная ситуация
Belek
 Аватар для Belek
6 / 6 / 0
Регистрация: 15.12.2010
Сообщений: 200
08.01.2011, 13:57  [ТС]     устранить ошибки #3
яссно... всегда думал что пузырьковая сортировка самая медленная и не эффективная... да и в книжках так сказанно...
как вы посоветовали я оптимизировал, но никакой разницы не заметил...просто поменяли место объявления переменных int i, j и b... по моему это никак не сказывается на работоспособносте программы. или я ошибаюсь?
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
08.01.2011, 14:02     устранить ошибки #4
Belek, а вы не заметили изменений во втором for? Эта оптимизация изменяет сложность алгоритма с http://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{2} на http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{{n}^{2}}{2}

И кстати, на очень больших объемах данных создание переменных в цикле тоже увеличивает время выполнения
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
08.01.2011, 14:05     устранить ошибки #5
Belek, ну конечно, не скажется. У вас на каждом проходе внешнего цикла внутренний цикл пробегает массив полностью. В оптимизированном вариант на каждом проходе внешнего цикла внутренний пробегает только ещё не отсортированную часть массива, которая с каждой итерацией внешнего цикла уменьшается на 1.

Добавлено через 32 секунды

Не по теме:

M128K145, торможу, как всегда)))

Belek
 Аватар для Belek
6 / 6 / 0
Регистрация: 15.12.2010
Сообщений: 200
08.01.2011, 14:10  [ТС]     устранить ошибки #6
упс, да. for я проморгал. извените. спасибо!
Yandex
Объявления
08.01.2011, 14:10     устранить ошибки
Ответ Создать тему
Опции темы

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