Question

Suppose you have a group of N numbers and would like to determine the kth largest. This is known as the selection problem. There are quite a few “obvious” solutions.

One way to solve this problem would be to read the N numbers into an array, sort the array in decreasing order by some simple algorithm such as bubble sort, and then return the element in position k.

A somewhat better algorithm might be to read the 1st k elements into an array and sort them (in decreasing order). Next, each remaining element is read one by one. As a new element arrives, it is ignored if it is smaller than the kth element in the array. Otherwise, it is placed in its correct spot in the array, bumping one element out of the array. When the algorithm ends, the element in the kth position is returned as the answer.

Write a program to solve the selection problem. Let k=N/2.

Draw a table showing the running time of your program for various values of N. ( use Excel to create a chart of exported runtime data )

IT'S C++ CODING LAB

Answer 1

#include <iostream>

using namespace std;

void swap(int *xp, int *yp);

void bubbleSort(int arr[], int n);

void insertElement(int nums[], int size, int pos, int value);

int main()

{

int size;

cout << endl << "How many numbers do you want to enter? ";

cin >> size;

int original[size];

cout << "Enter the numbers: " << endl;

for(int i = 0; i < size; i++)

{

cin >> original[i];

}

cout << "\nThe original array is: ";

for(int i = 0; i < size; i++)

{

if(i == size - 1)

cout << original[i] << endl;

else

cout << original[i] << ", ";

}

cout << endl;

// user input for k

int k;

cout << "Enter the value of k: ";

cin >> k;

int kthArr[k];

int rem[size - k];

// copy all the elements upto k from original array to the kthArr

for(int i = 0; i < k; i++)

{

kthArr[i] = original[i];

}

// copy the remaining elements from original array to rem array

for(int i = 0; i < size - k; i++)

{

rem[i] = original[i + k];

}

// bubble sort the kthArray in decreasing order

bubbleSort(kthArr, k);

int kArrLen = sizeof(kthArr) / sizeof(kthArr[0]);

int remArrLen = sizeof(rem) / sizeof(rem[0]);

cout << endl;

// perform the operation

int counter = 0;

while(counter < remArrLen)

{

// get a new element from the rem array

int testElement = rem[counter];

// if the chosen element from the rem array is greater than the last element of the kthArr array

if(testElement > kthArr[kArrLen - 1])

{

// loop over the whole kthArr

for(int i = 0; i < kArrLen; i++)

{

// if the chosen element is greater than the ith element of the kthArr array, insert the chosen element at the ith position in the kthArr and bumb out the last element from the kthArr

if(testElement > kthArr[i])

{

insertElement(kthArr, kArrLen, i, testElement);

break;

}

}

}

counter++;

}

cout << "The largest element for (k = " << k << ") is: " << kthArr[k - 1] << endl;

return 0;

}

// this method swaps 2 integers

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

// the bubble sort method

void bubbleSort(int arr[], int n)

{

int i, j;

for (i = 0; i < n-1; i++)

{

for (j = 0; j < n-i-1; j++)

{

if (arr[j] < arr[j+1])

swap(&arr[j], &arr[j+1]);

}

}

}

// this method inserts the value at the given position of the specified array of a given size

void insertElement(int nums[], int size, int pos, int value)

{

for(int i = size; i > pos; i--)

  {

    nums[i] = nums[i - 1];

  }

nums[pos] = value;

}

******************************************************************* SCREENSHOT ********************************************************