timingSortingAlgs/main.cpp at master · jacoblbeck/timingSortingAlgs · GitHub

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
//
//  main.cpp
//  sortingAlgorithms
//
//  Created by Jacob Beck on 2/26/19.
//  Copyright © 2019 Jacob Beck. All rights reserved.
//

#include "quickSort.hpp"
#include "randomizedQuicksort.hpp"
#include "binHeap.hpp"
#include <stdlib.h>
#include <sys/time.h>
#include <iostream>

using namespace std;

int main(){
    //create objects
    quickSort qs;
    randomizedQuickSort rqs;
    BinHeap heap;
    int n = 10000;

    struct timeval tstart, tend, tdiff;
    struct timeval ttotal;

    //fills arrays for sorting
    for( int i = 1; i < n; i++) {
        qs.A[i] = i;
        rqs.A[i] = i;
        heap.A[i] = i;
    }


    timerclear(&ttotal);
    gettimeofday(&tstart,0);
    qs.sort(1, n-1);
    gettimeofday(&tend,0);
    timersub(&tend,&tstart,&tdiff);
    timeradd(&ttotal, &tdiff, &ttotal);
    double avg = (ttotal.tv_sec + ttotal.tv_usec/1000000.0);
    printf("quickSort time = %f\n", avg);

    timerclear(&ttotal);
    gettimeofday(&tstart,0);
    rqs.sort(1,n-1);
    gettimeofday(&tend,0);
    timersub(&tend,&tstart,&tdiff);
    timeradd(&ttotal, &tdiff, &ttotal);
    avg = (ttotal.tv_sec + ttotal.tv_usec/1000000.0);
    printf("randomizedQuickSort time = %f\n", avg);

    timerclear(&ttotal);
    gettimeofday(&tstart,0);
    heap.minHeapSort();
    gettimeofday(&tend,0);
    timersub(&tend,&tstart,&tdiff);
    timeradd(&ttotal, &tdiff, &ttotal);
    avg = (ttotal.tv_sec + ttotal.tv_usec/1000000.0);
    printf("heapSort time = %f\n", avg);

    return 0;
}