Question

C++

Time the sequential search and the binary search methods several times each for randomly generated values, then record the results in a table. Do not time individual searches, but groups of them. For example, time 100 searches together or 1,000 searches together. Compare the running times of these two search methods that are obtained during the experiment.

Regarding the efficiency of both search methods, what conclusion can be reached from this experiment? Both the table and your conclusions should be included in a separate Word document.

main.cpp

/********************************************

* Week 5 lesson: *

* ArrayList class with search algorithms *

*********************************************/

#include

#include "ArrayList.h"

#include

using namespace std;

/*

* Program to test the ArrayList class.

*/

int main()

{

srand((unsigned)time(0));

//list creation

ArrayList numbers;

for (int i = 0; i<20; i++)

{

numbers.add(rand()%100);

}

//printing the list

cout << "List of numbers:" << endl <<"\t";

numbers.display();

int x;

//searching with sequential search

cout << endl << "(Sequential Search) Enter a number: ";

cin >> x;

if (numbers.sequentialSearch(x)) cout << "Found!" << endl;

else cout << "Not found!" << endl;

//Sorting the list

numbers.quicksort();

cout << endl << "Sorted list of integers:" << endl <<"\t";

numbers.display();

//searching with sorted search

cout << endl << "(Sorted Search) Enter a number: ";

cin >> x;

if (numbers.sortedSearch(x)) cout << "Found!" << endl;

else cout << "Not found!" << endl;

//searching with binary search

cout << endl << "(Binary Search) Enter a number: ";

cin >> x;

if (numbers.binarySearch(x)) cout << "Found!" << endl;

else cout << "Not found!" << endl;

return 0;

}

ArrayList.cpp

/********************************************

* Week 5 lesson: *

* ArrayList class with search algorithms *

*********************************************/

#include

#include "ArrayList.h"

using namespace std;

/*

* Default constructor. Sets length to 0, initializing the list as an empty

* list. Default size of array is 20.

*/

ArrayList::ArrayList()

{

SIZE = 20;

list = new int[SIZE];

length = 0;

}

/*

* Destructor. Deallocates the dynamic array list.

*/

ArrayList::~ArrayList()

{

delete [] list;

list = NULL;

}

/*

* Determines whether the list is empty.

*

* Returns true if the list is empty, false otherwise.

*/

bool ArrayList::isEmpty()

{

return length == 0;

}

/*

* Prints the list elements.

*/

void ArrayList::display()

{

for (int i=0; i < length; i++)

cout << list[i] << " ";

cout << endl;

}

/*

* Adds the element x to the end of the list. List length is increased by 1.

*

* x: element to be added to the list

*/

void ArrayList::add(int x)

{

if (length == SIZE)

{

cout << "Insertion Error: list is full" << endl;

}

else

{

list[length] = x;

length++;

}

}

/*

* Removes the element at the given location from the list. List length is

* decreased by 1.

*

* pos: location of the item to be removed

*/

void ArrayList::removeAt(int pos)

{

if (pos < 0 || pos >= length)

{

cout << "Removal Error: invalid position" << endl;

}

else

{

for ( int i = pos; i < length - 1; i++ )

list[i] = list[i+1];

length--;

}

}

/*

* Bubble-sorts this ArrayList

*/

void ArrayList::bubbleSort()

{

for (int i = 0; i < length - 1; i++)

for (int j = 0; j < length - i - 1; j++)

if (list[j] > list[j + 1])

{

//swap list[j] and list[j+1]

int temp = list[j];

list[j] = list[j + 1];

list[j + 1] = temp;

}

}

/*

* Quick-sorts this ArrayList.

*/

void ArrayList::quicksort()

{

quicksort(0, length - 1);

}

/*

* Recursive quicksort algorithm.

*

* begin: initial index of sublist to be quick-sorted.

* end: last index of sublist to be quick-sorted.

*/

void ArrayList::quicksort(int begin, int end)

{

int temp;

int pivot = findPivotLocation(begin, end);

// swap list[pivot] and list[end]

temp = list[pivot];

list[pivot] = list[end];

list[end] = temp;

pivot = end;

int i = begin,

j = end - 1;

bool iterationCompleted = false;

while (!iterationCompleted)

{

while (list[i] < list[pivot])

i++;

while ((j >= 0) && (list[pivot] < list[j]))

j--;

if (i < j)

{

//swap list[i] and list[j]

temp = list[i];

list[i] = list[j];

list[j] = temp;

i++;

j--;

} else

iterationCompleted = true;

}

//swap list[i] and list[pivot]

temp = list[i];

list[i] = list[pivot];

list[pivot] = temp;

if (begin < i - 1)

quicksort(begin, i - 1);

if (i + 1 < end)

quicksort(i + 1, end);

}

/*

* Computes the pivot location.

*/

int ArrayList::findPivotLocation(int b, int e)

{

return (b + e) / 2;

}

/*

* Determines if an item exists in the array list using sequential (linear)

* search.

*

* x: item to be found.

*

* Returns true if x is found in the list, false otherwise.

*/

bool ArrayList::sequentialSearch(int x)

{

for (int i=0; i < length; i++)

if (list[i] == x)

return true; // x is in the array

return false; // x is not in the array

}

/*

* Determines if an item exists in the array list using sorted search.

* Precondition: list must be sorted.

*

* x: item to be found.

*

* Returns true if x is found in the list, false otherwise.

*/

bool ArrayList::sortedSearch(int x)

{

int i = 0;

while (i < length && list[i] < x)

i++;

if (i < length && list[i] == x)

return true; // x is in the array

else

return false; // x is not in the array

}

/*

* Determines if an item exists in the array list using binary search.

* Precondition: list must be sorted.

*

* x: item to be found.

*

* Returns true if x is found in the list, false otherwise.

*/

bool ArrayList::binarySearch(int x)

{

int first = 0, last = length - 1, pivot;

bool found = false;

while (first <= last && !found)

{

pivot = (first + last) / 2;

if (list[pivot] == x)

found = true;

else if (x < list[pivot])

last = pivot - 1;

else

first = pivot + 1;

}

if (found)

return true;

else

return false;

}

ArrayList.h

/********************************************

* Week 5 lesson: *

* ArrayList class with search algorithms *

*********************************************/

/*

* Class implementing an array based list. Sequential search, sorted search, and

* binary search algorithms are implemented also.

*/

class ArrayList

{

public:

ArrayList ();

~ArrayList();

bool isEmpty();

void display();

void add(int);

void removeAt(int);

void bubbleSort();

void quicksort();

bool sequentialSearch(int);

bool sortedSearch(int);

bool binarySearch(int);

private:

void quicksort(int, int);

int findPivotLocation(int, int);

int SIZE; //size of the array that stores the list items

int *list; //array to store the list items

int length; //amount of elements in the list

};

Answer 1

Hi,
i used the following code, to meaure the times,

#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

class ArrayList
{
public:
ArrayList ();
~ArrayList();
bool isEmpty();
void display();
void add(int);
void removeAt(int);
void bubbleSort();
void quicksort();
bool sequentialSearch(int);
bool sortedSearch(int);
bool binarySearch(int);
private:
void quicksort(int, int);
int findPivotLocation(int, int);
int SIZE; //size of the array that stores the list items
int *list; //array to store the list items
int length; //amount of elements in the list
};
/*
* Program to test the ArrayList class.
*/
ArrayList::ArrayList()
{
SIZE = 500;
list = new int[SIZE];
length = 0;
}
/*
* Destructor. Deallocates the dynamic array list.
*/
ArrayList::~ArrayList()
{
delete [] list;
list = NULL;
}
/*
* Determines whether the list is empty.
*
* Returns true if the list is empty, false otherwise.
*/
bool ArrayList::isEmpty()
{
return length == 0;
}
/*
* Prints the list elements.
*/
void ArrayList::display()
{
for (int i=0; i < length; i++)
cout << list[i] << " ";
cout << endl;
}
/*
* Adds the element x to the end of the list. List length is increased by 1.
*
* x: element to be added to the list
*/
void ArrayList::add(int x)
{
if (length == SIZE)
{
cout << "Insertion Error: list is full" << endl;
}
else
{
list[length] = x;
length++;
}
}
/*
* Removes the element at the given location from the list. List length is
* decreased by 1.
*
* pos: location of the item to be removed
*/
void ArrayList::removeAt(int pos)
{
if (pos < 0 || pos >= length)
{
cout << "Removal Error: invalid position" << endl;
}
else
{
for ( int i = pos; i < length - 1; i++ )
list[i] = list[i+1];
length--;
}
}
/*
* Bubble-sorts this ArrayList
*/
void ArrayList::bubbleSort()
{
for (int i = 0; i < length - 1; i++)
for (int j = 0; j < length - i - 1; j++)
if (list[j] > list[j + 1])
{
//swap list[j] and list[j+1]
int temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
}
}
/*
* Quick-sorts this ArrayList.
*/
void ArrayList::quicksort()
{
quicksort(0, length - 1);
}
/*
* Recursive quicksort algorithm.
*
* begin: initial index of sublist to be quick-sorted.
* end: last index of sublist to be quick-sorted.
*/
void ArrayList::quicksort(int begin, int end)
{
int temp;
int pivot = findPivotLocation(begin, end);
// swap list[pivot] and list[end]
temp = list[pivot];
list[pivot] = list[end];
list[end] = temp;
pivot = end;
int i = begin,
j = end - 1;
bool iterationCompleted = false;
while (!iterationCompleted)
{
while (list[i] < list[pivot])
i++;
while ((j >= 0) && (list[pivot] < list[j]))
j--;
if (i < j)
{
//swap list[i] and list[j]
temp = list[i];
list[i] = list[j];
list[j] = temp;
i++;
j--;
} else
iterationCompleted = true;
}
//swap list[i] and list[pivot]
temp = list[i];
list[i] = list[pivot];
list[pivot] = temp;
if (begin < i - 1)
quicksort(begin, i - 1);
if (i + 1 < end)
quicksort(i + 1, end);
}
/*
* Computes the pivot location.
*/
int ArrayList::findPivotLocation(int b, int e)
{
return (b + e) / 2;
}
/*
* Determines if an item exists in the array list using sequential (linear)
* search.
*
* x: item to be found.
*
* Returns true if x is found in the list, false otherwise.
*/
bool ArrayList::sequentialSearch(int x)
{
for (int i=0; i < length; i++)
if (list[i] == x)
return true; // x is in the array
return false; // x is not in the array
}
/*
* Determines if an item exists in the array list using sorted search.
* Precondition: list must be sorted.
*
* x: item to be found.
*
* Returns true if x is found in the list, false otherwise.
*/
bool ArrayList::sortedSearch(int x)
{
int i = 0;
while (i < length && list[i] < x)
i++;
if (i < length && list[i] == x)
return true; // x is in the array
else
return false; // x is not in the array
}
/*
* Determines if an item exists in the array list using binary search.
* Precondition: list must be sorted.
*
* x: item to be found.
*
* Returns true if x is found in the list, false otherwise.
*/
bool ArrayList::binarySearch(int x)
{
int first = 0, last = length - 1, pivot;
bool found = false;
while (first <= last && !found)
{
pivot = (first + last) / 2;
if (list[pivot] == x)
found = true;
else if (x < list[pivot])
last = pivot - 1;
else
first = pivot + 1;
}
if (found)
return true;
else
return false;
}
ArrayList getList(int n)
{
srand((unsigned)time(0));
//list creation
ArrayList numbers;
for (int i = 0; i<n; i++)
{
numbers.add(rand()%100);
}
return numbers;
}
int main()
{
ArrayList numbers=getList(500);//getting random list of 500 numbers
//printing the list
cout << "List of numbers:" << endl <<"\t";
numbers.display();
int x;
high_resolution_clock::time_point t1 = high_resolution_clock::now();//mesuring time before
//searching with sequential search
for(int i=0;i<100;i++)
{
if (numbers.sequentialSearch(i)) {
cout<<"";
}
}

high_resolution_clock::time_point t2 = high_resolution_clock::now();//mesuring time after

auto duration = duration_cast<microseconds>( t2 - t1 ).count();
cout <<"(100 searches)for sequential seacrh in micro seconds "<< duration<<endl;//printing difference
//Sorting the list
numbers.quicksort();

//searching with binary search
t1 = high_resolution_clock::now();//mesuring time before
for(int i=0;i<100;i++)
{
if (numbers.binarySearch(i))
cout << "";
  
}
t2 = high_resolution_clock::now();//mesuring time after

duration = duration_cast<microseconds>( t2 - t1 ).count();
cout <<"(100 searches)for binary seacrh in micro seconds "<< duration<<endl;//printing difference
  
t1 = high_resolution_clock::now();//mesuring time before
//searching with sequential search
for(int i=0;i<1000;i++)
{
if (numbers.sequentialSearch(i)) {
cout<<"";
}
}

t2 = high_resolution_clock::now();//mesuring time after

duration = duration_cast<microseconds>( t2 - t1 ).count();
cout <<"(1000 searches)for sequential seacrh in micro seconds "<< duration<<endl;//printing difference
//Sorting the list
numbers.quicksort();

//searching with binary search
t1 = high_resolution_clock::now();//mesuring time before
for(int i=0;i<1000;i++)
{
if (numbers.binarySearch(i))
cout << "";
  
}
t2 = high_resolution_clock::now();//mesuring time after

duration = duration_cast<microseconds>( t2 - t1 ).count();
cout <<"(1000 searches)for binary seacrh in micro seconds "<< duration<<endl; //printing difference
return 0;
}
added comments where i am measuring the times
i tested for array of size 500 and searching numbers from 1 to 100 in case of 100 searches and 1 to 1000 in case of 1000 searches,
we can see from the results clearly that binary search trumps the sequential search as it is of log n complexity where as sequential search is n complexity, you can see the increase in numbers when increasing n by 10 in both cases

Please see the o/p attached -
Thumbs up if this was helpful, otherwise let me know in comments