ALGORITHM DESIGN

 LINEAR SEARCH 

#include <stdio.h>

void sequentialSearch(int arr[], int n, int key) {

    int found = 0; // Flag to indicate if the element is found

    for (int i = 0; i < n; i++) {

        if (arr[i] == key) {

            printf("Element %d found at index %d (Position %d)\n", key, i, i + 1);

            found = 1;

            break; // Exit the loop as the element is found

        }

    }

    if (!found) {

        printf("Element %d not found in the array.\n", key);

    }

}

int main() {

    int n, key;

    // Input: Size of the array

    printf("Enter the number of elements in the array: ");

    scanf("%d", &n);

    int arr[n]; // Declare an array of size n

    // Input: Elements of the array

    printf("Enter %d elements of the array:\n", n);

    for (int i = 0; i < n; i++) {

        scanf("%d", &arr[i]);

    }

    // Input: Key to search

    printf("Enter the element to search for: ");

    scanf("%d", &key);

    // Call the sequential search function

    sequentialSearch(arr, n, key);

    return 0;

}

Explanation of the Program

Inputs:

1. • The size of the array (n) is input by the user.
   • The elements of the array are entered by the user.
   • The element to be searched (key) is also input.

2. Core Logic:

   • The function sequentialSearch() iterates through the array using a for loop.
   • Each element is compared with the key.
   • If the key matches an element, its index and position are displayed, and the search ends.
   • If the loop completes without finding the key, a message indicates that the key is not present.

3. Output:

   • If the key is found, the program prints its index and position (1-based index).
   • If not found, it prints an appropriate message.

4. Features:

   • Handles both cases where the key is present and absent.
   • Works for arrays of any size (dynamic size based on user input).

---

Time Complexity Analysis

Best Case: $O(1)$

The element is found at the first position in the array.
Worst Case: $O(n)$

The element is at the last position or not present at all, requiring $n$ comparisons.
Average Case: $O(n/2)$, which simplifies to $O(n)$.

Space Complexity Analysis

Space Used by Variables:

• • Array: $O(n)$
  • Other variables (e.g., loop counters, key): $O(1)$

• Total Space Complexity: $O(n)$
  
   
  BINARY SEARCH
  
  
  #include <stdio.h>
  
  void binarySearch(int arr[], int n, int key) {
      int low = 0, high = n - 1, mid;
      int found = 0; // Flag to indicate if the element is found
  
      while (low <= high) {
          mid = low + (high - low) / 2; // Prevents overflow in large values
  
          if (arr[mid] == key) {
              printf("Element %d found at index %d (Position %d)\n", key, mid, mid + 1);
              found = 1;
              break;
          }
          else if (arr[mid] < key) {
              low = mid + 1; // Discard the left half
          }
          else {
              high = mid - 1; // Discard the right half
          }
      }
  
      if (!found) {
          printf("Element %d not found in the array.\n", key);
      }
  }
  
  int main() {
      int n, key;
  
      // Input: Size of the array
      printf("Enter the number of elements in the array: ");
      scanf("%d", &n);
  
      int arr[n]; // Declare an array of size n
  
      // Input: Elements of the array
      printf("Enter %d elements of the array in sorted order:\n", n);
      for (int i = 0; i < n; i++) {
          scanf("%d", &arr[i]);
      }
  
      // Input: Key to search
      printf("Enter the element to search for: ");
      scanf("%d", &key);
  
      // Call the binary search function
      binarySearch(arr, n, key);
  
      return 0;
  }
  Explanation of the Program
  Precondition:

1. • The array must be sorted for binary search to work.

2. Inputs:

   • n: The number of elements in the array.
   • The array elements, entered in sorted order.
   • key: The element to search for.

3. Core Logic:

   • Low and High Pointers: The array is divided into two halves using pointers low and high.
   • Mid Calculation: mid = low + (high - low) / 2 ensures no overflow.
   • Comparison:
     • If the key matches the middle element (arr[mid]), its index and position are printed.
     • If key is smaller than arr[mid], discard the right half (high = mid - 1).
     • If key is larger than arr[mid], discard the left half (low = mid + 1).
   • If the search ends and key is not found, print a not-found message.

4. Output:

   • The program prints the index (0-based) and position (1-based) of the key if found.
   • If the key is not found, it prints an appropriate message.

---

Time Complexity Analysis

Best Case: $O(1)$

The key is found at the middle index in the first iteration.
Worst Case: $O(\log n)$

The array is repeatedly divided in half until the key is found or the search ends.
Average Case: $O(\log n)$

The average number of comparisons follows the same logarithmic pattern.

Space Complexity Analysis

Iterative Approach:

• • The space used for variables (low, high, mid, etc.) is $O(1)$.
  • The array requires $O(n)$.

• Total Space Complexity: $O(n)$
  
  
  
  MERGE SORT
  
  
  #include <stdio.h>
  
  // Function to merge two subarrays
  void merge(int arr[], int left, int mid, int right) {
      int n1 = mid - left + 1; // Size of left subarray
      int n2 = right - mid;    // Size of right subarray
  
      // Temporary arrays to hold subarray elements
      int L[n1], R[n2];
  
      // Copy data to temporary arrays
      for (int i = 0; i < n1; i++) {
          L[i] = arr[left + i];
      }
      for (int j = 0; j < n2; j++) {
          R[j] = arr[mid + 1 + j];
      }
  
      // Merge the temporary arrays back into arr[left..right]
      int i = 0, j = 0, k = left;
  
      while (i < n1 && j < n2) {
          if (L[i] <= R[j]) {
              arr[k] = L[i];
              i++;
          } else {
              arr[k] = R[j];
              j++;
          }
          k++;
      }
  
      // Copy remaining elements of L[], if any
      while (i < n1) {
          arr[k] = L[i];
          i++;
          k++;
      }
  
      // Copy remaining elements of R[], if any
      while (j < n2) {
          arr[k] = R[j];
          j++;
          k++;
      }
  }
  
  // Function to perform merge sort
  void mergeSort(int arr[], int left, int right) {
      if (left < right) {
          int mid = left + (right - left) / 2;
  
          // Sort the left half
          mergeSort(arr, left, mid);
  
          // Sort the right half
          mergeSort(arr, mid + 1, right);
  
          // Merge the sorted halves
          merge(arr, left, mid, right);
      }
  }
  
  int main() {
      int n;
  
      // Input: Size of the array
      printf("Enter the number of elements in the array: ");
      scanf("%d", &n);
  
      int arr[n];
  
      // Input: Elements of the array
      printf("Enter %d elements of the array:\n", n);
      for (int i = 0; i < n; i++) {
          scanf("%d", &arr[i]);
      }
  
      // Perform merge sort
      mergeSort(arr, 0, n - 1);
  
      // Output: Sorted array
      printf("Sorted array:\n");
      for (int i = 0; i < n; i++) {
          printf("%d ", arr[i]);
      }
      printf("\n");
  
      return 0;
  }
  Explanation of the Program
  Divide and Conquer:

1. • The array is recursively divided into two halves until each subarray contains only one element (base case).
   • The mergeSort function performs this division.

2. Merging:

   • The merge function combines two sorted subarrays into a single sorted array.
   • Temporary arrays L and R store the elements of the two subarrays.

3. Sorting:

   • During the merging process, elements from L and R are compared and placed in the correct position in the original array.

4. Output:

   • After sorting, the program prints the elements of the sorted array.

---

Time Complexity Analysis

Divide Phase:

1. • The array is repeatedly divided into halves until there are $n$ single-element subarrays.
   • This requires $\log n$ divisions.

2. Merge Phase:

   • Merging two sorted arrays takes $O(n)$ operations at each level of recursion.
   • With $\log n$ levels of recursion, the merge phase requires $O(n \log n)$ operations.

3. Total Time Complexity:

   • Best Case: $O(n \log n)$
   • Worst Case: $O(n \log n)$
   • Average Case: $O(n \log n)$

---

Space Complexity Analysis

Temporary Arrays:

1. • Two temporary arrays L and R are created during the merge phase.
   • The combined size is proportional to the size of the array being merged.

2. Recursive Calls:

   • Each recursive call adds a stack frame, and the depth of recursion is $\log n$.

3. Total Space Complexity:

   • Auxiliary Space: $O(n)$ for temporary arrays.
   • Stack Space: $O(\log n)$ for recursion.
   • Total: $O(n + \log n)$, approximated to $O(n)$.

QUICK SORT 

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// Function to swap two numbers

void swap(int *a, int *b) {

    int temp = *a;

    *a = *b;

    *b = temp;

}

// Partition function for Quick Sort

int partition(int arr[], int low, int high) {

    int pivot = arr[high]; // Choosing the last element as pivot

    int i = low - 1;       // Index of smaller element

    for (int j = low; j < high; j++) {

        if (arr[j] <= pivot) {

            i++;

            swap(&arr[i], &arr[j]);

        }

    }

    // Swap the pivot element with the element at i+1

    swap(&arr[i + 1], &arr[high]);

    return (i + 1);

}

// Quick Sort function

void quickSort(int arr[], int low, int high) {

    if (low < high) {

        int pi = partition(arr, low, high);

        // Recursively sort elements before and after partition

        quickSort(arr, low, pi - 1);

        quickSort(arr, pi + 1, high);

    }

}

int main() {

    int n;

    // Input: Number of random numbers to generate

    printf("Enter the number of random numbers to sort: ");

    scanf("%d", &n);

    int arr[n];

    // Seed the random number generator

    srand(time(0));

    // Generate n random numbers

    printf("Generated random numbers:\n");

    for (int i = 0; i < n; i++) {

        arr[i] = rand() % 1000; // Generate numbers between 0 and 999

        printf("%d ", arr[i]);

    }

    printf("\n");

    // Perform Quick Sort

    quickSort(arr, 0, n - 1);

    // Output: Sorted array

    printf("Sorted array:\n");

    for (int i = 0; i < n; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

    return 0;

}

Explanation of the Program

Random Number Generation:

1. • The rand() function generates random integers between 0 and 999.
   • The numbers are stored in an array for sorting.

2. Partition Function:

   • Selects the last element as the pivot.
   • Rearranges elements so that all values smaller than the pivot appear before it and larger values appear after.

3. Recursive Quick Sort:

   • The array is recursively divided into two partitions:
     • One containing elements less than the pivot.
     • The other containing elements greater than the pivot.
   • Sorting continues until all partitions contain one or no elements.

4. Output:

   • Prints the generated random numbers and the sorted array.

---

Time Complexity Analysis

Best Case:

• Pivot divides array evenly at every step.
• The array is divided into two halves recursively, resulting in $\log n$ levels.
• Merging elements takes $O(n)$ at each level.
• Time Complexity: $O(n \log n)$.

Worst Case:

• Pivot is always the smallest or largest element.
• Results in $n - 1$ recursive calls, each handling one element.
• Time Complexity: $O(n^2)$.

Average Case:

• On average, the pivot divides the array approximately evenly.
• Time Complexity: $O(n \log n)$.

---

Space Complexity Analysis

In-Place Sorting:

1. • No additional array is used; sorting happens within the original array.
   • Space complexity for storage is $O(1)$.

2. Recursive Stack:

   • Recursion depth depends on the partitioning:
     • Best Case: $O(\log n)$ stack space.
     • Worst Case: $O(n)$ stack space.

3. Total Space Complexity:

   • Best Case: $O(\log n)$.
   • Worst Case: $O(n)$.