I'm trying to run a binary sort that sorts through a list of randomly generated numbers, but for some reason isn't working.
It will usually tell me if the highest or lowest numbers are in the array, but acts like a spaz on the middle ones. I keep fiddling with it and I get crash, or just wrong info Can someone take a look and point me in the right direction?
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
// ------ PROTOTYPES -----------------------------------
void print(int []);
void sort(int []);
void populate(int []);
bool isInArray(int [], int);
// ------ CONSTS ---------------------------------------
const int ArraySize = 100;
// ****** MAIN *****************************************
int main()
{
int array[ArraySize];
unsigned seed = time(0);
srand(seed);
// Assign random numbers between 1 and 100 to each element of the array
populate(array);
print(array);
cout << endl;
sort(array);
print(array);
cout << endl;
// check the array for values 0, 25, 50, 75, 100
for (int i = 0; i <= 100; i += 25)
{
cout << i << " is ";
if (!isInArray(array, i))
{
cout << "not ";
}
cout << "in the array" << endl;
}
}
// ------ FUNCTION Binary Search -----------------------
//
// -----------------------------------------------------
bool isInArray(int array[], int num)
{
int lower = 0;
int higher = ArraySize - 1;
int middle;
while(lower <= higher)
{
middle = (lower + higher)/2;
if(array[lower] == num || array[ArraySize - 1] == num)
{
return true;
}
if(num < array[middle])
{
higher = middle - 1;
}
else if(num > array[middle])
{
lower = middle + 1;
}
return false;
}
}
// ------ FUNCTION POPULATE ----------------------------
// Generate 100 random numbers between 0 and 100
// -----------------------------------------------------
void populate(int array[])
{
for(int i = 0; i < ArraySize; i++)
{
array[i] = rand() % 100;
}
return;
}
// ------ FUNCTION SORT --------------------------------
// Sort numbers from lowest to highest
// -----------------------------------------------------
void sort(int array[])
{
int temp = array[0];
bool swapped;
do
{
swapped = false;
for(int i = 0; i < ArraySize -1; i++)
{
if(array[i] < array[i + 1])
{
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = true;
}
}
}while(swapped);
return;
}
// ------ FUNCTION PRINT -------------------------------
//
// -----------------------------------------------------
void print(int array[])
{
int counter = 0;
for(int i = 0; i < ArraySize; i++)
{
cout << array[i] << " ";
counter ++;
if(counter > 1 && counter % 25 == 0)
{
cout << endl;
counter = 0;
}
}
return;
}
OUTPUT:
69 84 13 30 57 98 2 56 97 28 31 50 21 84 45 93 55 60 2 47 14 60 69 46 45
60 90 3 94 89 20 55 65 67 33 8 13 21 78 39 40 24 71 45 18 25 7 84 32 38
64 27 82 75 82 84 63 81 81 41 7 34 28 25 18 14 79 37 75 10 13 19 59 47 78
1 39 93 7 72 91 49 72 6 44 71 64 27 92 32 19 77 33 23 84 6 8 31 22 85
98 97 94 93 93 92 91 90 89 85 84 84 84 84 84 82 82 81 81 79 78 78 77 75 75
72 72 71 71 69 69 67 65 64 64 63 60 60 60 59 57 56 55 55 50 49 47 47 46 45
45 45 44 41 40 39 39 38 37 34 33 33 32 32 31 31 30 28 28 27 27 25 25 24 23
22 21 21 20 19 19 18 18 14 14 13 13 13 10 8 8 7 7 7 6 6 3 2 2 1
0 is not in the array
25 is not in the array
50 is not in the array
75 is not in the array
100 is not in the array
Process returned 0 (0x0) execution time : 0.546 s
Press any key to continue.
