Insertion Sort Algorithm in DSA C++ - Build from Scratch

Insertion Sort Algorithm

📖 Scenario: You have a small list of numbers that you want to arrange from smallest to largest. This is like organizing books on a shelf by their height, one by one.

🎯 Goal: Build a program that sorts a list of numbers using the insertion sort method, showing how the list becomes sorted step by step.

📋 What You'll Learn

Create an array called arr with the exact values: 8, 3, 5, 4, 6

Create an integer variable called n that stores the size of arr

Use a for loop with variable i starting from 1 to n - 1

Inside the loop, use a variable key to hold the current element arr[i]

Use a while loop with variable j to move elements greater than key one position ahead

Insert the key at the correct sorted position

Print the sorted array elements separated by spaces

💡 Why This Matters

🌍 Real World

Sorting small lists manually is useful in simple apps like organizing scores, names, or small datasets where quick sorting is needed without complex tools.

💼 Career

Understanding insertion sort helps in grasping basic sorting concepts, which are foundational for many programming and data processing jobs.

1

Create the initial array

Create an integer array called arr with the exact values: 8, 3, 5, 4, 6.

DSA C++

# Create the array arr with values 8, 3, 5, 4, 6
// Your code here

Hint

Use C++ array syntax: int arr[] = {values};

2

Set the size of the array

Create an integer variable called n that stores the size of the array arr using sizeof(arr) / sizeof(arr[0]).

DSA C++

int arr[] = {8, 3, 5, 4, 6};
// Create an integer variable n to store the size of arr
// Your code here

Hint

Use sizeof(arr) / sizeof(arr[0]) to get the number of elements.

3

Implement the insertion sort logic

Use a for loop with variable i from 1 to n - 1. Inside the loop, create an integer key equal to arr[i]. Then create an integer j equal to i - 1. Use a while loop to move elements greater than key one position ahead by setting arr[j + 1] = arr[j] and decrementing j. After the while loop, insert key at position j + 1.

DSA C++

int arr[] = {8, 3, 5, 4, 6};
int n = sizeof(arr) / sizeof(arr[0]);
// Write the insertion sort algorithm below
// Your code here

Hint

Follow the insertion sort steps: pick key, shift larger elements, insert key.

4

Print the sorted array

Use a for loop with variable i from 0 to n - 1 to print each element of arr separated by spaces using std::cout. End with a newline.

DSA C++

int arr[] = {8, 3, 5, 4, 6};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 1; i = 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}
// Print the sorted array elements separated by spaces
// Your code here

Hint

Use a loop to print each element followed by a space, then print a newline.