Homework SourseC Searching Sorting Answer each question seperately 5 Sort
C++ Searching & Sorting
(Answer each question seperately)
5. Sort the following list using the selection sort algorithm. Show the list after each iteration of the outerforloop.
36, 55, 17, 35, 63, 85, 12, 48, 3, 66
6. Consider the following list: 5, 18, 21, 10, 55, 20
The first three keys are in order. To move 10 to its proper position using the insertion sort as described in this chapter, exactly how many key comparisons are executed?
7. Consider the following list: 7, 28, 31, 40, 5, 20
The first four keys are in order. To move 5 to its proper position using the insertion sort as described in this chapter, exactly how many key comparisons are executed?
8. Consider the following list: 28, 18, 21, 10, 25, 30, 12, 71, 32, 58, 15
This list is to be sorted using the insertion sort algorithm. Show the resulting list after six
passes of the sorting phase – that is, after six iterations of the for loop.
9. Perform the insertion sort algorithm using the following list of keys: 18, 8, 11, 9, 15, 20, 32, 61, 22, 48, 75, 83, 35, 3
Show the list after each iteration. Exactly how many key comparisons are executed to sort this list using insertion sort?
10. a. The performance of bubble sort can be improved if we stop the sorting process as soon as we find that in an iteration, no swapping of elements takes place. Write a function that implements bubble sort algorithm using this fact.
b. Using the algorithm that you designed in part (a), find the number of iterations that are needed to sort the list: 65, 14, 52, 43, 75, 25, 80, 90, 95.
11. Suppose that L is a sorted list of 4096 elements. What is the maximum number of comparisons made by binary search to determine whether an item is in L?
12. Suppose that the elements of a list are in descending order, and they need to be put in ascending order. Write a C++ function that takes as input an array of items in descending order and the number of elements in the array. The function must not incorporate any sorting algorithms, that is, no item comparisons should take place.
Solution
#include <iostream>
#include \"SearchAndSort.h\"
using namespace std;
void main()
{
//initilizes the varibles to store the number of comparisons
int linearSearchComp=0;
int binarySearchComp=0;
int insertionSortComp=0;
int selectionSortComp=0;
int bubbleSortComp=0;
int mergeSortComp=0;
for(int i = 0; i < 50; i++) //runs 50 instances of the various sorting and seraching methods on data
{
SearchAndSort arr;
cout << \"Initial Conditions\" << endl;
arr.print();
cout << endl << \"After Linear Search\" << endl;
linearSearchComp = linearSearchComp + arr.linearSearch(50);
arr.print();
cout << endl << \"After Binary Search\" << endl;
binarySearchComp = binarySearchComp + arr.binarySearch(50);
arr.print();
cout << endl << \"After Insertion Sort\" << endl;
insertionSortComp = insertionSortComp + arr.insertionSort();
arr.print();
cout << endl << \"After Selection Sort\" << endl;
selectionSortComp = selectionSortComp + arr.selectionSort();
arr.print();
cout << endl << \"After Bubble Sort\" << endl;
bubbleSortComp = bubbleSortComp + arr.bubbleSort();
arr.print();
cout << endl << \"After Merge Sort\" << endl;
mergeSortComp = mergeSortComp + arr.mergeSort();
arr.print();
}
//detemines the average amount of comparisons for that are used for each searching and sorting algorithms
linearSearchComp = linearSearchComp / 50;
binarySearchComp = binarySearchComp / 50;
insertionSortComp = insertionSortComp / 50;
selectionSortComp = selectionSortComp / 50;
bubbleSortComp = bubbleSortComp / 50;
mergeSortComp = mergeSortComp / 50;
//outputs the averge number of comparisons performed for each searching and sorting algorithms
cout << \"Average Number of Comparisons for Linear Search \" << linearSearchComp << endl;
cout << \"Average Number of Comparisons for Binary Search \" << binarySearchComp << endl;
cout << \"Average Number of Comparisons for Insertion Sort \" << insertionSortComp << endl;
cout << \"Average Number of Comparisons for Selection Sort \" << selectionSortComp << endl;
cout << \"Average Number of Comparisons for Bubble Sort \" << bubbleSortComp << endl;
cout << \"Average Number of Comparisons for Merge Sort \" << mergeSortComp << endl;
system(\"pause\");
}
#ifndef SEARCH_AND_SORT_H
#define SEARCH_AND_SORT_H
class SearchAndSort
{
public:
SearchAndSort();
void prepareArr();
void copyArr();
void print();
int linearSearch(int); //takes in key for search and returns number of comparisons
int binarySearch(int); //takes in key for search and returns number of comparisons
int insertionSort(); //returns number of comparisons
int selectionSort(); //returns number of comparisons
int bubbleSort(); //returns number of comparisons
int mergeSort(); //returns number of comparisons
private:
static const int size = 100;
int initialArr[size];
int sortResult[size];
int searchResult;
int mergeSortReccur(int,int); //recursive funtion used for merge sort
int merge(int,int,int,int); //utility function for the merge sort that merges two sub arrays
};
#include \"SearchAndSort.h\"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <ctime>
using namespace std;
SearchAndSort::SearchAndSort()
{
prepareArr();
copyArr();
}
void SearchAndSort::prepareArr() //fill an array with 100 elements with random values from 0 to 100
{
srand(time(0)); //time is used as the random seed
for(int i = 0; i <= size-1; i++)
{
initialArr<i> = rand() % 101; //assigns random number in array
}
}
void SearchAndSort::copyArr() //copies the values stored in initial array to the sorted result array
{
for(int i = 0; i <= size-1; i++)
{
sortResult<i> = initialArr<i>; //copies element by element
}
}
void SearchAndSort::print() //outputs the initial array, sorted result array, and search result
{
cout << \"Initial Array\" << endl;
for(int i = 0; i <= size-1; i++)
{
cout << initialArr<i> << \" \";
}
cout << endl;
cout << \"Sorted Result Array\" << endl;
for(int i = 0; i <= size-1; i++)
{
cout << sortResult<i> << \" \";
}
cout << endl;
cout << \"Search Result\" << endl;
cout << searchResult << endl;
}
int SearchAndSort::linearSearch(int key)
{
copyArr();
int comparisons = 0;
searchResult = -1;
for(int i = 0; i <= size-1; i++) //cycles through each element in the array
{
comparisons++;
if(key == initialArr<i>) //if the value in array matches key then position is stored
{
searchResult = i;
break; //breaks once values is found in array
}
}
return comparisons;
}
int SearchAndSort::binarySearch(int key)
{
mergeSort(); //binary search requires that the array be sorted before search
int low = 0;
int high = size -1;
int mid = (low + high + 1) / 2;
int loc = -1;
int comparisons = 0;
do{
if(key == sortResult[mid]) //checks to see if the middle value is equal to the key
{
loc = mid; //if so the location is set to middle position
comparisons++;
}
else if(key > sortResult[mid]) //if key is greater than the mid point then the key value must be in the first half of the array if it exists at all
{
high = mid - 1; //make the new right bound of array to the left of the midpoint
comparisons++;
}
else //if key is less than the mid point then the key value must be in the second half of the array if it exists at all
{
low = mid + 1; //make the new left bound of the array to the right of the midpoint
comparisons++;
}
mid = (low + high + 1) / 2; // the new bid is determined from the new high and low
}while((low <= high) && (loc == -1)); //runs as long the key has not been found and low does not become greater than high
searchResult = loc;
return comparisons;
}
int SearchAndSort::insertionSort()
{
copyArr();
int j, insert = 0, comparisons = 0;
for(int i = 1; i <= size-1; i++)
{
comparisons++;
insert = sortResult<i>;
for( j = i - 1; (j >= 0) && (sortResult[j] < insert); j--) //smaller values move up in the array
{
comparisons++;
sortResult[j+1] = sortResult[j];
}
sortResult[j+1] = insert; //put the inserted value in the its the right place to be sorted
}
return comparisons;
}
int SearchAndSort::selectionSort()
{
copyArr();
int comparisons = 0;
int first;
for(int i = size-1; i > 0; i--)
{
comparisons++;
first = 0;
for(int j = 1; j <= i; j++) //locates smallest between 1 and i
{
comparisons++;
if(sortResult[j] < sortResult[first])
{
first = j;
comparisons++;
}
}
int temp = sortResult[first]; //swaps the smallest with the element in position i
sortResult[first] = sortResult<i>;
sortResult<i> = temp;
}
return comparisons;
}
int SearchAndSort::bubbleSort()
{
copyArr();
int comparisons = 0;
for(int i = 0; i < size-1; i++)
{
comparisons++;
for(int j = 0; j < size-1; j++)
{
comparisons++;
if(sortResult[j+1] > sortResult[j]) //if next element is greater than the current element then swap elements
{
comparisons++;
int temp = sortResult[j]; //swaps the elements
sortResult[j] = sortResult[j+1];
sortResult[j+1] = temp;
}
}
}
return comparisons;
}
int SearchAndSort::mergeSort()
{
copyArr();
return mergeSortReccur(0,size-1); //calls the merge sort recursive function and returns the number of comparisons
}
int SearchAndSort::mergeSortReccur(int low, int high)
{
int comparisons = 0;
int mid = 0;
if((high - low) >= 1)
{
comparisons++;
mid = ((low + high) / 2);
mergeSortReccur(low, mid); //runs recursive function with first half of array
mergeSortReccur(mid+1, high); //runs recursive function with second half of the array
comparisons = comparisons + merge(low, mid, mid+1, high); //call the merge and totals the number of comparisons
}
return comparisons;
}
int SearchAndSort::merge(int left, int mid1, int mid2, int right) //merges two sub arrays
{
int leftIndex = left;
int rightIndex = mid2;
int combinedIndex = left;
int combined[size];
int comparisons = 0;
while(leftIndex <= mid1 && rightIndex <= right) //merge arrays until the end of the either array
{
comparisons++;
//places larger of the two current elements into the resulting combined array
if(sortResult[leftIndex] >= sortResult[rightIndex])
{
comparisons++;
combined[combinedIndex++] = sortResult[leftIndex++];
}else
{
comparisons++;
combined[combinedIndex++] = sortResult[rightIndex++];
}
}
if(leftIndex == mid2) //if the left array is at end
{
comparisons++;
while(rightIndex <= right) //copy the remaining elements in the right array
{
comparisons++;
combined[combinedIndex++] = sortResult[rightIndex++];
}
}else //if the right array is at end
{
comparisons++;
while(leftIndex <= mid1) //copy the remaing elements in the left array
{
comparisons++;
combined[combinedIndex++] = sortResult[leftIndex++];
}
}
//copies values back in the original result array
for(int i = left; i <= right; i++)
sortResult<i> = combined<i>;
return comparisons;
}
