/*
 * -----------------------------------------------------
 * CS2S03/SE2S03, November 2011
 * Assignment 5, Question 2
 * File: PE0805.cpp
 * -----------------------------------------------------
 * This program sorts 3 arrays of size n using
 * selection, merge and quick sorting algorithms.
 * -----------------------------------------------------
 */

#include "genlib.h"
#include <iostream>

/* Private function prototypes */

void Sort1(int arr[], int n);
void Sort2(int arr[], int n);
void Sort3(int arr[], int n);

void Merge(int arr[], int arr1[], int arr2[], int n, int n1, int n2);
void Quicksort(int arr[], int start, int end);
int Partition(int arr[], int start, int end);

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

/* Main program */

int main() {
    int arr1[] = {2,1,8,3,0,9,7,5,6,4};
    int arr2[] = {2,1,8,3,0,9,7,5,6,4};
    int arr3[] = {2,1,8,3,0,9,7,5,6,4};

    int n1 = sizeof(arr1) / sizeof(int);
    int n2 = sizeof(arr2) / sizeof(int);
    int n3 = sizeof(arr3) / sizeof(int);

    Sort1(arr1, n1);
    cout << "Selection Sort Result:	";
    Display(arr1, n1);

    Sort2(arr2, n2);
    cout << "Merge Sort Result:	";
    Display(arr2, n2);

    Sort3(arr3, n3);
    cout << "Quick Sort Result:	";
    Display(arr3, n3);

    return 0;
}

/*
 * Function: Sort1
 * Usage: Sort1(arr, n)
 * --------------------
 * This implementation uses an algorithm called selection sort,
 * which can be described in English as follows. With your left
 * hand (lh), point at each element in the array in turn,
 * starting at index 0. At each step in the cycle:
 *
 * 1. Find the smallest element in the range between your left
 * hand and the end of the array, and point at that element
 * with your right hand (rh).
 *
 * 2. Move that element into its correct position by exchanging
 * the elements indicated by your left and right hands.
 */

void Sort1(int arr[], int n) {
    if (n < 2) return;

    for (int lh = 0; lh < n; lh++) {
        int rh = lh;
        for (int i = lh + 1; i < n; i++) {
            if (arr[i] < arr[rh]) rh = i;
        }
        int temp = arr[lh];
        arr[lh] = arr[rh];
        arr[rh] = temp;
    }
}

/*
 * Function: Sort2
 * Usage: Sort2(arr, n) 
 * ------------------------------------------------------------------
 * This function sorts the elements of the array into
 * increasing numerical order using the merge sort algorithm,
 * which consists of the following steps:
 *
 * 1. Divide the array into two halves.
 * 2. Sort each of these smaller arrays recursively.
 * 3. Merge the two arrays back into the original one.
 */

void Sort2(int arr[], int n) {
    if (n <= 1) return;
    int n1 = n/2;
    int n2 = n - n1;
    int* arr1 = new int[n1];
    int* arr2 = new int[n2];

    for (int i = 0; i < n; i++) {
        if (i < n1)
            arr1[i] = arr[i];
        else
            arr2[i-n1] = arr[i];
        }

    Sort2(arr1, n1);
    Sort2(arr2, n2);

    for (int i = 0; i < n; i++) //Not required.
        arr[i] = 0;

    Merge(arr, arr1, arr2, n1, n2);
}

/*
 * Function: Merge
 * Usage: Merge(arr, arr1, arr2, n1, n2)
 * -------------------------------------
 * This function merges two sorted arrays (arr1 and arr2) into the
 * array arr.
 * Because the input arrays are sorted, the implementation can
 * always select the first unused element in one of the input
 * arrays to fill the next position.
 */

void Merge(int arr[], int arr1[], int arr2[], int n1, int n2) {
    int p = 0;
    int p1 = 0;
    int p2 = 0;
    while (p1 < n1 && p2 < n2) {
        if (arr1[p1] < arr2[p2]) {
            arr[p++] = arr1[p1++];
        } else {
            arr[p++] = arr2[p2++];
        }
    }
    while (p1 < n1) arr[p++] = arr1[p1++];
    while (p2 < n2) arr[p++] = arr2[p2++];
}

/*
 * Function: Sort3
 * Usage: Sort3(arr, n)
 * --------------------
 * This function sorts the elements of the array into
 * increasing numerical order using the Quicksort algorithm.
 * In this implementation, Sort is a wrapper function that
 * calls Quicksort to do all the work.
 */

void Sort3(int arr[], int n) {
    Quicksort(arr, 0, n-1);
}

/*
 * Function: Quicksort
 * Usage: Quicksort(arr, start, finish)
 * ------------------------------------
 * Sorts the elements in the array between index positions
 * start and finish, inclusive. The Quicksort algorithm begins
 * by "partitioning" the array so that all elements smaller
 * than a designated pivot element appear to the left of a
 * boundary and all equal or larger values appear to the right.
 * Sorting the subsidiary arrays to the left and right of the
 * boundary ensures that the entire array is sorted.
 */

void Quicksort(int arr[], int start, int finish) {
    if (start >= finish) return;
    int boundary = Partition(arr, start, finish);
    Quicksort(arr, start, boundary - 1);
    Quicksort(arr, boundary + 1, finish);
}

/*
 * Function: Partition
 * Usage: boundary = Partion(arr, start, finish)
 * ---------------------------------------------
 * This function rearranges the elements of the array so that the
 * small elements are grouped at the left end of the array and the
 * large elements are grouped at the right end. The distinction
 * between small and large is made by comparing each element to the
 * pivot value, which is initially taken from array[start]. When the
 * partitioning is done, the function returns a boundary index such
 * that arr[i] < pivot for all i < boundary, arr[i] == pivot
 * for i == boundary, and arr[i] >= pivot for all i > boundary.
 */

int Partition(int arr[], int start, int finish) {
    int pivot = arr[start];
    int lh = start + 1;
    int rh = finish;
    while (true) {
        while (lh < rh && arr[rh] >= pivot) rh--;
        while (lh < rh && arr[lh] < pivot) lh++;
        if (lh == rh) break;
        int temp = arr[lh];
        arr[lh] = arr[rh];
        arr[rh] = temp;
    }
    if (arr[lh] >= pivot) return start;
    arr[start] = arr[lh];
    arr[lh] = pivot;
    return lh;
}

/*
 * Function: Display
 * Usage: Display(arr, n)
 * ----------------------
 * This function displays the array elements.
 */

void Display(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}