Coding questions: Create an ADT that contains a fixed-size array that can hold a
ID: 655163 • Letter: C
Question
Coding questions: Create an ADT that contains a fixed-size array that can hold at most 100 integers and the following member functions:
A default constructor that initializes all the elements in this array to 0.
A member function that asks an end user to provide a list of integers from the keyboard and stores these numbers into the fixed-size array.
A member function that recursively prints out the array in reverse order. For example, if the array contains the number 4, 19, and 17. Your function will print out: 17, 19, 4.
A member function that recursively searches the largest number in the array. This function will return not only the value of the largest number but also its index in the array.
A member function that recursively finds the value of the k-th smallest number in the array, where k is provided by the end-user. You are required to use the partition-based, recursive algorithm as discussed in class.
A member function that implements the QuickSort algorithm to sort the array in increasing order.
A member function that implements the QuickSort algorithm to sort the array in decreasing order.
An overloaded put operator (<<) to recursively print out the elements in the array in order.
Explanation / Answer
#include <iostream>
#include <iomanip>
using namespace std;
#define SIZE 9
void swap(int a[], int i, int j)
{
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void print(const int arr[])
{
for(int i=0;i < SIZE; i++)
{
cout << setw(3) << arr[i];
}
cout << endl;
}
/* sort arr[left]...arr[right] into increasing order */
void qsort(int a[], int left_index, int right_index)
{
int left, right, pivot;
if(left_index >= right_index) return;
left = left_index;
right = right_index;
// pivot selection
pivot = a[(left_index + right_index) /2];
// partition
while(left <= right)
{
while(a[left] < pivot) left++;
while(a[right] > pivot) right--;
if(left <= right)
{
swap(a,left,right);
left++; right--;
}
print(a);
}
// recursion
qsort(a,left_index,right);
qsort(a,left,right_index);
for(int i =0; i < size; i++)
{
cout<<" The array elements in asceding order: "<<endl<<a[i];
}
cout<<" Array elements in discending order are: ";
for(int i= size-1; i>=0; i--)
cout<<a[i];
}
int main()
{
int a[SIZE]={1, 12, 5, 26, 7, 14, 3, 7, 2};
print(a);
qsort(a,0,SIZE-1);
}