CS 3358 Quick Sort and Heap Sort

In this assignment, you are asked to implement two fundamental sorting algorithms - quick sort and heapsort. The places you need to fill out in the code are marked by // TODO. You need to read the comments in the code carefully.

• Implement the quick sort algorithm in quicksort.cpp to sort the input array in ascending order, where you are expected to implement three functions, such as Swap(), Partition(), and Quicksort(). The function Partition() must be implemented based on the Lomuto's scheme. In the implementation, you can just use the last element as the pivot element. Note that you will not receive any credit if your implementation is based on the Hoares scheme.
  • You are not expected to change the main() function and declare and implement other additional functions. If you do not want to use Swap() in your implementation, you can just delete it or comment it out.
• Implement the heapsort algorithm in heapsort.cpp to sort the input array in descending order, where you are expected to implement five functions, such as Swap(), PercolateDown(), DeleteMin(), BuildHeap(), and Heapsort().
  • You are not expected to change the main() function and declare and implement other additional functions. If you do not want to use Swap() in your implementation, you can just delete it or comment it out. In addition, you can change the parameters (add or delete some parameters) of each function if necessary.

Starter Codes

quicksort.cpp

#include < iostream>

using namespace std;

// This function exchanges the values of var1 and var2.
void Swap(int& var1, int& var2)
{
// TODO
}

// This function uses the last element as the pivot element and
// partitions the array arr[first..last] by rearranging the elements
// and returning the (correct) position of the pivot, say q, so that
// arr[x] <= arr[q] for all x < q, and arr[x] >= arr[q] for all x > q.
// This function must to be implemented based on the Lomuto’s scheme.
int Partition(int arr[], int first, int last)
{
// TODO
}

// This is the 'quick sort' function that sorts the array arr[first..last]
// in ascending order.
void Quicksort(int arr[], int first, int last)
{
// TODO
}

int main()
{
cout << "Please enter the length (number of elements) of the input array: ";
int size;
cin >> size;

if (size <= 0) {
cout << "Illegal input array length!" << endl;
return 0;
}

int* arr = new int[size];

cout << "Please enter each element in the array" << endl;
cout << "(each element must be an integer within the range of int type)." << endl;
for (int i = 0; i < size; i++) {
cout << "arr[" << i << "] = ";
cin >> arr[i];
}

cout << "The input arr[] is: ";
for (int i = 0; i < size - 1; i++)
cout << arr[i] << ",";
cout << arr[size - 1] << endl;

Quicksort(arr, 0, size - 1);

cout << "After quicksort, the sorted array arr[] is: ";
for (int i = 0; i < size - 1; i++)
cout << arr[i] << ",";
cout << arr[size - 1] << endl;

delete[] arr;

return 0;
}

heapsort.cpp

#include < iostream>

using namespace std;

// This function exchanges the values of var1 and var2.
void Swap(int& var1, int& var2)
{
// TODO
}

// This function performs the 'percolate down' operation from node arr[index].
void PercolateDown(int arr[], int index, int size)
{
// TODO
}

// This function swaps the minimum-value element with the last element
// in arr[first..last] and leaves (does not delete) the minimum-value element.
// After DeleteMin, the heap shrinks by 1.
void DeleteMin(int arr[], int& last)
{
// TODO
}

// This functions coverts the array arr[] to a heap, i.e., it has the *head-order*
// property while it is interpreted as a complete binary tree.
void BuildHeap(int arr[], int size)
{
// TODO
}

// This is the 'heapsort' function that sorts the array arr[] in *descending* order.
// You may want to use the BuildHeap and DeleteMin functions in this function.
void Heapsort(int arr[], int size)
{
// TODO
}

int main()
{
cout << "Please enter the length (number of elements) of the input array: ";
int size;
cin >> size;

if (size <= 0) {
cout << "Illegal input array length!" << endl;
return 0;
}

int* arr = new int[size + 1];

cout << "Please enter each element in the array" << endl;
cout << "(each element must be an integer within the range of int type)." << endl;
for (int i = 1; i <= size; i++) {
cout << "arr[" << i << "] = ";
cin >> arr[i];
}

cout << "The input array arr[] is: ";
for (int i = 1; i < size; i++)
cout << arr[i] << ",";
cout << arr[size] << endl;

Heapsort(arr, size);

cout << "After heapsort, the sorted array arr[] is: ";
for (int i = 1; i < size; i++)
cout << arr[i] << ",";
cout << arr[size] << endl;

delete[] arr;

return 0;
}