Searching and Sorting Algorithms

Overview

Searching and sorting algorithms are fundamental in Computer Science. They help in organising data and retrieving information efficiently. Understanding when and how to apply these algorithms is crucial for optimising performance in various applications.

Why Do We Need Searching and Sorting Algorithms?

Searching Algorithms:

Locate specific data within a collection.

Examples: Finding a username in a database or looking up a word in a dictionary.

Sorting Algorithms:

Arrange data in a specific order (ascending or descending).

Examples: Sorting a list of student grades or arranging files by name or date.

Efficient searching and sorting improve data processing speeds, making programs more responsive and usable.

Pre-conditions for Specific Algorithms

Different algorithms have unique pre-conditions that must be met for them to function correctly or optimally.

Key Searching Algorithms

Linear Search

• Searches each element sequentially.
• Suitable for small or unsorted data sets.
• Complexity: O(n) for both best and worst cases.

METHOD LinearSearch(array, target)
    FOR i FROM 0 TO array.length - 1
        IF array[i] = target
            RETURN i
    ENDFOR
    RETURN -1  // Target not found

Binary Search

• Efficient search on sorted data by repeatedly dividing the search interval in half.
• Complexity: O(log n) for both best and worst cases.

METHOD BinarySearch(array, target)
    low ← 0
    high ← array.length - 1
    WHILE low <= high
        mid ← (low + high) DIV 2
        IF array[mid] = target
            RETURN mid
        ELSE IF array[mid] < target
            low ← mid + 1
        ELSE
            high ← mid - 1
    ENDWHILE
    RETURN -1  // Target not found

Key Sorting Algorithms

Bubble Sort

• Repeatedly swaps adjacent elements if they are in the wrong order.
• Simple but inefficient for large data sets.
• Complexity: Best case O(n) (already sorted), Worst case O(n²).

METHOD BubbleSort(array)
    FOR i FROM 0 TO array.length - 1
        FOR j FROM 0 TO array.length - i - 2
            IF array[j] > array[j + 1]
                SWAP array[j] AND array[j + 1]

Insertion Sort

• Builds the sorted list one item at a time.
• Works efficiently for small or nearly sorted data.
• Complexity: Best case O(n), Worst case O(n²).

METHOD InsertionSort(array)
    FOR i FROM 1 TO array.length - 1
        key ← array[i]
        j ← i - 1
        WHILE j >= 0 AND array[j] > key
            array[j + 1] ← array[j]
            j ← j - 1
        ENDWHILE
        array[j + 1] ← key

Merge Sort

• Divides the array into halves, sorts each half, and then merges them.
• Suitable for large data sets.
• Complexity: O(n log n) for all cases.

METHOD MergeSort(array)
    IF array.length > 1
        mid ← array.length DIV 2
        left ← array[0 TO mid - 1]
        right ← array[mid TO array.length - 1]
        CALL MergeSort(left)
        CALL MergeSort(right)
        CALL Merge(left, right, array)

Quick Sort

• Partitions the array around a pivot and recursively sorts the partitions.
• Complexity: Best and average case O(n log n), Worst case O(n²) (poor pivot).

METHOD QuickSort(array, low, high)
    IF low < high
        pivot ← Partition(array, low, high)
        CALL QuickSort(array, low, pivot - 1)
        CALL QuickSort(array, pivot + 1, high)

Note Summary