Question

Develop a program that creates just 3 identical arrays, mylist_1, mylist_2, and mylist_3, of just 250 items. For this assignment, the program then will sort mylist_1 using a bubble sort, mylist_2 using a selection sort, and mylist_3 will be using an insertion sort and outputs the number of comparisons and item assignments made by each sorting algorithm.

template <class elemType>
int seqSearch(const elemType list[], int length, const elemType& item)
{
int loc;
bool found = false;

loc = 0;

while (loc < length && !found)
if (list[loc] == item)
found = true;
else
loc++;

if (found)
return loc;
else
return -1;
} //end seqSearch

template <class elemType>
int binarySearch(const elemType list[], int length,
const elemType& item)
{
int first = 0;
int last = length - 1;
int mid;

bool found = false;

while (first <= last && !found)
{
mid = (first + last) / 2;

if (list[mid] == item)
found = true;
else if (list[mid] > item)
last = mid - 1;
else
first = mid + 1;
}

if (found)
return mid;
else
return -1;
} //end binarySearch

template <class elemType>
void bubbleSort(elemType list[], int length)
{
for (int iteration = 1; iteration < length; iteration++)
{
for (int index = 0; index < length - iteration;
index++)
{
if (list[index] > list[index + 1])
{
elemType temp = list[index];
list[index] = list[index + 1];
list[index + 1] = temp;
}
}
}
} //end bubbleSort

template <class elemType>
void selectionSort(elemType list[], int length)
{
int minIndex;

for (int loc = 0; loc < length; loc++)
{
minIndex = minLocation(list, loc, length - 1);
swap(list, loc, minIndex);
}
} //end selectionSort

template <class elemType>
void swap(elemType list[], int first, int second)
{
elemType temp;

temp = list[first];
list[first] = list[second];
list[second] = temp;
} //end swap

template <class elemType>
int minLocation(elemType list[], int first, int last)
{
int minIndex;

minIndex = first;

for (int loc = first + 1; loc <= last; loc++)
if (list[loc] < list[minIndex])
minIndex = loc;

return minIndex;
} //end minLocation

template <class elemType>
void insertionSort(elemType list[], int length)
{
for (int firstOutOfOrder = 1; firstOutOfOrder < length;
firstOutOfOrder++)
if (list[firstOutOfOrder] < list[firstOutOfOrder - 1])
{
elemType temp = list[firstOutOfOrder];
int location = firstOutOfOrder;

do
{
list[location] = list[location - 1];
location--;
}
while(location > 0 && list[location - 1] > temp);

list[location] = temp;
}
} //end insertionSort

template <class elemType>
void quickSort(elemType list[], int length)
{
recQuickSort(list, 0, length - 1);
} //end quickSort

template <class elemType>
void recQuickSort(elemType list[], int first, int last)
{
int pivotLocation;

if (first < last)
{
pivotLocation = partition(list, first, last);
recQuickSort(list, first, pivotLocation - 1);
recQuickSort(list, pivotLocation + 1, last);
}
} //end recQuickSort

template <class elemType>
int partition(elemType list[], int first, int last)
{
elemType pivot;

int smallIndex;

swap(list, first, (first + last) / 2);

pivot = list[first];
smallIndex = first;

for (int index = first + 1; index <= last; index++)
if (list[index] < pivot)
{
smallIndex++;
swap(list, smallIndex, index);
}

swap(list, first, smallIndex);

return smallIndex;
} //end partition

template <class elemType>
void heapSort(elemType list[], int length)
{
buildHeap(list, length);

for (int lastOutOfOrder = length - 1; lastOutOfOrder >= 0;
lastOutOfOrder--)
{
elemType temp = list[lastOutOfOrder];
list[lastOutOfOrder] = list[0];
list[0] = temp;
heapify(list, 0, lastOutOfOrder - 1);
}//end for
}//end heapSort

template <class elemType>
void heapify(elemType list[], int low, int high)
{
int largeIndex;

elemType temp = list[low]; //copy the root node of
//the subtree

largeIndex = 2 * low + 1; //index of the left child

while (largeIndex <= high)
{
if (largeIndex < high)
if (list[largeIndex] < list[largeIndex + 1])
largeIndex = largeIndex + 1; //index of the
//largest child

if (temp > list[largeIndex]) //subtree
//is already in a heap
break;
else
{
list[low] = list[largeIndex]; //move the larger
//child to the root
low = largeIndex; //go to the subtree to
//restore the heap
largeIndex = 2 * low + 1;
}
}//end while

list[low] = temp; //insert temp into the tree,
//that is, list
}//end heapify

template <class elemType>
void buildHeap(elemType list[], int length)
{
for (int index = length / 2 - 1; index >= 0; index--)
heapify(list, index, length - 1);
}

Answer 1

CODE:

CODE(for copy):

#include<iostream>
#include<ctime>
#include<cstdlib>

using namespace std;

void bubbleSort(int list[], int length)
{
int comparison = 0, item_assignment = 0;
item_assignment++; //Assigning iteration=1;
for (int iteration = 1; iteration < length; iteration++)
{
comparison++; //Comparing iteration < length
item_assignment++; //Assigning index=0;
for (int index = 0; index < length - iteration; index++)
{
comparison++; //Comparing index < length - iteration
if (list[index] > list[index + 1])
{
comparison++; //Comparing list[index] > list[index + 1]
int temp = list[index];
list[index] = list[index + 1];
list[index + 1] = temp;
item_assignment+=3; //Assigning above three statement
}
}
}
cout<<"Bubble Sort\n";
cout<<"Number of comparison: "<<comparison<<"\n";
cout<<"Number of item assignment: "<<item_assignment<<"\n";
} //end bubbleSort

void swap(int list[], int first, int second)
{
int temp;

temp = list[first];
list[first] = list[second];
list[second] = temp;
} //end swap

int minLocation(int list[], int first, int last, int &comp, int &assignment)
{
int minIndex;
assignment++; //Assigning minIndex=first;
minIndex = first;
assignment++; //Assigning loc=first+1;
for (int loc = first + 1; loc <= last; loc++)
{
comp++; //Comparing loc <= last
if (list[loc] < list[minIndex])
{
comp++; //Comparing list[loc] < list[minIndex]
minIndex = loc;
assignment++; //Assigning minIndex = loc;
}
}

return minIndex;
} //end minLocation

void selectionSort(int list[], int length)
{
int minIndex, comparison = 0, item_assignment = 0;

item_assignment++; //Assigning loc=0;
for (int loc = 0; loc < length; loc++)
{
comparison++; //Comparing loc < length
minIndex = minLocation(list, loc, length - 1, comparison, item_assignment);
swap(list, loc, minIndex);
item_assignment+=3; //Assignment in swap condition
}
cout<<"Selection Sort\n";
cout<<"Number of comparison: "<<comparison<<"\n";
cout<<"Number of item assignment: "<<item_assignment<<"\n";
} //end selectionSort

void insertionSort(int list[], int length)
{
int comparison = 0, item_assignment = 0;
item_assignment++; //Assigning firstOutOfOrder = 1
for (int firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++)
{
comparison++; //Comparing firstOutOfOrder < length
if (list[firstOutOfOrder] < list[firstOutOfOrder - 1])
{
comparison++; //Comparing firstOutOfOrder < length
int temp = list[firstOutOfOrder];
int location = firstOutOfOrder;
item_assignment+=2; //Assigning of above 2 statement
do
{
list[location] = list[location - 1];
location--;
item_assignment++; //Assigning list[location] = list[location - 1]
comparison+=2; //Comparing while statement
}
while(location > 0 && list[location - 1] > temp);

list[location] = temp;
item_assignment++; //Assigning list[location]=temp
}
}
cout<<"Insertion Sort\n";
cout<<"Number of comparison: "<<comparison<<"\n";
cout<<"Number of item assignment: "<<item_assignment<<"\n";
} //end insertionSort

void Create_Array(int mylist[], int len)
{
srand(time(0));
for(int i=0; i < len; i++)
{
mylist[i] = rand() % 10000;
}
}

int main()
{
int mylist_1[250], mylist_2[250], mylist_3[250];
Create_Array(mylist_1, 250);
for(int i=0; i<250; i++)
{
mylist_2[i]=mylist_1[i];
mylist_3[i]=mylist_1[i];
}
bubbleSort(mylist_1, 250);
selectionSort(mylist_2, 250);
insertionSort(mylist_3, 250);
return 0;
}

OUTPUT:

For any doubt please comment.