-
Notifications
You must be signed in to change notification settings - Fork 0
/
assignment1.hpp
97 lines (82 loc) · 2.92 KB
/
assignment1.hpp
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
//
// assignment1.cpp
// Algorithms: Design and Analysis, Part 1
//
// Programming Assignment 1
//
// Created by Nenad Mancevic on 2/2/15.
// Copyright (c) 2015 Nenad Mancevic. All rights reserved.
//
// Problem:
//
/***********************
Download the text file here (http://bit.ly/1z79yXK)
This file contains all of the 100,000 integers between 1 and 100,000
(inclusive) in some order, with no integer repeated.
Your task is to compute the number of inversions in the file given,
where the ith row of the file indicates the ith entry of an array.
Because of the large size of this array, you should implement the
fast divide-and-conquer algorithm covered in the video lectures.
************************/
#include <iostream>
#include <vector>
namespace assignment1
{
// counting inversions
long long CountSplitInv(std::vector<int> &input, const std::vector<int>& left, const std::vector<int>& right)
{
std::vector<int> result;
long long inversions = 0;
size_t i = 0, j = 0;
for (size_t k = 0; k < (left.size() + right.size()); k++)
{
if ( (i < left.size()) && (j < right.size()) && (left[i] < right[j]))
{
result.push_back(left[i]);
i++;
}
else if ( (j < right.size()) && (i <left.size()) && (right[j] <= left[i]))
{
result.push_back(right[j]);
j++;
// inversion found (it's a split inversion)!
inversions += left.size() - i;
// if you want to print the inversions, uncomment this code
//for (int o = i; o < left.size(); o++)
// cout << right[(j - 1)] << ", " << left[o] << endl;
}
else if (i < left.size())
{
result.push_back(left[i]);
i++;
}
else if (j < right.size())
{
result.push_back(right[j]);
j++;
}
}
input = result;
return inversions;
}
// entry point to the algorithm
long long Count(std::vector<int> &input)
{
if (input.size() == 1)
return 0;
else
{
// prepare two subarrays
auto mid = input.begin() + (input.size()/2);
std::vector<int> left(input.begin(), mid);
std::vector<int> right(mid, input.end());
// find inversions in each half of the array
long long x = Count(left);
long long y = Count(right);
// finally if there are split inversions find them two
long long z = CountSplitInv(input, left, right);
// the result is the sum of the inversions in each step
return x + y + z;
}
}
} // assignment1