Implementation of Insertion Sort Algorithm in CPP

Insertion sort is an algorithm used to sort a list of items in ascending, descending or any other custom order. In this article, we’ll implement a basic version of insertion sort algorithm in C++ programming language which can sort a given list of numbers in ascending order. We’ll then explore several practical variations, including sorting in descending order, using templates for implementing algorithm in generic fashion and handling custom objects with flexible sorting criteria.

Prerequisites:

Basic Insertion Sort Implementation

Let’s start with the standard iterative implementation of insertion sort. This version sorts an array in ascending order by repeatedly taking an element and inserting it into its correct position in the already sorted portion of the array.

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& vec) {
  // Handle empty or single-element vectors
  if (vec.size() <= 1) return;
  
  // Start from the second element
  for (int i = 1; i < vec.size(); i++) {
    int key = vec[i];  // Current element to be inserted
    int j = i - 1;     // Index of last element in sorted portion
    
    // Move elements greater than key ahead
    while (j >= 0 && vec[j] > key) {
      vec[j + 1] = vec[j];
      j--;
    }
    
    // Place key in its correct position
    vec[j + 1] = key;
  }
}

// Utility function to print vector
void printVector(const vector<int>& vec) {
  for (int num : vec)
    cout << num << " ";
  cout << endl;
}

int main() {
  // Test with a simple vector
  vector<int> vec = {64, 34, 25, 12, 22, 11, 90};
  
  cout << "Original vector: ";
  printVector(vec);
  
  insertionSort(vec);
  
  cout << "Sorted vector: ";
  printVector(vec);
  
  // Test with duplicates
  vector<int> vecWithDuplicates = {4, 3, 2, 4, 1, 2};
  
  cout << "\nOriginal vector with duplicates: ";
  printVector(vecWithDuplicates);
  
  insertionSort(vecWithDuplicates);
  
  cout << "Sorted vector with duplicates: ";
  printVector(vecWithDuplicates);
  
  return 0;
}

Output:

Original vector: 64 34 25 12 22 11 90 
Sorted vector: 11 12 22 25 34 64 90 

Original vector with duplicates: 4 3 2 4 1 2 
Sorted vector with duplicates: 1 2 2 3 4 4

Sorting in Descending Order

Sometimes we need our data in reverse order, from largest to smallest. This section shows how to modify the basic insertion sort algorithm to achieve descending order sorting. The main difference lies in changing the comparison operator from > to <, making it perfect for scenarios where you need data in reverse order, such as displaying top scores in a game or highest temperatures in weather data.

#include <iostream>
#include <vector>
using namespace std;

void insertionSortDesc(vector<int>& vec) {
  if (vec.size() <= 1) return;
  
  for (int i = 1; i < vec.size(); i++) {
    int key = vec[i];
    int j = i - 1;
    
    // Notice the < operator instead of >
    while (j >= 0 && vec[j] < key) {
      vec[j + 1] = vec[j];
      j--;
    }
    
    vec[j + 1] = key;
  }
}

int main() {
  vector<int> vec = {64, 34, 25, 12, 22, 11, 90};
  
  cout << "Original vector: ";
  printVector(vec);
  
  insertionSortDesc(vec);
  
  cout << "Sorted vector (descending): ";
  printVector(vec);
  
  return 0;
}

Output:

Original vector: 64 34 25 12 22 11 90 
Sorted vector (descending): 90 64 34 25 22 12 11

Template-based Implementation for Any Data Type

Templates in C++ provide a powerful way to write generic code that works with multiple data types. This implementation demonstrates how to create a versatile sorting function that can handle different data types like integers, floating-point numbers, or even custom objects. This approach follows the “write once, use many times” principle of efficient programming.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

template<typename T>
void insertionSort(vector<T>& vec) {
  if (vec.size() <= 1) return;
  
  for (int i = 1; i < vec.size(); i++) {
    T key = vec[i];
    int j = i - 1;
    
    while (j >= 0 && vec[j] > key) {
      vec[j + 1] = vec[j];
      j--;
    }
    
    vec[j + 1] = key;
  }
}

template<typename T>
void printVector(const vector<T>& vec) {
  for (const T& element : vec)
    cout << element << " ";
  cout << endl;
}

int main() {
  // Sort integers
  vector<int> intVec = {64, 34, 25, 12, 22};
  
  cout << "Original integer vector: ";
  printVector(intVec);
  
  insertionSort(intVec);
  
  cout << "Sorted integer vector: ";
  printVector(intVec);
  
  // Sort doubles
  vector<double> doubleVec = {3.14, 1.41, 2.71, 0.58};
  
  cout << "\nOriginal double vector: ";
  printVector(doubleVec);
  
  insertionSort(doubleVec);
  
  cout << "Sorted double vector: ";
  printVector(doubleVec);
  
  return 0;
}

Sorting Custom Objects

Real-world applications often require sorting complex objects rather than simple data types. This section shows how to sort custom objects like student records, employee data, or any other user-defined types. By implementing comparison operators, we can define custom sorting criteria based on any object attribute, making the sort function highly flexible and practical for business applications.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Student {
private:
  string name;
  int age;

public:
  Student(string n, int a) : name(n), age(a) {}
  
  string getName() const { return name; }
  int getAge() const { return age; }
  
  bool operator>(const Student& other) const {
    return age > other.age;  // Sort by age
  }
  
  friend ostream& operator<<(ostream& os, const Student& s) {
    os << s.name << " (" << s.age << ")";
    return os;
  }
};

int main() {
  vector<Student> students = {
    Student("Alice", 20),
    Student("Bob", 19),
    Student("Charlie", 21)
  };
  
  cout << "Original student vector:\n";
  for (const Student& student : students)
    cout << student << endl;
  
  insertionSort(students);
  
  cout << "\nSorted student vector (by age):\n";
  for (const Student& student : students)
    cout << student << endl;
  
  return 0;
}

Output:

Original student vector:
Alice (20)
Bob (19)
Charlie (21)

Sorted student vector (by age):
Bob (19)
Alice (20)
Charlie (21)

What’s Next?

Now that you’ve learned how to implement insertion sort in C++, you might want to explore: