TLDR: I have an assignment to find the median of a random large sequence, my code for this is at the bottom and works about 50% of the time, and I've completely run out of ideas. Can someone help?
So I'm taking a class and learning C++ coding, with just a little bit of prior experience. I have an assignment to write a function called select to find the median of a random large sequence using a specific formula, shown below in psuedocode:
select(k, a, b)
Pick a pivot p in the subsequence between a and b.
Partition the subsequence elements into three subsequences:
the elements < p, = p, > p
Let n1, n2, n3 be the sizes of each of these subsequences.
if k < n1
return select(k, 0, n1).
else if (k > n1 + n2)
return select(k, n1 + n2, n).
else
return p.
When running my code(shown at the bottom), there are a few warnings, but execution continues. First it creates two identical arrays of size 100, filled with random integers from 0 to 100. One of the arrays, the one called values2, is then sorted and the middle element is output to the console, which is the median for both of the sequences to be compared to my function. After the real median is determined, I run my function called select() to hopefully find the median of the same sequence. The result of this is then printed out to the console, and the two values match approximately 50% of the time. I was given a piece of advice by my instructor that I should try to only call partition() once for each call to select(). My brain is completely fried and I've been attempting to fix this for a week now to no avail, can somebody help?
#include <iostream>
#include <ctime>
#include <algorithm>
#include <vector>
using namespace std;
void swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
int partition(int a[], int lb, int ub)
{
int pivot = a[(lb + ub) / 2];
int i = lb;
int j = lb;
int n = ub - 1;
while (j <= n) {
if (a[j] < pivot) {
swap(a[i], a[j]);
j++;
i++;
}
else if (a[j] > pivot) {
swap(a[j], a[n]);
n--;
}
else {
j++;
}
}
ub = n + 1;
lb = n;
while (lb > 0 && a[lb] == pivot) {
lb--;
}
lb++;
return lb;
}
int select(int arr[], int k, int a, int b) {
if (a >= b) {
return arr[k];
}
int n1 = partition(arr, a, b);
int n2 = partition(arr, n1 - 1, b);
n2 = n2 - n1;
if (k < n1) {
return select(arr, k, a, n1);
}
else if (k > (n1 + n2)) {
return select(arr, k, (n1 + n2), sizeof(arr) / sizeof(arr[0]));
}
else {
return arr[k];
}
}
int main()
{
srand(time(0));
const int SIZE = 100;
int values[SIZE];
int values2[SIZE];
for (int x = 0; x < SIZE; x++)
{
values[x] = rand() % 100;
values2[x] = values[x];
}
sort(values2, values2 + SIZE);
int median2 = values2[SIZE / 2];
cout << median2;
//cout << total / SIZE << endl;
int median = select(values, SIZE / 2, 0, SIZE);
cout << "\n" << median << endl;
return 0;
}
