Experiment 13 – Search and Sort Algorithms

#include <stdio.h>

// Linear Search
int linearSearch(int arr[], int n, int key) {
    int i;
    for (i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;  // Return index if found
        }
    }
    return -1;  // Return -1 if not found
}

// Binary Search (requires sorted array)
int binarySearch(int arr[], int n, int key) {
    int left = 0, right = n - 1, mid;
    
    while (left <= right) {
        mid = (left + right) / 2;
        
        if (arr[mid] == key) {
            return mid;  // Found at index mid
        }
        
        if (key < arr[mid]) {
            right = mid - 1;  // Search left half
        } else {
            left = mid + 1;   // Search right half
        }
    }
    
    return -1;  // Not found
}

// Bubble Sort
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Selection Sort
void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    
    for (i = 0; i < n - 1; i++) {
        min_idx = i;  // Assume first element is minimum
        
        // Find minimum element in unsorted portion
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        // Swap minimum with first element of unsorted portion
        if (min_idx != i) {
            temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

// Function to display array
void displayArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[100], n, i, key, choice, index;
    
    printf("Enter number of elements: ");
    scanf("%d", &n);
    
    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    printf("\n1. Linear Search\n");
    printf("2. Binary Search (array must be sorted)\n");
    printf("3. Bubble Sort\n");
    printf("4. Selection Sort\n");
    printf("Enter your choice: ");
    scanf("%d", &choice);
    
    switch(choice) {
        case 1:
            printf("Enter element to search: ");
            scanf("%d", &key);
            index = linearSearch(arr, n, key);
            if (index != -1) {
                printf("Element %d found at index %d\n", key, index);
            } else {
                printf("Element %d not found in array.\n", key);
            }
            break;
            
        case 2:
            // Sort array first for binary search
            bubbleSort(arr, n);
            printf("Array sorted for binary search: ");
            displayArray(arr, n);
            
            printf("Enter element to search: ");
            scanf("%d", &key);
            index = binarySearch(arr, n, key);
            if (index != -1) {
                printf("Element %d found at index %d\n", key, index);
            } else {
                printf("Element %d not found in array.\n", key);
            }
            break;
            
        case 3:
            printf("Original array: ");
            displayArray(arr, n);
            bubbleSort(arr, n);
            printf("Sorted array (Bubble Sort): ");
            displayArray(arr, n);
            break;
            
        case 4:
            printf("Original array: ");
            displayArray(arr, n);
            selectionSort(arr, n);
            printf("Sorted array (Selection Sort): ");
            displayArray(arr, n);
            break;
            
        default:
            printf("Invalid choice!\n");
    }
    
    return 0;
}