-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmain.cpp
More file actions
211 lines (182 loc) Β· 5.43 KB
/
main.cpp
File metadata and controls
211 lines (182 loc) Β· 5.43 KB
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <iostream>
#include <algorithm>
#include <sys/time.h>
#include <vector>
#include <cstdlib>
#include <climits>
#include <iomanip>
/**
* @brief Generate the insertion order for the "small" elements
* based on the Jacobsthal sequence logic.
*
* @param n The number of elements to generate order for.
* @return A vector containing indices in the insertion order.
*/
std::vector<int> insertOrder(int n)
{
std::vector<int> jacob;
jacob.push_back(0);
jacob.push_back(1);
int prev = 1;
int next = 3;
while (static_cast<int>(jacob.size()) < n)
{
for (int i = (next >= n ? n - 1 : next); i > prev; --i)
{
jacob.push_back(i);
if (static_cast<int>(jacob.size()) == n)
break;
}
prev = next;
next = next + 2 * prev;
}
return (jacob);
}
/**
* @brief Sort a vector using the Merge-Insertion sort algorithm (Ford-Johnson).
* Elements are divided into pairs, sorted recursively, and inserted
* using a special insertion order (based on Jacobsthal).
*
* @param input The vector to be sorted (in-place).
*/
void MergeInsertionSort(std::vector<int> &input)
{
if (input.size() <= 1)
return ;
std::vector<int> bigs;
std::vector<int> smalls;
// Step 1: Pairing elements into bigs and smalls
for (size_t i = 0; i < input.size() - 1; i += 2)
{
if (input[i] > input[i + 1])
{
bigs.push_back(input[i]);
smalls.push_back(input[i + 1]);
}
else
{
bigs.push_back(input[i + 1]);
smalls.push_back(input[i]);
}
}
// Handle leftover element if the input size is odd
int leftover = (input.size() % 2 != 0) ? input.back() : -1;
// Step 2: Recursively sort the bigs
MergeInsertionSort(bigs);
// Step 3: Insert the smalls into the sorted bigs using a specific insertion order
std::vector<int> sorted = bigs;
if (!smalls.empty())
{
std::vector<int> indeces = insertOrder(smalls.size());
for (size_t i = 0; i < smalls.size(); ++i)
{
int idx = indeces[i];
std::vector<int>::iterator pos = std::lower_bound(sorted.begin(), sorted.end(), smalls[idx]);
sorted.insert(pos, smalls[idx]);
}
}
// Step 4: Insert the leftover element if exists
if (leftover != -1)
{
std::vector<int>::iterator pos = std::lower_bound(sorted.begin(), sorted.end(), leftover);
sorted.insert(pos, leftover);
}
// Update the input with the sorted result
input = sorted;
}
/**
* @brief Print a vector with a given label.
*
* @param vector The vector to print.
* @param str A label to display before the values.
*/
void printContainer(const std::vector<int> &vector, std::string str)
{
std::cout << str << ": ";
for (size_t i = 0; i < vector.size(); i++)
std::cout << vector[i] << " ";
std::cout << std::endl;
}
/**
* @brief Get the current time in microseconds.
*
* @return The current timestamp in microseconds.
*/
long long getTimeMicroseconds()
{
struct timeval time;
gettimeofday(&time, NULL);
return (long long)(time.tv_sec) * 1000000 + time.tv_usec;
}
/**
* @brief Print the elapsed time of the sorting operation.
*
* @param start The starting time (in microseconds).
* @param end The ending time (in microseconds).
* @param size The size of the sorted vector.
*/
void printTiming(long long start, long long end, size_t size)
{
std::cout << std::fixed << std::setprecision(5);
std::cout << "Time to process a range of " << size
<< " elements with std::vector : "
<< static_cast<double>(end - start) << " us" << std::endl;
}
/**
* @brief Parse input arguments from command line, validate and store as integers.
*
* @param ac Argument count.
* @param av Argument vector.
* @return A vector of parsed and validated integers.
*
* @throws std::runtime_error if any input is invalid or duplicated.
*/
std::vector<int> parseInput(int &ac, char **av)
{
std::vector<int> result;
for (int i = 1; i < ac; ++i)
{
char *end;
long num = std::strtol(av[i], &end, 10);
if (*end != '\0' || num < 0 || num > INT_MAX)
throw std::runtime_error("Error: Invalid input -> " + static_cast<std::string>(av[i]));
bool isDuplicate = (std::find(result.begin(), result.end(), num) != result.end());
if (isDuplicate)
throw std::runtime_error("Error: Duplicate number found: " + static_cast<std::string>(av[i]));
result.push_back(static_cast<int>(num));
}
return (result);
}
/**
* @brief Entry point of the program.
*
* @param ac Argument count.
* @param av Argument vector.
* @return int Exit status.
*/
int main(int ac, char **av)
{
if (ac < 2)
{
std::cerr << "Usage: ./PmergeMe <numbers...>" << std::endl;
return (1);
}
try
{
std::vector<int> input;
long long timeStart;
long long timeEnd;
input = parseInput(ac, av);
printContainer(input, "Before");
timeStart = getTimeMicroseconds();
MergeInsertionSort(input);
timeEnd = getTimeMicroseconds();
printContainer(input, "After");
printTiming(timeStart, timeEnd, input.size());
}
catch (const std::exception &e)
{
std::cerr << e.what() << '\n';
}
return (0);
}