I am doing this small project for a class and I have pretty much finished it but for some reason my merged vector is double the size it should be and has leading 0's that shouldn't be there. The main function was written for us, we have to write the partition, quick sort, and multiway_merge functions. First, the program should take in the number of lists, number of integers in each list, and then the numbers that go in each list from the keyboard. Then we quick sort each of the lists using a quick sort and partition function. The pivot in the partition function should be the median of the first, middle, and last elements in the list. Once sorted, we use the multiway_merge function to merge the sorted lists. I have gotten it to sort the lists and merge them but for some reason I am getting a final vector that is double the size it should be and the first half of it are 0's. If you guys could help me figure this out, that would be great!
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int partition(vector<int>& list, int first, int last) {
// The pivot should be the median of the
// first, middle, and last elements.
int pivot;
int index, smallIndex;
int middle = floor(list.size() / 2);
int arr[3] = {first, middle, last};
int size = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + size);
swap(first, arr[1]);
pivot = list[first];
smallIndex = first;
for(index = first + 1; index <= last; index++)
if(list[index] < pivot) {
smallIndex++;
swap(smallIndex, index);
}
swap(first, smallIndex);
return smallIndex;
}
void quicksort(vector<int>& list, int first, int last) {
if(first == last)
return;
else {
int pivotLocation = partition(list, first, last);
quicksort(list, first, pivotLocation - 1);
quicksort(list, pivotLocation + 1, last);
}
}
void multiway_merge(vector<vector<int> >& input_lists,
vector<int>& output_list) {
int size = input_lists.size();
int s = input_lists[0].size();
priority_queue<int, vector<int>, greater<int> > minHeap;
for(int i = 0; i < size; i++) {
for(int j = 0; j < s; j++) {
minHeap.push(input_lists[i][j]);
if(minHeap.size() > size) {
output_list.push_back(minHeap.top());
minHeap.pop();
}
}
}
while(minHeap.size()) {
output_list.push_back(minHeap.top());
minHeap.pop();
}
}
int main(int argc, char** argv) {
int n, m;
cin >> n >> m;
vector<vector<int> > input_lists(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> input_lists[i][j];
}
}
// Quicksort k sublists
for (int i = 0; i < input_lists.size(); ++i)
quicksort(input_lists[i], 0, m-1);
// Merge n input sublists into one sorted list
vector<int> output_list(n * m);
multiway_merge(input_lists, output_list);
for (int i = 0; i < output_list.size(); ++i)
cout << output_list[i] << " ";
cout << endl;
}
