Design-And-Analysis-Of-Algorithms/heapsort.cpp at main · httpsVishu/Design-And-Analysis-Of-Algorithms · 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
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>

using namespace std;

void heapify(vector<int>& arr, int n, int i, long long& comparisons, long long& swaps){
    int largest = i;
    int left = 2*i+1;
    int right = 2*i+2;

    if (left < n){
        comparisons++;
        if (arr[left] > arr[largest])
            largest = left;
    }
    if (right < n){
        comparisons++;
        if (arr[right] > arr[largest])
            largest = right;
    }

    if (largest != i){
        swap(arr[i], arr[largest]);
        swaps++;
        heapify(arr, n, largest, comparisons, swaps);
    }
}

void buildMaxHeap(vector<int>& arr, int n, long long& comparisons, long long& swaps){
    for (int i = n/2-1; i>=0; i--){
        heapify(arr, n, i, comparisons, swaps);
    }
}

void heapSort(vector<int>& arr, int n, long long& comparisons, long long& swaps){
    buildMaxHeap(arr, n, comparisons, swaps);
    for (int i = n-1; i>0; i--){
        swap(arr[i], arr[0]);
        swaps++;
        heapify(arr, i, 0, comparisons, swaps);
    }
}

void processArray(vector<int> arr, char type, int arrayNum, ofstream &fout, long long &sumCom, long long &sumSwaps,int& batchCount){
        long long comparisons = 0;
        long long swaps = 0;

        heapSort(arr, arr.size(), comparisons, swaps);  //array sorted

        fout << arrayNum << "," << type << "," << arr.size() << ","
            << comparisons << "," << swaps << endl;

        sumCom += comparisons;
        sumSwaps += swaps;
        batchCount++;

        if (batchCount == 10){
            fout << "AVG,AVG," <<arr.size()<<","
                    <<(double)sumCom/10 << "," << (double)sumSwaps/10 << "\n";

            batchCount = 0;
            sumCom = 0;
            sumSwaps = 0;
        }
}

int main(){
    ifstream fin("arrays.csv");
    ofstream fout("heap_results.csv");

    if (!fin || !fout){
        cout << "file error :/";
        return 0;
    }

    fout << "Array_No,Type,Size,Comparisons,Swaps\n";   //headers add kiye hai

    int arrayNum =  1;
    int batchCount = 0;

    long long sumCom = 0;
    long long sumSwaps = 0;

    while (true){
        vector<int> arr;
        char type; int size;
        int number;
        char comma;

        if (!(fin >> type >> comma >> size >> comma)) break;

        while (fin>>number){
            arr.push_back(number);
            if (fin.peek() == ','){
                fin.ignore();
            } else{
                break;
            }
        }

        char ch;
        while (fin.get(ch) && ch != '\n');

        processArray(arr, type, arrayNum, fout, sumCom, sumSwaps, batchCount);

        arrayNum++;
    }

    fin.close();
    fout.close();
    cout<< "Heap sort completed :)";

    return 0;

}