Sort

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

int n;

void swap(int *p, int *q) {
    int temp = *p;
    *p = *q;
    *q = temp;
}

void display(int arr[]) {
    printf("\n[");
    for (int i = 0; i < n - 1; i++) {
        printf("%d, ", arr[i]);
    }
    printf("%d]\n", arr[n - 1]);
}

void enterArray(int arr[]) {
    printf("Enter %d elements:", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

}

void bubbleSort() {
    printf("Enter size of the array:");
    scanf("%d", &n);
    int arr[n];
    enterArray(arr);
    printf("Array Before Sorting:");
    display(arr);
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
        }
    }
    printf("Array After Sorting:");
    display(arr);
}

void selectionSort() {
    printf("Enter size of the array:");
    scanf("%d", &n);
    int arr[n];
    enterArray(arr);
    printf("Array Before Sorting:");
    display(arr);
    for (int i = 0; i < n - 1; ++i) {
        int min = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min])
                min = j;
        }
        if (arr[i] != arr[min])
            swap(&arr[i], &arr[min]);
    }
    printf("Array After Sorting:");
    display(arr);
}

void insertionSort() {
    printf("Enter size of the array:");
    scanf("%d", &n);
    int arr[n];
    enterArray(arr);
    printf("Array Before Sorting:");
    display(arr);
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (key < arr[j] && j >= 0) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
    printf("Array After Sorting:");
    display(arr);
}

int partition(int arr[], int leftEnd, int rightEnd) {
    int left = leftEnd;
    int right = rightEnd;
    int pivot = arr[left];
    while (left < right) {
        while (left < rightEnd && arr[left] <= pivot)
            left++;
        while (right > leftEnd && arr[right] > pivot)
            right--;
        if (left < right)
            swap(&arr[left], &arr[right]);
        else
            swap(&arr[leftEnd], &arr[right]);
    }
    return right;
}

void quickSort(int arr[], int leftEnd, int rightEnd) {
    if (leftEnd > rightEnd)
        return;
    else {
        int p = partition(arr, leftEnd, rightEnd);
        quickSort(arr, leftEnd, p - 1);
        quickSort(arr, p + 1, rightEnd);
    }
}

void merge(int arr[], int left, int mid, int right) {
    int i = left, temp[n];
    int j = mid + 1;
    int k = left;
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            temp[k] = arr[i];
            i++;
            k++;
        } else {
            temp[k] = arr[j];
            j++;
            k++;
        }
    }
    while (i <= mid) {
        temp[k] = arr[i];
        i++;
        k++;
    }
    while (j <= right) {
        temp[k] = arr[j];
        j++;
        k++;
    }
    i = left;
    while (i <= right) {
        arr[i] = temp[i];
        i++;
    }
}

void mergeSort(int arr[], int left, int right) {
    int mid = (left + right) / 2;
    if (left < right) {
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void createHeap(int arr[], int N) {
    for (int i = 1; i <= N; i++) {
        int j = i;
        while ((j - 1) / 2 >= 0 && arr[j] > arr[(j - 1) / 2]) {
            swap(&arr[j], &arr[(j - 1) / 2]);
            j = (j - 1) / 2;
        }
    }
}

void removeMax(int arr[], int N) {
    swap(&arr[N], &arr[0]);
}

void rebuildHeap(int arr[], int N) {
    if (N == 0)
        return;
    int j = 0, flag = 1, child;
    while (flag == 1) {
        int rchild = 2 * j + 2;
        int lchild = 2 * j + 1;
        if (rchild <= N) {
            if (arr[rchild] > arr[lchild])
                child = rchild;
            else
                child = lchild;
        } else if (lchild <= N)
            child = lchild;
        else
            flag = 0;
        if (arr[child] > arr[j]) {
            swap(&arr[child], &arr[j]);
            j = child;
        } else
            flag = 0;
    }
}

void heapSort(int arr[], int N) {
    createHeap(arr, N - 1);
    for (int i = N - 1; i >= 1; i--) {
        removeMax(arr, i);
        rebuildHeap(arr, i - 1);
    }
}

int main() {
    int arg;
    while (1) {
        printf("\n******************");
        printf("\nEnter your choice:\n1. Bubble Sort\n2. Selection Sort\n3. Insertion Sort\n4. Quick Sort\n5. Merge Sort\n6. Heap Sort\n0. Exit");
        printf("\n******************\n");
        scanf("%d", &arg);
        switch (arg) {
            case 1:
                bubbleSort();
                break;
            case 2:
                selectionSort();
                break;
            case 3:
                insertionSort();
                break;
            case 4: {
                printf("Enter size of the array:");
                scanf("%d", &n);
                int arr[n];
                enterArray(arr);
                printf("Array Before Sorting:");
                display(arr);
                quickSort(arr, 0, n - 1);
                printf("Array After Sorting:");
                display(arr);
                break;
            }
            case 5: {
                printf("Enter size of the array:");
                scanf("%d", &n);
                int arr[n];
                enterArray(arr);
                printf("Array Before Sorting:");
                display(arr);
                mergeSort(arr, 0, n - 1);
                printf("Array After Sorting:");
                display(arr);
                break;
            }
            case 6: {
                printf("Enter size of the array:");
                scanf("%d", &n);
                int arr[n];
                enterArray(arr);
                printf("Array Before Sorting:");
                display(arr);
                heapSort(arr, n);
                printf("Array After Sorting:");
                display(arr);
                break;
            }

            case 0:
                exit(0);
            default:
                printf("Invalid Argument!");
                break;
        }
    }
}