Standard Algorithms: Search & Sorting – Linear Search, Binary Search, Bubble Sort, Selection Sort & Insertion Sort

This article is a conceptual overview of search and sorting algorithms, including exam-relevant questions and key terms.

In a Nutshell

These fundamental algorithms help you quickly locate values (search) or arrange data in order (sorting) within arrays or lists. They form an essential foundation for algorithmic thinking and appear regularly in technical interviews and exams.

Core Concepts

Linear and binary search are basic techniques for finding a value in a data structure. Linear search checks each element sequentially, while binary search exploits a sorted list by repeatedly halving the search space. Sorting algorithms like Bubble Sort, Selection Sort, and Insertion Sort organize data into order. Bubble Sort repeatedly compares and swaps adjacent elements; Selection Sort finds the minimum element in each pass and moves it to the front; Insertion Sort builds a sorted sequence incrementally. These algorithms differ primarily in their complexity and efficiency, measured using Big-O notation.

Key Points for Exams

• Linear search examines every element in sequence (O(n))
• Binary search iteratively halves the search range (O(log n), requires sorted data)
• Bubble Sort compares and swaps adjacent elements multiple times (O(n²))
• Selection Sort finds the minimum and swaps it to the front each iteration (O(n²))
• Insertion Sort organizes data by successively inserting elements (O(n²), but efficient for nearly sorted data)
• Understanding the step-by-step logic is critical for exams (pseudocode, trace execution)
• Stability, space complexity, and time complexity vary significantly between algorithms

Core Components

1. Linear search
2. Binary search
3. Bubble Sort
4. Selection Sort
5. Insertion Sort
6. Time complexity (Big-O)
7. Stability (preserving order of equal elements)
8. Iterative execution with index management
9. Boundary checks to prevent index errors
10. Trace execution for verification

Practical Example

// Example: Insertion Sort
function 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
        array[j + 1] = key

Explanation: The current element is inserted into the sorted portion on the left.

Strengths and Weaknesses

Strengths

• Simple to implement and understand
• Well-suited for small or nearly sorted datasets
• Stable algorithms (especially Insertion Sort)

Weaknesses

• Inefficient with large datasets (O(n²))
• Bubble Sort and Selection Sort require many comparisons
• Binary search only works on sorted arrays

Common Exam Questions (with Brief Answers)

1. How does binary search work and when should you use it? It iteratively halves the search range—only applicable to sorted data.

2. What’s the difference between Bubble Sort and Selection Sort? Bubble Sort compares adjacent pairs; Selection Sort finds the minimum in each pass.

3. Why is Insertion Sort stable? Equal values retain their original relative order.

4. What is Bubble Sort’s worst-case time complexity? O(n²), since every element is compared multiple times.

5. What does stability mean for a sorting algorithm? Equal elements preserve their relative order from the input.

6. Which search is more efficient on sorted data? Binary search with O(log n) complexity.

7. Why is Insertion Sort efficient for nearly sorted data? Fewer comparisons and shifts are required when most elements are already in order.

8. How do you verify an algorithm’s correctness? By manually tracing through the steps with concrete sample data.

Key Resources

1. https://visualgo.net/en/sorting
2. https://www.geeksforgeeks.org/sorting-algorithms
3. https://cs-field-guide.org.nz/en/chapters/algorithms