CSE245_LAB01_SUBMISSION

#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <ctime>
#define SIZE 1000000
#define RANGE 10000
using namespace std;

int A[SIZE], B[SIZE];

void swap (long long &X, long long &Y) {
    int temp = X;
    X = Y;
    Y = temp;
}

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 sequentialSearch (int *A, int N, int x) {
    for (int i = 0; i < N; i++) {
        if (A[i] == x)
            return i;
    }
    return -1;
}

int binarySearch (int *A, int lo, int hi, int x) {
    if (lo == hi) {
        if (A[lo] == x)
            return lo;
        else
            return -1;
    }
    int mid = (lo + hi) / 2;
    if (A[mid] >= x)
        return binarySearch (A, lo, mid, x);
    else
        return binarySearch (A, mid + 1, hi, x);
}

int binarySearchIterative (int *A, int N, int x) {
    int lo = 0;
    int hi = N - 1;
    int mid;

    while (lo <= hi) {
        mid = (lo + hi) / 2;
        if (A[mid] > x)
            hi = mid - 1;
        else if (A[mid] < x)
            lo = mid + 1;
        else
            return mid;
    }
    return -1;
}

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


int main() {
    ofstream outfile;
    outfile.open("random.txt");
    srand(time(NULL));
    for (int i = 0; i < SIZE; i++)
        outfile << rand() % RANGE << " ";
    outfile << endl;
    outfile.close();

    ifstream infile;
    infile.open("random.txt");

    cout << "Reading " << SIZE << " Inputs from the File..." << endl;
    for (long long i = 0; i < SIZE; i++)
        infile >> B[i];
    infile.close();

    long long Start, End;

    cout << "INSERTION SORT" << endl;
    cout << "--------------" << endl;
    for (long long i = 0; i < SIZE; i++)
        A[i] = B[i];
//    cout << "Unsorted Array: ";
//    display(A, SIZE);
//    cout << "Sorting..." << endl;
    Start = clock();
    insertionSort (A, SIZE);
    End = clock();
//    cout << "Sorted Array: ";
//    display (A, SIZE);
    cout << "Insertion Sort took " << fixed << setprecision(4) << (End - Start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl << endl << endl;


    cout << "BUBBLE SORT" << endl;
    cout << "-----------" << endl;
    for (long long i = 0; i < SIZE; i++)
        A[i] = B[i];
//    cout << "Unsorted Array: ";
//    display(A, SIZE);
//    cout << "Sorting..." << endl;
    Start = clock();
    bubbleSort (A, SIZE);
    End = clock();
//    cout << "Sorted Array: ";
//    display (A, SIZE);
    cout << "Bubble Sort took " << fixed << setprecision(4) << (End - Start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl << endl << endl;


    cout << "SELECTION SORT" << endl;
    cout << "--------------" << endl;
    for (long long i = 0; i < SIZE; i++)
        A[i] = B[i];
//    cout << "Unsorted Array: ";
//    display(A, SIZE);
//    cout << "Sorting..." << endl;
    Start = clock();
    selectionSort (A, SIZE);
    End = clock();
//    cout << "Sorted Array: ";
//    display (A, SIZE);
    cout << "Selection Sort took " << fixed << setprecision(4) << (End - Start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl << endl << endl;



    cout << "Enter the Value to Search: ";
    int x;
    cin >> x;


    cout << "SEQUENTIAL SEARCH" << endl;
    cout << "-----------------" << endl;
    cout << "Searching " << x << " in the Array...." << endl;
    Start = clock();
    int pos = sequentialSearch(A, SIZE, x);
    End = clock();
    if (pos >= 0)
        cout << x << " Found on Position: " << pos << endl;
    else
        cout << x << " Not Found" << endl;
    cout << "Sequential Search took " << fixed << setprecision(4) << (End - Start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl << endl << endl;


    cout << "BINARY SEARCH" << endl;
    cout << "-----------------" << endl;
    cout << "Searching " << x << " in the Array...." << endl;
    Start = clock();
    End = clock();
    pos = binarySearch (A, 0, SIZE - 1, x);
    if (pos >= 0)
        cout << x << " Found on Position: " << pos << endl;
    else
        cout << x << " Not Found" << endl;
    cout << "Binary Search took " << fixed << setprecision(4) << (End - Start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl << endl << endl;


    cout << "BINARY (Iterative) SEARCH" << endl;
    cout << "-----------------" << endl;
    cout << "Searching " << x << " in the Array...." << endl;
    Start = clock();
    End = clock();
    pos = binarySearchIterative (A, SIZE, x);
    if (pos >= 0)
        cout << x << " Found on Position: " << pos << endl;
    else
        cout << x << " Not Found" << endl;
    cout << "Binary Search (Iteratieve) took " << fixed << setprecision(4) << (End - Start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl << endl << endl;


    return 0;
}