Searching and Sorting Algorithms: A Comprehensive Guide

Overview of Searching Processes

• Definition of Searching: Searching is the algorithmic process of identifying a particular item within a collection of items or finding the position of a given value in a list of values.

• Decision Agency: Searching decides whether a designated "search key" is present or absent within the data.

• Scope of Application: Searching can be performed on both internal data structures and external data structures.

• Categorization of Techniques: To locate an element in an array, two primary methods are utilized:     1. Sequential Search     2. Binary Search

Sequential Search (Linear Search)

• Alternative Name: Also commonly referred to as Linear Search.

• Fundamental Mechanism: Sequential search is a basic and simple algorithm that begins at the start of a list and checks every element sequentially until a match is found.

• Comparison Logic: It compares the target element with every other element in the list.     * If the element matches, the algorithm returns the value's index.     * If no match is found after checking all elements, it returns $-1$.

• Operational Example: Searching for the element $25$     * The process moves step-by-step in a sequence.     * The search continues until the desired value is located or the list ends.

• Ideal Use Cases:     * Applied to unsorted or unordered lists.     * Best suited for lists containing a small number of elements.

• Sequential Search Implementation in C:

#include <stdio.h>
int main() {
  int num[50], target, count, i, flag = 0;
  printf("Enter the number of elements in array\n");
  scanf("%d", &count);
  printf("Enter % d integer(s)\n", count);
  for (i = 0; i < count; i++) {
    scanf("%d", &num[i]);
  }
  printf("Enter the number to search\n");
  scanf("%d", &target);
  for (i = 0; i < count; i++) {
    if (num[i] == target) /* if required element found */ {
      printf("%d is present at location %d.\n", target, i + 1);
      flag = 1;
      break;
    }
  }
  if (flag == 0) {
    printf("%d is not present in array.\n", target);
  }
}

Binary Search

• Prerequisite: Binary Search must be used on a sorted array to function correctly.

• Performance Metrics: It is a fast search algorithm characterized by a run-time complexity of $O(\log(n))$.

• Algorithmic Principle: Operates on the principle of Divide and Conquer.

• Methodology: The technique locates an element by comparing the target to the middlemost element of the collection.

• Suitability: Highly useful for processing large numbers of elements in an array.

• Logic Flow:     * Start with the middle element.     * If the middle element matches the target, return true.     * If the target is less than the middle element, move to the left half of the list.     * If the target is greater than the middle element, move to the right half of the list.     * Repeat process until the element is found or the search space is exhausted.

• Binary Search Implementation in C:

#include <stdio.h>
void main() {
  int num[10] = {6, 12, 18, 22, 31, 39, 55, 65, 74, 82};
  int target, mid;
  int start = 0, end = 9;
  printf("\nEnter your target value=");
  scanf("%d", &target);
  while (start <= end) {
    mid = (start + end) / 2;
    if (num[mid] == target) {
      printf("Element %d found at %d position", target, mid + 1);
      break;
    } else {
      if (num[mid] < target) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
  }
}

Introduction to Sorting

• Definition: Sorting refers to the arrangement of data into a specific format or order, most commonly numerical or lexicographical (alphabetical).

• Importance of Sorting:     * Optimization: Searching operations can be optimized to high levels if data is stored in a sorted manner.     * Readability: Representing data in sorted order makes it more readable for humans.

• Real-Life Scenarios:     * Telephone Directory: Numbers are sorted by name so that specific entries can be located easily.     * Dictionary: Words are stored alphabetically to facilitate easy word searching.

Selection Sort Algorithm

• Core Concept: In selection sort, the smallest value among the unsorted elements is selected in every pass and moved to its appropriate position.

• Nature: It is an in-place comparison algorithm and one of the simplest sorting methods.

• Logical Partitioning: The array is divided into two segments:     * Sorted Part: Stored on the left (initially empty).     * Unsorted Part: Stored on the right (initially contains the entire array).

• The Process: The first smallest element is found and placed at index 0. The second smallest is then found and placed at index 1. This continues until the entire array is sorted.

• Complexity Specifications:     * Worst-case Complexity: $O(n^2)$.     * Average-case Complexity: $O(n^2)$.     * Best-case Complexity: $O(n^2)$.     * Space Complexity: $O(1)$ (an extra variable is required for swapping).     * Stability: YES.

• Usage Criteria: Selection sort is preferred when:     * Dealing with small arrays.     * The cost of swapping values does not matter.     * It is mandatory to check all elements.

• Step-by-Step Example (Initial values: 12, 29, 8):     1. First Position: Entire array is scanned. $8$ is found as the smallest. Swap $12$ with $8$. Array becomes: $8, 29, 12$.     2. Second Position: Scan the rest (29, 12). $12$ is the second lowest. Swap $29$ with $12$. Array becomes: $8, 12, 29$.

• Selection Sort Implementation in C:

#include<stdio.h>
void main() {
  int arr[6] = {5, 9, 7, 12, 2};
  int i, j, k, temp;
  for (i = 0; i < 5; i++) {
    for (j = i + 1; j < 5; j++) {
      if (arr[i] > arr[j]) {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  for (k = 0; k < 5; k++) {
    printf("%d ", arr[k]);
  }
}

Bubble Sort Algorithm

• Mechanism: Bubble sort works by repeatedly swapping adjacent elements if they are not in the intended order.

• The Metaphor: Named "bubble sort" because the movement of elements resembles air bubbles rising to the surface of water; larger elements "bubble up" to the end of the array in each iteration.

• Efficiency: Primarily used as an educational tool. Performance is poor in real-world applications and unsuitable for large data sets.

• Complexity Specifications:     * Worst-case Time Complexity: $O(n^2)$.     * Average-case Time Complexity: $O(n^2)$.     * Best-case Time Complexity: $O(n)$ (specifically for optimized bubble sort when the array is already sorted).     * Space Complexity: $O(1)$ for standard; $O(2)$ for optimized bubble sort (requiring two extra variables).     * Stability: YES.

• Pseudo-Algorithm:     1. begin BubbleSort(arr)     2. for all array elements     3. if arr[i] > arr[i+1]     4. swap(arr[i], arr[i+1])     5. end if     6. end for     7. return arr     8. end BubbleSort

• Operational Example (Trace: 32, 13, 26, 35, 10):     * First Pass:         * Compare 32 and 13: (32 > 13) Swap is not required based on the text logic (Note: standard ascending sort would swap, but transcript text says "32 is greater than 13, so it is already sorted" implying a specific logic trace).         * Compare 32 and 26: 26 is smaller than 36 (likely typo for 32). Swapping required.         * Compare 32 and 35: 35 > 32. No swapping.         * Compare 35 and 10: 10 is smaller. Swapping required.     * Subsequent Passes: The process repeats for the second, third, and fourth passes until no further swaps are required.

Optimized Bubble Sort

• The Problem: Standard bubble sort makes comparisons even when the array is already sorted, increasing execution time.

• The Solution: Use an extra variable called swapped.     * swapped is set to true if a swap occurs.     * swapped is set to false at the start of each iteration.     * If after a full iteration swapped remains false, the array is sorted and the algorithm terminates.

• Optimized Algorithm Structure:     1. bubbleSort(array)     2. n = length(array)     3. repeat     4. swapped = false     5. for i = 1 to n - 1     6. if array[i - 1] > array[i], then     7. swap(array[i - 1], array[i])     8. swapped = true     9. end if     10. end for     11. n = n - 1     12. until not swapped     13. end bubbleSort

Bubble Sort Implementation in C

#include<stdio.h>
void main() {
  int arr[6] = {5, 9, 7, 12, 2, 67};
  int i, j, k, temp, xc = 0;
  int n = 6;
  for (i = 0; i < n - 1; i++) {
    for (j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  for (k = 0; k < 5; k++) {
    printf("%d ", arr[k]);
  }
}