Write a program that creates a 1000 element array with the data values of 10, 20

Question

Write a program that creates a 1000 element array with the data values of 10, 20, 30,... 10,000 in the elements. using binary search algorithm, search the array three times. Each time output how many comparisons were made by the search. The three searches should be for the values 30, 700, and 777(which should not be found).

Here is a binary search already in this file:

template <class elemType>
void mergeLists(elemType list[], elemType tempList[],
int first, int last, int m)
{
int i = first;
int j = m + 1;
int k = first;

while (i <= m && j <= last)
{
if (list[i] < list[j])
{
tempList[k] = list[i];
i = i + 1;
}
else
{
tempList[k] = list[j];
j = j + 1;
}

k = k + 1;
}

if (i <= m)
while (i <= m)
{
tempList[k] = list[i];
k = k + 1;
i = i + 1;
}
else
while (j <= last)
{
tempList[k] = list[j];
k = k + 1;
j = j + 1;
}
}

template <class elemType>
void recMergeSort(elemType list[], int first, int last)
{
elemType *tempList;
int m;
int i;

tempList = new elemType[last + 1];

if (first < last)
{
m = (first + last) / 2;

recMergeSort(list, first, m); //Merge sort list[first...m]
recMergeSort(list, m + 1, last); //Merge sort list[m+1...t]
mergeLists(list, tempList, first, last, m); //Merge list[first...m]
           //and list[m+1...last];

               //tempList[s...t] contains merged lists
for (i = first; i <= last; i++) //Copy tempList[first...last]
           //into list[first...last]
list[i] = tempList[i];
}
}

template <class elemType>
void mergeSort(elemType list[], int length)
{
recMergeSort(list, 0, length - 1);
}
  

//********************
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 loc, minIndex;

for (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 loc, minIndex;

minIndex = first;

for (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 index, smallIndex;

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

pivot = list[first];
smallIndex = first;

for (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);
}

Explanation / Answer

#include #include #define TOTAL_NUMBERS 1000000000 #define N_TOP_NUMBERS 100 int compare_function(const void *first, const void *second) { int a = *((int *) first); int b = *((int *) second); if (a > b){ return 1; } if (a

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.