Standard Algorithms: Search, Linear and Binary Search, Sorting, Bubblesort, Selection, and Insertion

Searching and sorting are among the most fundamental operations in software development. In this article, you’ll learn five essential standard algorithms: linear search, binary search, bubblesort, selection sort, and insertion sort. For each algorithm, I’ll explain how it works, its time complexity in Big-O notation, and provide a Python example.

Whether you’re preparing for an exam, pursuing a degree, or undertaking any IT training, searching and sorting will inevitably come up. Usually it’s just the basics—simple bubblesort implementations or basic array operations—but understanding these algorithms matters.

Learning the key algorithms will make your life easier. Time is money, and this is where the first dilemma in programming appears: when is an algorithm good, and when is it unusable?

The larger your dataset, the more important it is to choose the right approach. With small datasets, the difference between waiting 0.2 seconds or 0.5 seconds feels negligible. But with large datasets, that gap can stretch from seconds to minutes.

We measure algorithms by speed. The goal is always to find the fastest solution. We’ve written about this before, but since it’s relevant here, let me recap the essentials.

What do O(1), O(n), O(log n), and O(n²) mean?

Before we look at individual algorithms, you need to understand how we describe their speed using Big-O notation. It doesn’t tell you how many milliseconds an algorithm takes; rather, it describes how much the runtime grows as your data grows.

Here’s a quick overview of the main complexity classes:

O(1) – constant: Runtime stays the same regardless of data size. Accessing an array element by index is an example.
O(log n) – logarithmic: Runtime grows very slowly. Binary search halves the search space each step, which is why it’s O(log n).
O(n) – linear: Runtime grows in proportion to your data size. With 1,000 elements, you’ll need roughly twice as long as with 500 elements.
O(n²) – quadratic: Runtime grows very quickly. When you double the data, runtime increases about four times. Many simple sorting algorithms have this complexity.

Big-O notation always describes the worst case—the most unfavorable scenario. This helps you estimate the worst-case runtime your algorithm might face.

For a deeper explanation, check out Big-O Notation: Runtime Complexity and Efficiency O(1), O(n), O(log n) and the introduction to Complexity Analysis, Big-O, Search and Sorting Algorithms.

For the algorithms below, it’s enough to look at our summary and judge each as either “GOOD” or “NOT SO GOOD.”

Linear Search

Linear search moves through a list element by element until it finds the target or reaches the end. It works on both sorted and unsorted data.

Think of it like walking through a queue from the start to the end. You might get lucky and find what you need right away, or it could be the last element.

def lineare_suche(liste, ziel):
    for index, wert in enumerate(liste):
        if wert == ziel:
            return index
    return -1

Best Case: O(1) (target element is near the front)
Worst Case: O(n) (target element is at the end, or doesn’t exist)
Average Case: O(n)

Linear search is simple but slow on large datasets.

Binary Search

Binary search halves the search space with each step. It requires the list to be sorted first. Compared to linear search, it’s dramatically faster on large datasets.

def binaere_suche(liste, ziel):
    links = 0
    rechts = len(liste) - 1

    while links <= rechts:
        mitte = (links + rechts) // 2
        if liste[mitte] == ziel:
            return mitte
        if liste[mitte] < ziel:
            links = mitte + 1
        else:
            rechts = mitte - 1

    return -1

Best Case: O(1)
Worst Case: O(log n)
Average Case: O(log n)

With a million elements, binary search needs only about 20 comparisons in the worst case.

Compare that to linear search—see the difference?

Bubblesort

Bubblesort repeatedly compares adjacent elements and swaps them if they’re in the wrong order. Larger elements gradually bubble up toward the end.

This algorithm is popular in exams and introductory exercises. You should understand it and be able to implement it later.

def bubblesort(liste):
    n = len(liste)
    while True:
        vertauscht = False
        for i in range(n - 1):
            if liste[i] > liste[i + 1]:
                liste[i], liste[i + 1] = liste[i + 1], liste[i]
                vertauscht = True
        n -= 1
        if not vertauscht:
            break
    return liste

Best Case: O(n)
Worst Case: O(n²)
Average Case: O(n²)

Bubblesort is easy to understand but inefficient for large datasets.

Selection Sort

Selection sort finds the smallest element in the unsorted portion during each pass and moves it to the sorted portion.

def selection_sort(liste):
    n = len(liste)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if liste[j] < liste[min_index]:
                min_index = j
        liste[i], liste[min_index] = liste[min_index], liste[i]
    return liste

Best Case: O(n²)
Worst Case: O(n²)
Average Case: O(n²)

Selection sort is straightforward but always quadratic. It performs fewer swaps than bubblesort.

Insertion Sort

Insertion sort places each element into its correct position within the already-sorted portion. It’s like sorting cards in your hand during a card game.

def insertion_sort(liste):
    for i in range(1, len(liste)):
        aktuelles = liste[i]
        j = i - 1
        while j >= 0 and liste[j] > aktuelles:
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = aktuelles
    return liste

Best Case: O(n)
Worst Case: O(n²)
Average Case: O(n²)

Insertion sort is particularly efficient when the list is already nearly sorted.

Comparison of Search and Sorting Algorithms

Algorithm	Type	Best Case	Worst Case	Use Case
Linear Search	Search	O(1)	O(n)	Small unsorted datasets
Binary Search	Search	O(1)	O(log n)	Large sorted datasets
Bubblesort	Sorting	O(n)	O(n²)	Learning purposes only
Selection Sort	Sorting	O(n²)	O(n²)	Small datasets, minimizing swaps
Insertion Sort	Sorting	O(n)	O(n²)	Nearly sorted data, small lists

Which Algorithm to Use When?

For searching:

Use linear search for unsorted data.
Use binary search for sorted data.

For sorting:

Bubblesort is suitable only for learning.
Selection Sort is straightforward but slow.
Insertion Sort works well for small or nearly sorted datasets.
For large datasets, reach for Quicksort, Mergesort, or Heapsort instead.

Linear search, binary search, Bubblesort, Selection Sort, and Insertion Sort form the foundation for understanding algorithms and data structures. They’re simple, instructive, and demonstrate how Big-O describes runtime complexity. In production, larger datasets call for faster algorithms, but mastering these five standard algorithms is essential for any developer.

FAQ: Standard Algorithms, Searching, and Sorting

1. What is a standard algorithm?

A standard algorithm is a proven procedure for recurring problems like searching, sorting, or comparing. These algorithms form the backbone of algorithmic thinking in software development.

2. What is the difference between searching and sorting?

Searching means finding a specific element in a dataset. Sorting means arranging elements according to a defined order, such as ascending or alphabetically.

3. What is linear search?

Linear search walks through a list element by element until it finds the target element or reaches the end. It works on sorted and unsorted data and runs in O(n) time.

4. When should you use linear search?

Linear search makes sense when your dataset is small or when the data isn’t sorted. On tiny lists, it’s often faster than more complex algorithms because it carries no overhead.

5. What is binary search?

Binary search halves the search space with each step. It requires sorted data and runs in O(log n) time.

6. Why is binary search faster than linear search?

Binary search is faster because it halves the search space at each step. With a million elements, it needs only around 20 comparisons in the worst case, while linear search may need up to a million.

7. What prerequisite does binary search need?

Binary search requires sorted data. If the list isn’t sorted, you must sort it first or use linear search instead.

8. What is Bubblesort?

Bubblesort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they’re in the wrong order. It has a worst-case runtime of O(n²).

9. Why is Bubblesort rarely used in practice?

Bubblesort is rarely used in practice because its O(n²) runtime is painfully slow for large datasets. However, it’s an excellent learning tool for understanding how sorting algorithms work.

10. What is Selection Sort?

Selection Sort finds the smallest element in the unsorted portion on each pass and places it in the next position of the sorted portion. Its runtime is always O(n²).

11. What is Insertion Sort?

Insertion Sort inserts each element into its correct position within the already-sorted portion. It’s especially efficient when the list is nearly sorted and has a best-case runtime of O(n).

12. What is the best case for Insertion Sort?

The best case for Insertion Sort is O(n), which occurs when the list is already sorted. Each element is inserted once without requiring any shifts.

13. What does O(1) mean?

O(1) means constant time. The required time is independent of input size. Accessing an array element by index is a classic example.

14. What does O(n) mean?

O(n) means linear time. The required time grows proportionally with input size. Double the data, and the algorithm takes roughly twice as long.

15. What does O(log n) mean?

O(log n) means logarithmic time. The runtime grows very slowly because the problem space shrinks with each step. Binary search is the classic example.

16. What does O(n²) mean?

O(n²) means quadratic time. Runtime grows quadratically with input size. Double the data, and the algorithm needs roughly four times as long. Bubblesort and Selection Sort have this complexity.

17. What is the worst case?

The worst case describes an algorithm’s most unfavorable scenario. Big-O notation typically specifies the worst case so you can estimate maximum runtime.

Don’t worry—we have an article on binary search as well. After reviewing these FAQs, you already understand how it works.

18. What is the best case?

The best case describes an algorithm’s most favorable scenario. For instance, linear search finds an element immediately at the start of the list and runs in O(1) time.

19. What is a stable sorting algorithm?

A sorting algorithm is stable if elements with equal values preserve their original order. Insertion Sort is stable, Bubblesort can be stable, and Selection Sort is typically not stable.

20. What does in-place sorting mean?

A sorting algorithm operates in-place if it uses only constant extra space and performs the sort directly on the original list. Bubblesort, Selection Sort, and Insertion Sort all work in-place.

21. Which search algorithm is the fastest?

For sorted data, binary search with O(log n) is the fastest of the algorithms covered here. For unsorted data, linear search with O(n) remains the simplest choice.

22. Which sorting algorithm is the fastest?

Among the algorithms presented here, Insertion Sort is fastest in the best case at O(n). For large, random datasets, however, Quicksort, Mergesort, or Heapsort with O(n log n) are significantly better.

23. When should you use Bubblesort?

You should virtually never use Bubblesort in production code. It’s useful only for learning and understanding sorting algorithms.

24. Can you use binary search on linked lists?

Binary search isn’t efficient on linked lists because accessing the middle element takes O(n) time. It’s optimal for arrays and similar structures with direct index access.

25. Which sorting algorithms should every developer know?

Every developer should understand Bubblesort, Selection Sort, Insertion Sort, Quicksort, Mergesort, and Heapsort. The simple algorithms help you grasp Big-O and core principles, while the complex ones are essential for real-world work.

Täglicher Artikel