main.cpp

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>


void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

int maximum(int *array, int size){

    int curr = 0;
    int max = 0;

    for (curr = 0; curr < size; curr++) {
        if (array[curr] > max) {
            max = array[curr];
        }
    }

    return max;
}

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

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

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++) {
        L[i] = arr[l + i];
        }
    for (j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j];
    }

    i = 0;
    j = 0;
    k = l;

    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void merge_sort(int *a, int start, int finish) {
    if (start < finish) {
        int mid = (start + finish) / 2;
        merge_sort(a, start, mid);
        merge_sort(a, mid + 1, finish);
        merge(a, start, mid, finish);
    }

}

void bubble_sort(int *a, int n) {
    int flag;
    for (int i = 0; i < n; i++) {
        flag = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(&a[j], &a[j + 1]);
                flag = 1;
            }
        }
        if (flag == 0) {
            break;
        }
    }
}

void selection_sort(int *a, int n) {
    int maxj = 0;
    for (int i = 0; i < n; i++) {
        maxj = 0;
        for (int j = 0; j < n - i; j++) {
            if (a[j] > a[maxj]) {
                maxj = j;
            }
            swap(&a[n - i - 1], &a[maxj]);
        }
    }
}

void insertion_sort(int *a, int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = a[i];
        j = i - 1;

        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j = j - 1;
        }
        a[j + 1] = key;
    }
}



void count_sort(int *a, int n, int max) {
    int i, k, j;
    int count[max];

    for (i = 0; i < max; i++) {
        count[i] = 0;
    }
    for (i = 0; i < n; i++) {
        count[a[i]]++;
    }

    k = 0;

    for (i = 0; i < max; i++) {
        for (j = 0; j <= count[i]; i++) {
            a[k] = i;
            k++;
        }
    }
}

int binary_search(int *a, int n, int k) {
    int i, start = 0, finish = n - 1;
    while (start <= finish) {
        i = (start + finish) / 2;
        if (a[i] == k) {
            return i;
        } else {
            if (a[i] > k) {
                finish = i - 1;
            } else {
                start = i + 1;
            }
        }
    }
    return -1;
}

int linear_search( int *a, int n, int k) {
    for (int i = 0; i < n; i++) {
        if (a[i] == k) {
            return i;
        }
    }
    return -1;
}

int main() {
    int choice;
    do {
        int n;
        int option;
        int target;
        printf("Please select your option: \n");
        printf("1. Bubble sort \n");
        printf("2. Selection sort \n");
        printf("3. Insertion sort \n");
        printf("4. Counting sort \n");
        printf("5. Merge sort \n");
        printf("6. Quick sort \n");
        printf("7. Binary search \n");
        printf("8. Linear search \n");
        printf("9. Quit the program \n");
        scanf("%d", &choice);
        if (choice == 9) {
            break;
        }
        printf("Enter the length of an array: ");
        scanf("%d", &n);
        int *a = (int*)malloc(sizeof(int) * n);
        printf("Choose if you want to generate a random array or enter your own. [1/2]");
        scanf("%d", &option);
        if (option == 1) {
            for (int i = 0; i < n; i++) {
                a[i] = rand() % 500;
            }
        }
        else {
            for (int i = 0; i < n; i++) {
                scanf("%d", &a[i]);
            }
        }
        clock_t begin = clock();
        switch (choice) {
            case 1:
                bubble_sort(a, n);
                break;
            case 2:
                selection_sort(a, n);
                break;
            case 3:
                insertion_sort(a, n);
                break;
            case 4: {
                int max = maximum(a, n);
                count_sort(a, n, max);
                break;
                }
            case 5:
                merge_sort(a, 0, n - 1);
                break;
            case 6:
                quick_sort(a, 0, n-1);
                break;
            case 7: {
                printf("Please enter your target value: \n");
                scanf("%d", &target);
                quick_sort(a, 0, n - 1);
                binary_search(a, n, target);
            }
            case 8: {
                printf("Please enter your target value: \n");
                scanf("%d", &target);
                linear_search(a, n, target);
            }
        }
        clock_t end = clock();
        double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

        printf("Array: \n");
        if (n < 20) {
            for (int i = 0; i < n; i++) {
                printf("%i \n", a[i]);
            }
        }
        printf("Execution time: %f sec \n", time_spent);

    } while (choice != 0);
    return 0;

}