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

Засечь время выполнения пирамидальной сортировки - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Циклические алгоритмы. http://www.cyberforum.ru/cpp-beginners/thread233928.html
Циклические алгоритмы. 1. Известны оценки по информатике каждого из 20 учеников класса. Сколько учеников имеют по информатике оценку «5»?. 2. Известны сведения о количестве осадков, выпавших за...
C++ поиск в очень маленькой БД Есть вот такая регистрационная форма, мне нужно по введенному имени найти всех зарегистрированных с таким же именем. #include<conio.h> #include<string> #include<iostream> using namespace std;... http://www.cyberforum.ru/cpp-beginners/thread233869.html
Мне надо сделать поиск последнего вхождения подстроки s1 в строку s(с функцией LastPos, не strstr). В этом коде просто вхождение подстроки в строку. C++
#include <stdio.h> int count_of_substrings(string s, string s1){ int start = 0; int count = 0; int pos = 0; for(i < 0; i < 4; i++){ pos = s.find(s1.c_s(),start); if...
C++ Назначение - конкатенация строк s1 и s2, не используя библиотечную функцию - strcat
#include <stdio.h> #include <stdlib.h> char * strcat_my (char *s1, char *s2){ char *p1, *p2; p1 = s1; p2 = s2; while ( *p1 != '\0') p1++;
C++ Строки http://www.cyberforum.ru/cpp-beginners/thread233846.html
Написать программу, которая удаляет из введенной с клавиатуры строки начальные пробелы. #include <iostream> #include <string> int main() { std::string s; getline(std::cin, s); while(s == '...
C++ Даны результаты переписи населения. Покажите список населения которые родились после 1990года. Даны результаты переписи населения. Покажите список населения которые родились после 1990года. Также покажите число такого населения. подробнее

Показать сообщение отдельно
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
25.01.2011, 19:48
Если ты говоришь, что сама сортировка работает правильно (тестировала упорядоченность массива после сортировки?), то, значит, дело в самих замерах. Ну, вот аналогичный код (сравниваем стандратный qsort и пирамидальную сортировку):
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
typedef void (*sortingFunc)(int*, int);
 
#define SIZE 4096 * 16 * 8
#define L_T -100500
#define R_T  100500
 
void downHeap(int a[], int k, int n);
void heapSort(int a[], int size);
void qsortWrapper(int a[], int size);
int cmp(const void* a, const void* b);
void test(sortingFunc func, const char* name);
 
int main()
{
    srand((size_t) time(NULL));
 
    test(qsortWrapper, "Standart qsort");
    test(heapSort, "Heap Sort");
    
    exit(0);
}
 
void downHeap(int a[], int k, int n) 
{
    int new_elem;
    int child;
    new_elem = a[k];
 
    while(k <= n/2) 
    { 
        child = 2*k;
 
        if( child < n && a[child] < a[child+1] ) 
            ++child;
        if( new_elem >= a[child] ) 
            break; 
 
        a[k] = a[child]; 
        k = child;
  }
  a[k] = new_elem;
}
 
void heapSort(int a[], int size) 
{
    int i;
    int temp;
 
    for(i=size/2-1; i >= 0; --i) 
        downHeap(a, i, size-1);
 
 
    for(i=size-1; i > 0; --i) 
    {
        temp=a[i]; a[i]=a[0]; a[0]=temp;
        downHeap(a, 0, i-1); 
    }
}
 
void qsortWrapper(int a[], int size)
{
    qsort(a, size, sizeof(int), cmp);
}
 
int cmp(const void* a, const void* b)
{
    int A = *(const int*) a;
    int B = *(const int*) b;
    if(A < B)
        return -1;
    if(B < A)
        return 1;
    return 0;
}
 
void test(sortingFunc func, const char* name)
{
    int *iarray;
    size_t i;
    clock_t start, finish;
    
    if((iarray = malloc(SIZE * sizeof(int))) == NULL)
        exit(1);
    
    for(i = 0; i < SIZE; ++i)
        iarray[i] = rand() % (R_T - L_T + 1) + L_T;
        
    start = clock();
    func(iarray, SIZE);
    finish = clock();
    printf("Sorted (%s) in %.3f seconds\n", name, ((double) (finish - start))/((double) CLOCKS_PER_SEC));
    
    free(iarray);
}
И что он мне выдал:
Код
nameless@nameless-laptop:~/foo$ make && ./foo
cc -ansi -pedantic -Wall   -c -o main.o main.c
cc -o foo main.o
Sorted (Standart qsort) in 0.430 seconds
Sorted (Heap Sort) in 0.570 seconds
nameless@nameless-laptop:~/foo$
И это при запуске на нетбуке, который отнюдь не блещет производительностью. Может, все же имеет смысл увеличить количество циферок?
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru