/*
 * SORTING & SEARCHING EXERCISES
 * Complete the functions as described in each exercise.
 * Test your solutions using the main() function provided.
 */

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

#define MAX 100

// Provided: Print array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Provided: Swap two integers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Provided: Copy array (for testing - so each sort gets fresh data)
void copyArray(int src[], int dest[], int n) {
    for (int i = 0; i < n; i++)
        dest[i] = src[i];
}

/* ============================================================
 * EXERCISE 1: Bubble Sort
 * Sort array in ascending order using bubble sort.
 * Parameters: arr - array to sort, n - size
 * Returns: void (sorts in-place)
 * Example: [64,34,25,12,22,11,90] -> [11,12,22,25,34,64,90]
 * ============================================================ */
void bubbleSort(int arr[], int n) {
    // Your code here
}

/* ============================================================
 * EXERCISE 2: Selection Sort
 * Sort by repeatedly finding minimum and placing it at beginning.
 * Parameters: arr - array to sort, n - size
 * Returns: void (sorts in-place)
 * Example: [64,25,12,22,11] -> [11,12,22,25,64]
 * ============================================================ */
void selectionSort(int arr[], int n) {
    // Your code here
}

/* ============================================================
 * EXERCISE 3: Insertion Sort
 * Sort by inserting each element into its correct position.
 * Parameters: arr - array to sort, n - size
 * Returns: void (sorts in-place)
 * Example: [12,11,13,5,6] -> [5,6,11,12,13]
 * ============================================================ */
void insertionSort(int arr[], int n) {
    // Your code here
}

/* ============================================================
 * EXERCISE 4: Merge Sort
 * Divide array in halves, sort each half, merge them.
 * Parameters: arr - array, left - start index, right - end index
 * Returns: void (sorts in-place)
 * You also need: void merge(int arr[], int l, int m, int r);
 * Example: [38,27,43,3,9,82,10] -> [3,9,10,27,38,43,82]
 * ============================================================ */
void merge(int arr[], int l, int m, int r) {
    // Your code here
}

void mergeSort(int arr[], int l, int r) {
    // Your code here
}

/* ============================================================
 * EXERCISE 5: Quick Sort
 * Pick a pivot, partition around it, recursively sort partitions.
 * Parameters: arr - array, low - start, high - end
 * Returns: void (sorts in-place)
 * You also need: int partition(int arr[], int low, int high);
 * Example: [10,7,8,9,1,5] -> [1,5,7,8,9,10]
 * ============================================================ */
int partition(int arr[], int low, int high) {
    // Your code here
    // Use last element as pivot
}

void quickSort(int arr[], int low, int high) {
    // Your code here
}

/* ============================================================
 * EXERCISE 6: Linear Search
 * Search for key in unsorted array.
 * Parameters: arr - array, n - size, key - value to find
 * Returns: index of key, or -1 if not found
 * Example: [5,3,8,1,9] key=8 -> 2
 * ============================================================ */
int linearSearch(int arr[], int n, int key) {
    // Your code here
}

/* ============================================================
 * EXERCISE 7: Binary Search (Iterative)
 * Search in sorted array by halving search space.
 * Parameters: arr - sorted array, n - size, key - value to find
 * Returns: index of key, or -1 if not found
 * Example: [2,5,8,12,16,23,38,56,72,91] key=23 -> 5
 * ============================================================ */
int binarySearch(int arr[], int n, int key) {
    // Your code here
}

/* ============================================================
 * EXERCISE 8: Binary Search (Recursive)
 * Recursive version of binary search.
 * Parameters: arr - sorted array, low - start, high - end, key
 * Returns: index of key, or -1 if not found
 * Example: Same as above
 * ============================================================ */
int binarySearchRec(int arr[], int low, int high, int key) {
    // Your code here
}

/* ============================================================
 * EXERCISE 9: Count Comparisons in Bubble Sort
 * Modified bubble sort that counts comparisons.
 * Parameters: arr - array, n - size
 * Returns: number of comparisons made
 * Example: [5,3,1,4,2] -> 10 comparisons (for n=5)
 * ============================================================ */
int bubbleSortCount(int arr[], int n) {
    // Your code here
}

/* ============================================================
 * EXERCISE 10: Sort Array of Strings Alphabetically
 * Sort strings using any sorting algorithm with strcmp.
 * Parameters: arr - array of strings, n - count
 * Returns: void (sorts in-place)
 * Example: ["banana","apple","cherry"] -> ["apple","banana","cherry"]
 * ============================================================ */
void sortStrings(char arr[][50], int n) {
    // Your code here
}

/* ============================================================
 * EXERCISE 11: Find Kth Smallest Element
 * Use partition (from Quick Sort) to find kth smallest.
 * Parameters: arr - array, n - size, k - position (1-based)
 * Returns: kth smallest element
 * Example: [7,10,4,3,20,15] k=3 -> 7
 * Hint: Partition and check pivot position. If pivot==k-1, done.
 *       If pivot > k-1, search left. Else search right.
 * ============================================================ */
int kthSmallest(int arr[], int n, int k) {
    // Your code here
}

/* ============================================================
 * EXERCISE 12: Counting Sort
 * Sort array where all values are in range 0-9.
 * Parameters: arr - array, n - size
 * Returns: void (sorts in-place)
 * Example: [4,2,2,8,3,3,1] -> [1,2,2,3,3,4,8]
 * Hint: Count occurrences of each value, then reconstruct.
 * ============================================================ */
void countingSort(int arr[], int n) {
    // Your code here
}


/* ============================================================
 * MAIN FUNCTION - Tests all exercises
 * ============================================================ */
int main() {
    int original[] = {64, 34, 25, 12, 22, 11, 90};
    int n = 7;
    int arr[MAX];

    printf("Original array: ");
    printArray(original, n);
    printf("\n");

    // Exercise 1: Bubble Sort
    printf("=== Exercise 1: Bubble Sort ===\n");
    copyArray(original, arr, n);
    bubbleSort(arr, n);
    printf("Sorted: ");
    printArray(arr, n);
    printf("Expected: 11 12 22 25 34 64 90\n\n");

    // Exercise 2: Selection Sort
    printf("=== Exercise 2: Selection Sort ===\n");
    copyArray(original, arr, n);
    selectionSort(arr, n);
    printf("Sorted: ");
    printArray(arr, n);
    printf("Expected: 11 12 22 25 34 64 90\n\n");

    // Exercise 3: Insertion Sort
    printf("=== Exercise 3: Insertion Sort ===\n");
    copyArray(original, arr, n);
    insertionSort(arr, n);
    printf("Sorted: ");
    printArray(arr, n);
    printf("Expected: 11 12 22 25 34 64 90\n\n");

    // Exercise 4: Merge Sort
    printf("=== Exercise 4: Merge Sort ===\n");
    copyArray(original, arr, n);
    mergeSort(arr, 0, n - 1);
    printf("Sorted: ");
    printArray(arr, n);
    printf("Expected: 11 12 22 25 34 64 90\n\n");

    // Exercise 5: Quick Sort
    printf("=== Exercise 5: Quick Sort ===\n");
    copyArray(original, arr, n);
    quickSort(arr, 0, n - 1);
    printf("Sorted: ");
    printArray(arr, n);
    printf("Expected: 11 12 22 25 34 64 90\n\n");

    // Exercise 6: Linear Search
    printf("=== Exercise 6: Linear Search ===\n");
    int searchArr[] = {5, 3, 8, 1, 9};
    printf("Search 8: index %d (expected: 2)\n", linearSearch(searchArr, 5, 8));
    printf("Search 7: index %d (expected: -1)\n\n", linearSearch(searchArr, 5, 7));

    // Exercise 7: Binary Search (Iterative)
    printf("=== Exercise 7: Binary Search (Iterative) ===\n");
    int sortedArr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    printf("Search 23: index %d (expected: 5)\n", binarySearch(sortedArr, 10, 23));
    printf("Search 100: index %d (expected: -1)\n\n", binarySearch(sortedArr, 10, 100));

    // Exercise 8: Binary Search (Recursive)
    printf("=== Exercise 8: Binary Search (Recursive) ===\n");
    printf("Search 56: index %d (expected: 7)\n", binarySearchRec(sortedArr, 0, 9, 56));
    printf("Search 1: index %d (expected: -1)\n\n", binarySearchRec(sortedArr, 0, 9, 1));

    // Exercise 9: Count Comparisons
    printf("=== Exercise 9: Bubble Sort Comparisons ===\n");
    int countArr[] = {5, 3, 1, 4, 2};
    int comps = bubbleSortCount(countArr, 5);
    printf("Comparisons: %d (expected: 10)\n\n", comps);

    // Exercise 10: Sort Strings
    printf("=== Exercise 10: Sort Strings ===\n");
    char strings[][50] = {"banana", "apple", "cherry", "date"};
    sortStrings(strings, 4);
    printf("Sorted: ");
    for (int i = 0; i < 4; i++) printf("%s ", strings[i]);
    printf("\nExpected: apple banana cherry date\n\n");

    // Exercise 11: Kth Smallest
    printf("=== Exercise 11: Kth Smallest ===\n");
    int kArr[] = {7, 10, 4, 3, 20, 15};
    printf("3rd smallest: %d (expected: 7)\n\n", kthSmallest(kArr, 6, 3));

    // Exercise 12: Counting Sort
    printf("=== Exercise 12: Counting Sort ===\n");
    int cArr[] = {4, 2, 2, 8, 3, 3, 1};
    countingSort(cArr, 7);
    printf("Sorted: ");
    printArray(cArr, 7);
    printf("Expected: 1 2 2 3 3 4 8\n");

    return 0;
}