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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Циклические алгоритмы. http://www.cyberforum.ru/cpp-beginners/thread233928.html
Циклические алгоритмы. 1. Известны оценки по информатике каждого из 20 учеников класса. Сколько учеников имеют по информатике оценку «5»?. 2. Известны сведения о количестве осадков, выпавших за каждый день мая. Первого мая осадков не было. Определить, в течение какого количества первых дней месяца непрерывно, начиная с первого мая, осадков не было. 3. Напечатать минимальное число, большее...
C++ поиск в очень маленькой БД Есть вот такая регистрационная форма, мне нужно по введенному имени найти всех зарегистрированных с таким же именем. #include<conio.h> #include<string> #include<iostream> using namespace std; struct registration{ string name; string surname; int age; string address; 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 (pos != -1){ start = pos + s1.size();
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 == ' ') { for(int i = 0; i < s.length() - 1; i++) { s = s;
C++ Даны результаты переписи населения. Покажите список населения которые родились после 1990года. Даны результаты переписи населения. Покажите список населения которые родились после 1990года. Также покажите число такого населения. подробнее

Показать сообщение отдельно
Nameless One
Эксперт С++
5769 / 3418 / 255
Регистрация: 08.02.2010
Сообщений: 7,446
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$
И это при запуске на нетбуке, который отнюдь не блещет производительностью. Может, все же имеет смысл увеличить количество циферок?
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru