Needs to be done in C++ Searching Applications Design and implement an algorithm
ID: 3873475 • Letter: N
Question
Needs to be done in C++
Searching Applications
Design and implement an algorithm that determines whether or not a given array of integers, list1, is completely contained within another given array of integers, list2. Consider two different scenarios: (1) Both arrays are unsorted and (2) both arrays are sorted and write functions unsortedSearch and sortedSearch for (1) and (2), respectively. Your algorithm for (2) is expected to be more efficient than the one for (1).
main.cpp
/********************************************
* Week 5 lesson: *
* ArrayList class with search algorithms *
*********************************************/
#include <iostream>
#include "ArrayList.h"
#include <time.h>
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 <<" ";
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 <<" ";
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 <iostream>
#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
};
Explanation / Answer
//used brute force in unsortedListSearch and binary saerch in sortedListSearch
/********************************************
* Week 5 lesson: *
* ArrayList class with search algorithms *
*********************************************/
#include <iostream>
#include "ArrayList.h"
#include <time.h>
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 << " ";
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 << " ";
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;
*/
ArrayList list1;
list1.add(2);
list1.add(1);
ArrayList list2;
list2.add(4);
list2.add(1);
list2.add(5);
list2.add(2);
//1 =true and 0=false
cout<<list1.unsortedListSearch(list2);
list1.quicksort();
list2.quicksort();
cout << list1.sortedListSearch(list2);
system("pause");
return 0;
}
------------------
/********************************************
* 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);
int binarySearch2(int);
bool sortedListSearch(ArrayList a);
bool unsortedListSearch(ArrayList a);
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
};
---------------
/********************************************
* Week 5 lesson: *
* ArrayList class with search algorithms *
*********************************************/
#include <iostream>
#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;
}
int ArrayList::binarySearch2(int x)
{
int first = 0, last = length - 1, pivot,index=-1;
bool found = false;
while (first <= last && !found)
{
pivot = (first + last) / 2;
if (list[pivot] == x)
{
index = pivot;
found = true;
}
else if (x < list[pivot])
last = pivot - 1;
else
first = pivot + 1;
}
return index;
}
bool ArrayList::unsortedListSearch(ArrayList a)
{
int foundCount = 0;
for (int i = 0; i<length; i++)
{
for (int j = 0; j<a.length; j++)
{
if (list[i] == a.list[j])
{
foundCount++;
}
}
}
if (foundCount == length)
{
return true;
}
return false;
}
bool ArrayList::sortedListSearch(ArrayList a)
{
int foundCount = 0;
int index = a.binarySearch2(list[0]);
if (index == -1)
{
return false;
}
for (int i = 0; i < length; i++)
{
for (int j = index; j < a.length; j++)
{
if (list[i] == a.list[j])
{
foundCount++;
}
}
}
if (foundCount == length)
{
return true;
}
return false;
}
--------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.