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
|
/**********
*
*
*
***********/
#include <iostream>
#include <cmath>
#include <ctime>
#include <iterator>
using namespace std;
int selectionSort(int [], int);
int binarySearch(int[], int, int);
int main()
{
srand (time_t(NULL));
int narray[100];
for (int i=0; i<100; i++)
{
narray[i]=rand()%999;
}
int i, moves;
moves = selectionSort(narray, 100);
cout << "The sorted list, in ascending order is: \n";
for (i=0; i < 100; i++)
cout << " " << narray[i];
cout << endl << moves << " moves were made to sort this list. \n";
int item, location,iterations;
cout<<"Enter the number you wish to find:";
cin>> item;
location=binarySearch(narray, 100, item);
iterations=selectionSort(narray, 100);
if (location > -1)
cout << "The number was found at index location " << location << " after " << iterations << " iterations."<<endl;
else
cout <<"the item was not found in the array\n";
return 0;
}
int selectionSort(int num[], int numel)
{
int i, j, min, minidx, temp, moves=0;
for (i=0; i<(numel-1); i++)
{
min = num[i];
minidx=i;
for(j = i + 1; j < numel; j++)
{
if (num[j] < min)
{
min = num[j];
minidx = j;
}
}
if (min < num[i])
{
temp = num[i];
num[i] = min;
num[minidx] = temp;
moves++;
}
}
return moves;
}
int binarySearch(int list[], int size, int key){
int left, right, midpoint;
left=0;
right=size -1;
while (left <= right) {
midpoint = (int) ((left + right) / 2);
if (key == list[midpoint]) {
return midpoint;
}
else if (key > list[midpoint])
left = midpoint + 1;
else
right = midpoint - 1;
}
return -1;
}
|