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

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

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

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

15.02.2011, 17:26. Просмотров 1483. Ответов 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++
Всем привет у меня такое задание Составить программы благоустройства первых N, N ≤12, элементов массива X. Вид сортировки, а также...

Сравнение алгоритмов сортировки (выбором и пузырьком) - C++
создать программу для сравнения алгоритмов сортировки (Выбором и Пузырьком)т.е. чтоб выдавал время построения массива.Помогите очень...

Сравнение алгоритмов сортировки ... алгоритм Шелла - C++
Вопрос такой, для лабораторной работы нужно сравнить три алгоритма сортировки чисел ... так вот измеряю время работы : double start...

Сравнение алгоритмов сортировки Хоара и std::sort - C++
Собственно в универе было дано задание, написать программу которая принимает на вход из файла в структуру имя - производитель-цена и...

Сравнение быстродействия алгоритмов сортировки слияния с сортировкой линейной выборкой - C++
Ребят,помогите,пишу курсовую,не могу сравнить два метода,метод слияния с методом линейной выборки,никак не пойму как сравнить их...

График зависимость количества перестановок и сравнений от размерности массива для алгоритмов сортировки - C++
имеются массивы с размерностью от 1 до 20 с данными не отсортированными,частично отсортированными ,отсортированными в обратную сторону...

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

Добавлено через 37 секунд
ну а потом можно поделить на 100
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.02.2011, 18:23
Привет! Вот еще темы с ответами:

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

Визуализация алгоритмов сортировки - C++
Нужно создать программу для визуализации 3 алгоритмов сортировки. Подскажите, как и на чем лучше делать?

Реализация алгоритмов сортировки - C++
Массив данных заполнять случайным образом. Рассмотреть массивы данных с элементов типа long и char. Использовать перезагрузку функций для...

Сравнительный анализ алгоритмов сортировки - C++
Помогите пожалуйста реализовать программу для сравнения алгоритмов сортировок. Нужно отдельно программу для внутренних сортировок. И...


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

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

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