|
The bigger problem is with the Binary Search. The program crashes when it's
excuted. and Visual Studio 2005 indicates stack over flow and shows a break
at that function.
Sequential search is working, but I am trying to have it display the number
of comparisons it took to find the number. It keeps displaying "2."
Thank you folks kindly,
T
#include <iostream>
#include <fstream>
#include<iomanip>
#include<cstdlib>
using namespace std;
ifstream inFile;
ofstream outFile;
void SequentialSearch(int isorted[],int size, int target, int &scompares,
bool &found);
void insertionSort(int isort[], int isorted[],int size);
void BinarySearch(int isorted[],int &compares, int first, int last, bool
&found, int target);
int main()
{
const int arraySize = 15;
int unSort[arraySize];
int sorted[arraySize];
int count=0;
int targets[6];
int compareB;
int compareS;
bool findS;
bool findB;
int firstN = 0;
int lastN = arraySize-1;
inFile.open("input3.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause");
EXIT_FAILURE; //stop program on failure
}
outFile.open("output.txt"); //opening input file
if (!outFile)
{
cerr << "Error Opening File" << endl;
system("pause");
EXIT_FAILURE; //stop program on failure
}
for (int i =0;i < arraySize;i++) //Read in the file with the unsorted
numbers
{
inFile >unSort[i];
}
for (int j=0;j< 6;j++) // get the search keys
{
inFile >targets[j];
}
insertionSort(unSort, sorted, arraySize); //call the insertion sort the here
for (int y=0;y < 6; y++)
{
SequentialSearch(sorted, arraySize, targets[y], compareS, findS);
// void SequentialSearch(int isorted[],int size, int target, int
&scompares, bool &found);
BinarySearch(sorted, compareB, firstN, lastN, findB, targets[y]);
// void BinarySearch(int isorted[],int &compares, int first, int last,
int &found, int target);
cout << setw(15)<< "Unsorted Array" << setw(15) << "Sorted Array" <<
endl;
for (int z=0; z< arraySize; z++){
cout << setw(15) << unSort[z] << setw(15)<< sorted[z] << endl;
}
cout << endl << "Target: " << targets[y] << endl;
cout << endl << "Binary Search Found: ";
if (findB == true)
cout << compareB;
else
cout << " Nothing" << endl;
cout << endl << "Sequential search Found: ";
if (findS == true)
cout << compareS << endl;
else cout << " Nothing" << endl << endl;
}
system("pause");
return EXIT_SUCCESS;
}
//insertion sort starts here
void insertionSort(int isort[], int isorted[],int size)
{
int i,j;
bool Done;
for (int k=0; k < size; k++) isorted[k] = isort[k]; // copy numArray(main)
into isort1
for(i=1;i<size;i++)
{
j=i;
Done = false;
while(j>=1 && !Done)
{
if (isorted[j-1] isorted[j])
swap(isorted[j-1], isorted[j]);
else
Done = true;
j-- ;
}
// end of WHILE loop
} // end of FOR loop
} // end of insertion sort
void SequentialSearch(int isorted[],int size, int target, int &scompares,
bool &found)
{
scompares = 0;
int index;
if (size ==0)
found = false;
else
scompares = 1;
index = 0;
while ((index <size -1) && (isorted[index] != target))
index++;
scompares++;
if (isorted[index] == target)
found = true;
else
found = false;
}
void BinarySearch(int isorted[],int &compares, int first, int last, bool
&found, int target)
{
compares=0;
int middle;
if(first last)
found = false;
else
compares++;
middle = (first + last)/2;
if (middle == target)
found = true;
else if (middle < target)
BinarySearch(isorted,compares, middle++ , last, found,
target);
else
BinarySearch(isorted,compares, first, middle--, found,
target);
}// end of Binary Search
/*void print(int isort[], int isorted[], int size, int count, int bfound,
int sfound, int target)
{
outFile << " Unsorted List Insertion Sorted" << endl;
for (int k =0;k < size;k++)
outFile << setw(15) <<isort[k] << setw(16) << << setw(20) << isorted[k]
<< endl;
outFile << endl << "Target: " << setw(23) << target << endl;
outFile << "Binary Search Found: " << found << endl;
outFile << "Sequential Search Found: " <<
}// end of print function */
|
