Answer to Question #291301 in C++ for hajar

Question

1. make the program run on your computer. Understand the logic of functions.
2. Make changes in the program to sort data in descending order by mergesort and quicksort.
3. Declare a list object D of size 50 and try your program on this object.

Answer 1

#include <iostream>


class List
{
    int size;
    int* arr;


public:
    List(int s)
    {
        this->size = s;
        arr = new int[size];
        for (int i = 0; i != size; ++i)
        {
            arr[i] = rand() % 100;
        }
    }


    void display()
    {
        for (int i = 0; i != size; ++i)
        {
            std::cout<<arr[i]<<" ";
        }
        std::cout << std::endl;
    }


    ~List()
    {
        delete arr;
    }


    void merge_sort(const int begin, const int end)
    {
        if (begin >= end)
            return;


        auto mid = begin + (end - begin) / 2;
        merge_sort(begin, mid);
        merge_sort(mid + 1, end);
        merge(begin, mid, end);
    }


    void merge(int const left, int const mid, int const right)
    {
        auto const subArrayOne = mid - left + 1;
        auto const subArrayTwo = right - mid;


        auto* leftArray = new int[subArrayOne],
            * rightArray = new int[subArrayTwo];


        for (auto i = 0; i < subArrayOne; i++)
            leftArray[i] = arr[left + i];
        for (auto j = 0; j < subArrayTwo; j++)
            rightArray[j] = arr[mid + 1 + j];


        auto indexOfSubArrayOne = 0, 
            indexOfSubArrayTwo = 0; 
        int indexOfMergedArray = left; 


        while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
            if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
                arr[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
                indexOfSubArrayOne++;
            }
            else {
                arr[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
                indexOfSubArrayTwo++;
            }
            indexOfMergedArray++;
        }


        while (indexOfSubArrayOne < subArrayOne) {
            arr[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
            indexOfMergedArray++;
        }


        while (indexOfSubArrayTwo < subArrayTwo) {
            arr[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
            indexOfMergedArray++;
        }
    }


    void swap(int* a, int* b)
    {
        int t = *a;
        *a = *b;
        *b = t;
    }


  
    int partition(int low, int high)
    {
        int pivot = arr[high];    
        int i = (low - 1);  


        for (int j = low; j <= high - 1; j++)
        {
         
            if (arr[j] <= pivot)
            {
                i++;    
                swap(&arr[i], &arr[j]);
            }
        }
        swap(&arr[i + 1], &arr[high]);
        return (i + 1);
    }


  
    void quickSort(int low, int high)
    {
        if (low < high)
        {
            int pi = partition(low, high);


            quickSort(low, pi - 1);
            quickSort(pi + 1, high);
        }
    }


};
int main()
{
    List l(50);
    l.display();
    l.merge_sort(0, 49);
    l.display();


    List l1(50);
    l1.display();
    l1.quickSort(0, 49);
    l1.display();
    
    
    return 0;
}