Question

Problem Description

Objective

This practical will test your knowledge on sorting and searching algorithms. In this practical, you will be implementing a number of algorithms. Each of these algorithms will be constructed in a different class. You should make sure that you know the complexity of the algorithms you implement.

Design

Think of how you are going to solve the problem and test your implementation with the test cases you designed based on the stages below. Testing Hint: it’s easier if you test things as a small piece of code, rather than building a giant lump of code that doesn’t compile or run correctly. As part of your design, you should also sketch out how you are going to build and test the code.

Sorting

Implement a base class called Sort. All other sorting algorithms must be derived from this class. You should decide how you are going to store the data that is going to be sorted or worked with as part of your sorting process. It is up to you to decide the storage mechanism.

Step 1: Implement bubble sort in a class called BubbleSort that extends Sort http://en.wikipedia.org/wiki/Bubble_sort

Step 2: Implement quick sort in a class called QuickSort that extends Sort http://en.wikipedia.org/wiki/Quicksort

As a requirement, for the pivot selection, when the list is of length at least 3, please always chose the third value in the list (e.g., if the (sub)list is formed by 4 elements 2, 4, 9, 1, then the pivot is 9). Optional challenge: Can you implement quick sort without using recursion?

Searching

Implement recursive binary search in a class called RecursiveBinarySearch.  In recursive binary search, the parameter list should include a sorted list of elements to be searched, a starting point and an ending point. When we search, we examine the middle element of our array. If we find the element we are looking for, return the index of the element. If the element we are looking for has value less than the middle element, call binary search with the same starting point and an ending point one position less than the current middle index. If the element we are looking for has a value greater than the middle element, call binary search with the same ending point and a starting point one greater than the current middle index.

Main function

The test script will compile your code using

g++ -o main.out -std=c++11 -O2 -Wall *.cpp

It is your responsibility to ensure that your code compiles on the university system. g++ has too many versions, so being able to compile on your laptop does not guarantee that it compiles on the university system. You are encouraged to debug your code on a lab computer (or use SSH).

Create a main function that takes in a list of integers (one line, separated by space) int1 int2 int3 ... intn.

In the main function, the list should be sorted in ascending order first using quick sort, then binary search is used to determine whether 1 belongs to the list or not. Your output should start with either “true” (1 belongs to the list) or “false”, and then followed by the sorted list. Please separate the results using space.

Sample input: 1 3 5 4 -5 100 7777 2014

Sample output: true -5 1 3 4 5 100 2014 7777

Sample input: 0 3 5 4 -5 100 7777 2014

Sample output: false -5 0 3 4 5 100 2014 7777

Answer 1

Please find the requested program below. Als attaching the screenshot of sample output and partial program to understand the indentation in the code.

Please provide your feedback.

Thanks and Happy Learning!

#include<iostream>
#include<vector>
#include<string>
#include<sstream>

class Sort
{
public:
    virtual void DoSort(std::vector<int>& ListToBeSorted) = 0;
};


class BubbleSort : public Sort
{
public:
    //Worst case performance O(n ^ 2)
    //Best case performance     O(n)
    //Average case performance O(n ^ 2)
    void DoSort(std::vector<int>& ListToBeSorted) override
    {
        int listSize = ListToBeSorted.size();
        for (int i = 0; i < listSize; i++)
        {
            for (int j = 0; j < (listSize - i - 1); j++)
            {
                if (ListToBeSorted[j] > ListToBeSorted[j + 1])
                {
                    std::swap(ListToBeSorted[j], ListToBeSorted[j + 1]);
                }
            }
        }
    }

};

class QuickSort : public Sort
{
private:
    int splitList(std::vector<int>& ListToBeSorted, int LeftBoundary, int RightBoundary)
    {
        // Make all the elements less than or equal to the pivot
        // element to the left of pivot element and all the
        // elements greater than or equal to the pivot element
        // to the right of pivot element.

        int pivotElement = 0;
        if ((RightBoundary - LeftBoundary) >= 2)
        {
            //When the list is of length at least 3, please always chose the 
            //third value in the list(e.g., if the(sub)list is formed by 4 
            //elements 2, 4, 9, 1, then the pivot is 9)
            pivotElement = ListToBeSorted[LeftBoundary + 2];
        }
        else
        {
          pivotElement = ListToBeSorted[LeftBoundary];
        }
        int leftBound = LeftBoundary;
        int rightBound = RightBoundary;
        int temp = 0;

        while (rightBound > leftBound)
        {
            while ((ListToBeSorted[rightBound] >= pivotElement) && (rightBound > LeftBoundary))
                rightBound--;

            while ((ListToBeSorted[leftBound] < pivotElement) && (leftBound< RightBoundary))
                leftBound++;

            if (rightBound > leftBound)
            {
                std::swap(ListToBeSorted[leftBound], ListToBeSorted[rightBound]);
            }

        }

        // Swap Pivot element. 
        if ((RightBoundary - LeftBoundary) >= 2)
        {
            std::swap(ListToBeSorted[LeftBoundary + 2], ListToBeSorted[rightBound]);
        }
        else
        {
            std::swap(ListToBeSorted[LeftBoundary], ListToBeSorted[rightBound]);
        }

        return rightBound;
    }

    void quickSort(std::vector<int>& ListToBeSorted, int startIndex, int endIndex)
    {
        if (endIndex > startIndex)
        {
            int pivot = splitList(ListToBeSorted, startIndex, endIndex);

            quickSort(ListToBeSorted, startIndex, pivot);
            quickSort(ListToBeSorted, pivot + 1, endIndex);

        }
    }

public:
   // Worst case performance O(n*n) [When the array is sorted or nearly sorted].
   // Best case performancecO(n log n) (simple partition) OR
   // O(n) (three - way partition and equal keys)
   // Average case performance  O(n log n)

    void DoSort(std::vector<int>& ListToBeSorted) override
    {
        quickSort(ListToBeSorted, 0, ListToBeSorted.size() - 1);
        std::cout << "Quick sort: ";
        for (int i = 0; i < ListToBeSorted.size(); i++)
        {
            std::cout << ListToBeSorted[i] << " ";
        }
        std::cout << std::endl;
    }
};

class RecursiveBinarySearch
{
public:
    // Worst case performance O(log n)
    // Best case performance  O(1)
    // Average case performance O(log n)
    // Worst case space complexity O(1)
    bool binarySearch(std::vector<int>& listTobeSearched, int data, int low, int high)
    {
        //Find the mid position of current search context
        int mid = (low + high) / 2;

        if (data == listTobeSearched[mid])
        {
            //Element found in the list
            return  true;;
        }
        if (low == high)
        {
            //Invalid mid element
            return false;
        }

        if (data < listTobeSearched[mid])
            return binarySearch(listTobeSearched, data, low, mid);
        else if (data > listTobeSearched[mid])
            return  binarySearch(listTobeSearched, data, (mid + 1), high);
    }

};

int main()
{
    std::vector<int> inputList;

    std::string strInput, strToken;
    std::cout << "Enter the list of numbers seperated by a space character" << std::endl;
    std::getline(std::cin, strInput);
    std::stringstream ss(strInput);

    //Extract the numbers by tokenizing the input using space character as delimiter
    while (std::getline(ss, strToken, ' '))
    {
        //Take a list of integers (one line, separated by space) int1 int2 int3 ... intn.
        inputList.push_back(atoi(strToken.c_str()));
    }

    //List should be sorted in ascending order first using quick sort
    Sort *pSort = new QuickSort();
    pSort->DoSort(inputList);

    //Then binary search is used to determine whether 1 belongs to the list or not
    RecursiveBinarySearch bs;
    bool bFound = bs.binarySearch(inputList, 1, 0, inputList.size());

    //Your output should start with either “true”(1 belongs to the list) or “false”, 
    //and then followed by the sorted list.Please separate the results using space.
    std::cout << (bFound ? "true" : "false") << " ";

    for (int i = 0; i < inputList.size(); i++)
    {
        std::cout << inputList[i] << " ";
    }
    
    std::cout << std::endl;
    getchar();
    return 0;
}