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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
Billy_boy
Сообщений: n/a
#1

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

15.02.2011, 17:26. Просмотров 1417. Ответов 1
Метки нет (Все метки)

Всем доброго времени суток Получил задание в университете, выполнил его. Результатом не очень доволен, хотя явных ошибок не вижу...
Задача: сравнить алгоритмы сортировки умным пузырьком и "глупым".
Использую функцию timeGetTime для получения времени вычисления.
В теории так назваемый умный пузырек должен сортировать ощутимо быстрее. На практике же отличия в несколько микросекунд, причем разница не сильно меняется с увеличением массива. Иногда по результатам даже на больших массивах глупый пузырек сортирует быстрее Строю граффик в эксэле - линии практически совпадают...
Главный вопрос: В чем может крыться причина столь небольшого отличия скоорости?
Может конечно, это мои заморочки и все работает верно, но что- то мне так не кажется. Помогите кто чем может.
Код:
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
#include "stdafx.h"
#include <windows.h>
#include <mmsystem.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;
#pragma comment(lib,"winmm.lib")
 
#define EXPSIZE 10
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale (LC_ALL,"rus");
    srand (( unsigned ) time( NULL ));
    int const N = 1000;
    int Arr1[N];
    int Arr2[N];
    DWORD aver1 = 0;
    DWORD aver2 = 0;
    DWORD mSecArr1[10];
    DWORD mSecArr2[10];
    bool flag = false;
 
    int l = N; // бредок
 
 
        for(int ind = 0; ind < EXPSIZE; ind ++)
        {
            for (int i = 0; i < l; i++ ) // Заполнение и копирование массивов
            {
                Arr1[i] = rand();
                Arr2[i] = Arr1[i];
            } 
 
            mSecArr1[ind] = timeGetTime();
 
            for (int i = 0; i < l; i++ ) //Сортировка глупым пузырьком
            {
                for (int j= 0; j < l-1; j++ )
                {
                    if (Arr1[j] > Arr1[j+1] )
                    {
                        int tmp = Arr1[j];
                        Arr1[j] = Arr1[j+1];
                        Arr1[j+1] = tmp;
                    }
                }
            }
 
            mSecArr1[ind] = timeGetTime() - mSecArr1[ind];
            //cout << ind + 1 << ") Сортировка " << l << " элементов глупым способом = " << mSecArr1[ind] << endl; 
        
            mSecArr2[ind] = timeGetTime();
 
            do                                  //Сортировака умным пузырьком
            {
                flag = false;
                for( int j = 0; j < l - 1; j++ )
                {
                    if ( Arr2[j] > Arr2[j + 1] )
                    {
                        int tmp = Arr2[j];
                        Arr2[j] = Arr2[j+1];
                        Arr2[j+1] = tmp;
                        flag = true;
                    }
                }
            } while ( flag );
        
            mSecArr2[ind] = timeGetTime() - mSecArr2[ind];
            //cout << ind + 1 << ") Сортировка " << l << " элементов умным способом = " << mSecArr2[ind] << "\n" << endl;
        }
            
 
        for(int ind = 0; ind < EXPSIZE; ind ++)
        {
            aver1 += mSecArr1[ind];
            aver2 += mSecArr2[ind];
            mSecArr1[ind] = 0; 
            mSecArr2[ind] = 0;
        }
 
        aver1 /= EXPSIZE;
        aver2 /= EXPSIZE;   
 
        cout << aver1 <<" - Среднее время глупой сортировки на длине ввода " << l << endl;
        cout << aver2 <<" - Среднее время умной сортировки на длине ввода " << l << endl << endl;
        aver1 = 0;
        aver2 = 0;
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.02.2011, 17:26     Сравнение алгоритмов сортировки массива
Посмотрите здесь:

Сравнение алгоритмов сортировок C++
C++ Сравнение алгоритмов сортировки ... алгоритм Шелла
C++ График зависимость количества перестановок и сравнений от размерности массива для алгоритмов сортировки
C++ Визуализация алгоритмов сортировки
Сравнение алгоритмов сортировок C++
C++ создать программу для сравнения алгоритмов сортировки
Сравнение быстродействия алгоритмов сортировки слияния с сортировкой линейной выборкой C++
Реализация алгоритмов сортировки C++
C++ Сравнить время работы алгоритмов сортировки
C++ Сравнение алгоритмов сортировки Хоара и std::sort
Алгоритмы сортировки,сравнение алгоритмов C++
5 алгоритмов сортировки C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Naatikin
4 / 4 / 0
Регистрация: 01.11.2010
Сообщений: 97
15.02.2011, 18:23     Сравнение алгоритмов сортировки массива #2
я сделал количество проходов для циклов по 100 и у меня была разница на 2порядка

Добавлено через 37 секунд
ну а потом можно поделить на 100
Yandex
Объявления
15.02.2011, 18:23     Сравнение алгоритмов сортировки массива
Ответ Создать тему
Опции темы

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