CSE245_LAB02_SUBMISSION

#include <iostream>
#include <algorithm>
#define SIZE 10
using namespace std;

void swap (int &A, int &B) {
    int temp;
    temp = A;
    A = B;
    B = temp;
}

bool comp (int i, int j) {
    return (i < j) ? true : false;
}

void insertionSort (int *A, long long N) {
    for (int i = 1; i < N; i++)
        for (int j = i - 1; j >= 0 && A[j] > A[j + 1]; j--)
            swap (A[j], A[j + 1]);
}

void bubbleSort (int *A, long long N) {
    for (long long i = 0; i < N - 1; i++)
        for (long long j = N - 1; j >= i + 1; j--)
            if (A[j] < A[j - 1])
                swap (A[j], A[j - 1]);
}

void selectionSort (int *A, long long N) {
    for (int i = 0, k; i < N - 1; i++) {
        k = i;
        for (int j = i + 1; j < N; j++)
            if (A[k] > A[j])
                k = j;
        if (i != k)
            swap (A[i], A[k]);
    }
}

int partition (int A[], int lo, int hi) {
    int x = A[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (A[j] <= x)
            swap (A[++i], A[j]);

    swap (A[i + 1], A[hi]);
    return i + 1;
}

void quickSort (int A[], int lo, int hi) {
    if (lo < hi) {
        int mid = partition (A, lo, hi);
        quickSort (A, lo, mid - 1);
        quickSort (A, mid + 1, hi);
    }
}

void merge (int A[], int lo, int mid, int hi) {
    int n1 = mid - lo + 1;
    int n2 = hi - mid;
    int L[n1];
    int R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = A[lo + i];
    for (int i = 0; i < n2; i++)
        R[i] = A[mid + 1 + i];

    for (int i = 0, j = 0, k = lo; k < hi + 1; k++) {
        if (i == n1)
            A[k] = R[j++];
        else if (j == n2)
            A[k] = L[i++];
        else if (L[i] <= R[j])
            A[k] = L[i++];
        else
            A[k] = R[j++];
    }
}


void mergeSort (int A[], int lo, int hi) {
    if (lo < hi) {
        int mid = (lo + hi) / 2;
        mergeSort (A, lo, mid);
        mergeSort (A, mid + 1, hi);
        merge (A, lo, mid, hi);
    }
}


void cpy (int A[], int B[]) {
    for (int i = 0; i < SIZE; i++)
        B[i] = A[i];
}


void display (int A[]) {
    for (int i = 0; i < SIZE; i++)
        cout << A[i] << " ";
    cout << endl;
}



int main() {
    int A[SIZE] = {8, 9, 7, 6, 5, 4, 3, 2, 1, 3}, B[SIZE];

    cout << "QUICK SORT" << endl;
    cpy (A, B);
    display(B);
    quickSort (B, 0, SIZE - 1);
    display(B);
    cout << endl << endl;

    cout << "MERGE SORT" << endl;
    cpy (A, B);
    display(B);
    mergeSort (B, 0, SIZE - 1);
    display(B);
    cout << endl << endl;

    cout << "BUILT-IN SORT" << endl;
    cpy (A, B);
    display(B);
    sort (B, B + SIZE, comp);
    display(B);
    cout << endl << endl;

    cout << "INSERTION SORT" << endl;
    cpy (A, B);
    display(B);
    insertionSort (B, SIZE);
    display(B);
    cout << endl << endl;

    cout << "BUBBLE SORT" << endl;
    cpy (A, B);
    display(B);
    bubbleSort (B, SIZE);
    display(B);
    cout << endl << endl;

    cout << "SELECTION SORT" << endl;
    cpy (A, B);
    display(B);
    selectionSort (B, SIZE);
    display(B);
    cout << endl << endl;

    return 0;
}