Bubble Sort, Selection Sort, and Insertion Sort

These three simple sorting algorithms all have quadratic worst-case time, but they organize work differently. Bubble sort swaps adjacent out-of-order values, selection sort chooses the smallest remaining value, and insertion sort inserts each next value into a sorted prefix. The program provides three separate implementations and gives each a copy of the same input so their behavior can be compared fairly.

Prerequisites: Introduction to Sorting; nested loops; vectors.

Build the idea

1. 1. Bubble the largest remaining item rightward

   In a left-to-right pass, compare neighbors and swap only when the left value is larger. The largest item in the scanned prefix keeps moving right, so after a full pass the largest remaining value is fixed at the end. Shrink the next pass’s end. A changed flag stops on an already sorted pass, giving linear best-case time. Strict comparisons preserve equal-key order.

2. 2. Select the smallest remaining item

   At position i, scan the entire suffix for its minimum and swap that value into i. The prefix becomes sorted one position at a time. For [3,1,2], choose 1 to get [1,3,2], then choose 2 to get [1,2,3]. It still performs quadratic comparisons even on sorted input, but only O(n) swaps. A distant swap can reorder equivalent records, so this version is not stable.

3. 3. Insert into a sorted prefix

   Before iteration i, positions 0..i−1 are sorted. Save a[i] in value, shift larger prefix elements one position right, then place value into the gap. For [3,1,2], inserting 1 gives [1,3,2], then inserting 2 gives [1,2,3]. Check j>0 BEFORE reading a[j−1]. Shifting only strictly larger values retains stability.

4. 4. Compare intermediate passes

   Bubble’s first pass on [3,1,2] does [1,3,2] then [1,2,3], fixing 3 at the end. Selection fixes 1 at the front; insertion sorts the first two. Their final arrays agree, but the invariants describe different fixed regions. A correctness argument should match that invariant rather than assuming any repeated swapping must sort.

5. 5. Relate cost to input structure

   Bubble and insertion can finish in O(n) on already sorted input; selection cannot avoid its full suffix searches. Reverse-sorted input makes insertion shift about n(n−1)/2 values. Insertion is useful for short or nearly sorted ranges, and appears inside hybrid sorts. None is a suitable general-purpose replacement for O(n log n) library sorting on large arbitrary arrays.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
void bubble(std::vector<int>&a){
    for(int end=(int)a.size()-1;end>0;--end){
        bool changed=false;
        for(int j=0;j<end;++j){
            if(a[j]>a[j+1]){
                std::swap(a[j],a[j+1]);
                changed=true;
            }
        }
        if(!changed){
            break;
        }
    }
}
void selection(std::vector<int>&a){
    for(int i=0;i<(int)a.size();++i){
        int best=i;
        for(int j=i+1;j<(int)a.size();++j){
            if(a[j]<a[best]){
                best=j;
            }
        }
        std::swap(a[i],a[best]);
    }
}
void insertion(std::vector<int>&a){
    for(int i=1;i<(int)a.size();++i){
        int value=a[i],j=i;
        while(j>0&&a[j-1]>value){
            a[j]=a[j-1];
            --j;
        }
        a[j]=value;
    }
}
void print(const std::vector<int>&a){
    for(int i=0;i<(int)a.size();++i){
        std::cout<<a[i]<<(i+1==(int)a.size()?'\n':' ');
    }
    if(a.empty()){
        std::cout<<'\n';
    }
}
int main(){
    int n;
    std::cin>>n;
    std::vector<int>original(n);
    for(int&x:original){
        std::cin>>x;
    }
    auto a=original,b=original,c=original; // Independent input for each algorithm.
    bubble(a);
    selection(b);
    insertion(c);
    print(a);
    print(b);
    print(c);
}

Complexity analysis

Each algorithm has O(n²) worst-case time and O(1) auxiliary space when operating on its array. Optimized bubble and insertion have O(n) best time; selection has Θ(n²) comparisons in every case. The complete comparison program stores four vectors, so O(n) total/extra storage, and has O(n²) worst-case total time.

Example input and output

Read n (0..2000) then n int values. Print three ascending lines, produced independently by bubble, selection and insertion respectively. Empty arrays produce three blank lines.

Input

3
3 1 2

Output

1 2 3
1 2 3
1 2 3

The three algorithms reach the same ordering through different fixed-prefix or fixed-suffix invariants.

Practical applications

Use these implementations for learning loop invariants and as small-input references. Insertion is practical for small/nearly sorted runs; selection can help when minimizing swaps matters more than comparisons. Use std::sort, merge sort or another suitable method for larger general inputs.

Check your understanding

Which taught algorithm always scans all remaining suffixes even on sorted input?

Put it into practice

Count comparisons and moves for each algorithm on sorted and reverse-sorted arrays.