Standard Algorithms Search & Sorting – Linear/Binary Search, BubbleSort, SelectionSort & InsertionSort

This post is a definition of terms for search and sorting algorithms – including exam questions and tags.

In a Nutshell

These standard algorithms serve the quick finding (search) or ordering (sorting) of data in arrays or lists. They form an exam-relevant foundation for algorithmic thinking.

Compact Technical Description

Linear and binary search are elementary methods for finding a value in data structures. Linear search checks each element sequentially, while binary search uses a sorted list and halves the search. Sorting algorithms such as Bubble Sort, Selection Sort, and Insertion Sort serve to arrange data in order. Bubble Sort compares neighboring elements multiple times, Selection Sort finds the smallest element and swaps it to the front, Insertion Sort builds a sorted list successively. These algorithms differ mainly in complexity and efficiency (Big-O).

Exam-Relevant Key Points

• Linear search traverses each element sequentially (O(n))
• Binary search iteratively halves the search range (O(log n), only with sorted data)
• Bubble Sort compares and swaps neighboring elements multiple times (O(n²))
• Selection Sort finds the minimum each time and swaps it to the front (O(n²))
• Insertion Sort sorts by successive insertion (O(n²), but good with nearly sorted data)
• Understanding the execution logic is exam-relevant (pseudocode, dry run)
• Stability, memory requirements, and complexity differ significantly

Core Components

1. Linear Search
2. Binary Search
3. Bubble Sort
4. Selection Sort
5. Insertion Sort
6. Runtime Complexity (Big-O)
7. Stability (order of equal elements)
8. Iterative execution with index management
9. Protection against index errors
10. Dry run 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 sorted into the sorted left part.

Advantages and Disadvantages

Advantages

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

Disadvantages

• Inefficient with large amounts of data (O(n²))
• Bubble and Selection Sort require many comparisons
• Binary search only applicable with sorted arrays

Typical Exam Questions (with Short Answer)

1. How does binary search work and when is it applicable? Iteratively halves the search range – only with sorted data.
2. Bubble Sort vs. Selection Sort? Bubble Sort compares neighbors, Selection Sort finds minimum per pass.
3. Why is Insertion Sort stable? Equal values retain their original order.
4. Bubble Sort runtime in worst case? O(n²), since each element is compared multiple times.
5. Stability in sorting algorithms means? Equal elements retain their order.
6. More efficient search with sorted data? Binary search with O(log n).
7. Is Insertion Sort efficient with nearly sorted data? Because only few comparisons and shifts are needed.
8. Check algorithm with dry run? By manually tracing the intermediate steps with concrete data.

Most Important Sources

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