Elementary Sorting Algorithms in C++ (Selection, Insertion, Shell Sort)

Sorting is one of the most common tasks in programming. Whether you’re organizing user data, ranking scores, or optimizing performance, sorting plays a key role. In this blog, we’ll dive deep into elementary sorting algorithms that form the foundation for more advanced techniques.

We will cover:

• What sorting is and why it matters
• Selection Sort
• Insertion Sort
• Shell Sort
• Multiple code examples and explanations
• Use cases and best practices

---

What is Sorting?

Sorting is the process of arranging elements in a particular order — typically ascending or descending. For example, sorting the array:

[5, 2, 9, 1, 3]

in ascending order gives:

[1, 2, 3, 5, 9]

Efficient sorting is essential for:

• Faster searching
• Data analysis
• UI display (leaderboards, tables)
• Algorithm optimization (e.g., binary search)

---

1. Selection Sort

Concept:

Selection sort repeatedly selects the smallest (or largest) element from the unsorted portion and places it at the beginning.

Step-by-Step:

Let’s say you have:

[29, 10, 14, 37, 13]

• First pass: Find min → 10 → swap with 29
  → [10, 29, 14, 37, 13]
• Second pass: Min in remaining → 13 → swap with 29
  → [10, 13, 14, 37, 29]
• And so on…

Code:

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        if (minIdx != i)
            std::swap(arr[i], arr[minIdx]);
    }
}

Example:

int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);

Output:

[11, 12, 22, 25, 64]

Pros:

• Easy to understand
• No extra memory required

Cons:

• Time complexity: O(n²)
• Not stable (equal elements can be reordered)

---

2. Insertion Sort

Concept:

Think of sorting playing cards in your hand. You pick one card at a time and insert it into the correct position.

Step-by-Step:

For array:

[12, 11, 13, 5, 6]

• Start from 11: insert before 12 → [11, 12, 13, 5, 6]
• Insert 5 → [5, 11, 12, 13, 6]
• Insert 6 → [5, 6, 11, 12, 13]

Code:

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Example:

int arr[] = {9, 5, 1, 4, 3};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSort(arr, n);

Output:

[1, 3, 4, 5, 9]

Pros:

• Stable sort
• Efficient for small or nearly sorted arrays
• Online sorting (can sort while inputting)

Cons:

• Time complexity: O(n²) for large unsorted arrays
• Slower than advanced sorts

---

3. Shell Sort

Concept:

Shell sort improves insertion sort by comparing distant elements. It sorts elements that are far apart, reducing the number of shifts needed later.

It uses a gap sequence that gets smaller each time until it’s 1 (which is just insertion sort).

Step-by-Step:

Given:

[23, 12, 1, 8, 34, 54, 2, 3]

Start with gap = 4
→ Sort [23, 34], [12, 54], [1, 2], [8, 3]

Then reduce gap = 2
Then gap = 1 → insertion sort

Code:

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}

Example:

int arr[] = {45, 23, 53, 12, 64, 11, 33, 90};
int n = sizeof(arr)/sizeof(arr[0]);
shellSort(arr, n);

Output:

[11, 12, 23, 33, 45, 53, 64, 90]

Pros:

• Much faster than selection/insertion for medium-sized arrays
• Easy to implement
• In-place

Cons:

• Not stable
• Performance depends on the gap sequence

---

Summary: Comparison Table

Algorithm	Time (Best)	Time (Worst)	Space	Stable	Use Case
Selection Sort	O(n²)	O(n²)	O(1)	No	Simplicity > Performance
Insertion Sort	O(n)	O(n²)	O(1)	Yes	Small or nearly sorted arrays
Shell Sort	O(n log n)	O(n²)	O(1)	No	Medium arrays, better than basic

---

Practice Questions

1. Implement selection sort on the array {10, 7, 3, 1, 9} and show each pass.
2. What is the best-case scenario for insertion sort?
3. What’s the main advantage of shell sort over insertion sort?
4. Modify shell sort to print the array after each gap iteration.
5. Compare the number of swaps in selection sort vs. insertion sort on this input: {5, 3, 2, 4, 1}.

---

Final Thoughts

Elementary sorting algorithms may not be the fastest, but they are essential for understanding how sorting works. They help build the foundation for more complex sorts like Merge Sort and Quicksort.

If you’re just starting out with data structures and algorithms, practice these sorts by:

• Dry running them on paper
• Debugging your implementations step-by-step
• Timing them on small vs large inputs