Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
insertion_sort.cpp File Reference

Insertion Sort Algorithm (Insertion Sort) More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
Include dependency graph for insertion_sort.cpp:

Namespaces

 sorting
 Sorting algorithms.
 

Functions

template<typename T >
void sorting::insertionSort (T *arr, int n)
 Insertion Sort Function. More...
 
template<typename T >
void sorting::insertionSort (std::vector< T > *arr)
 
template<typename T >
static void create_random_array (T *arr, int N)
 Create a random array objecthelper function to create a random array. More...
 
void tests ()
 
int main ()
 

Detailed Description

Insertion Sort Algorithm (Insertion Sort)

Insertion sort is a simple sorting algorithm that builds the final sorted array one at a time. It is much less efficient compared to other sorting algorithms like heap sort, merge sort or quick sort. However it has several advantages such as

  1. Easy to implement
  2. For small set of data it is quite efficient
  3. More efficient that other Quadratic complexity algorithms like Selection sort or bubble sort.
  4. It's stable that is it does not change the relative order of elements with equal keys
  5. Works on hand means it can sort the array or list as it receives.

It is based on the same idea that people use to sort the playing cards in their hands. the algorithms goes in the manner that we start iterating over the array of elements as soon as we find a unsorted element that is a misplaced element we place it at a sorted position.

Example execution steps:

  1. Suppose initially we have

    \begin{bmatrix}4 &3 &2 &5 &1\end{bmatrix}

  2. We start traversing from 4 till we reach 1 when we reach at 3 we find that it is misplaced so we take 3 and place it at a correct position thus the array will become

    \begin{bmatrix}3 &4 &2 &5 &1\end{bmatrix}

  3. In the next iteration we are at 2 we find that this is also misplaced so we place it at the correct sorted position thus the array in this iteration becomes

    \begin{bmatrix}2 &3 &4 &5 &1\end{bmatrix}

  4. We do not do anything with 5 and move on to the next iteration and select 1 which is misplaced and place it at correct position. Thus, we have

    \begin{bmatrix}1 &2 &3 &4 &5\end{bmatrix}

Function Documentation

◆ create_random_array()

template<typename T >
static void create_random_array ( T *  arr,
int  N 
)
static

Create a random array objecthelper function to create a random array.

Template Parameters
Ttype of array
Parameters
arrarray to fill (must be pre-allocated)
Nnumber of array elements
101  {
102  while (N--) {
103  double r = (std::rand() % 10000 - 5000) / 100.f;
104  arr[N] = static_cast<T>(r);
105  }
106 }
Here is the call graph for this function:

◆ main()

int main ( void  )

Main Function

Running predefined tests to test algorithm

For user insteraction

150  {
151  /// Running predefined tests to test algorithm
152  tests();
153 
154  /// For user insteraction
155  size_t n;
156  std::cout << "Enter the length of your array (0 to exit): ";
157  std::cin >> n;
158  if (n == 0) {
159  return 0;
160  }
161 
162  int *arr = new int[n];
163  std::cout << "Enter any " << n << " Numbers for Unsorted Array : ";
164 
165  for (int i = 0; i < n; i++) {
166  std::cin >> arr[i];
167  }
168 
169  sorting::insertionSort(arr, n);
170 
171  std::cout << "\nSorted Array : ";
172  for (int i = 0; i < n; i++) {
173  std::cout << arr[i] << " ";
174  }
175 
176  std::cout << std::endl;
177  delete[] arr;
178  return 0;
179 }
Here is the call graph for this function:

◆ tests()

void tests ( )

Test Cases to test algorithm

109  {
110  int arr1[10] = {78, 34, 35, 6, 34, 56, 3, 56, 2, 4};
111  std::cout << "Test 1... ";
112  sorting::insertionSort(arr1, 10);
113  assert(std::is_sorted(arr1, arr1 + 10));
114  std::cout << "passed" << std::endl;
115 
116  int arr2[5] = {5, -3, 7, -2, 1};
117  std::cout << "Test 2... ";
118  sorting::insertionSort(arr2, 5);
119  assert(std::is_sorted(arr2, arr2 + 5));
120  std::cout << "passed" << std::endl;
121 
122  float arr3[5] = {5.6, -3.1, -3.0, -2.1, 1.8};
123  std::cout << "Test 3... ";
124  sorting::insertionSort(arr3, 5);
125  assert(std::is_sorted(arr3, arr3 + 5));
126  std::cout << "passed" << std::endl;
127 
128  std::vector<float> arr4({5.6, -3.1, -3.0, -2.1, 1.8});
129  std::cout << "Test 4... ";
130  sorting::insertionSort(&arr4);
131  assert(std::is_sorted(std::begin(arr4), std::end(arr4)));
132  std::cout << "passed" << std::endl;
133 
134  int arr5[50];
135  std::cout << "Test 5... ";
136  create_random_array(arr5, 50);
137  sorting::insertionSort(arr5, 50);
138  assert(std::is_sorted(arr5, arr5 + 50));
139  std::cout << "passed" << std::endl;
140 
141  float arr6[50];
142  std::cout << "Test 6... ";
143  create_random_array(arr6, 50);
144  sorting::insertionSort(arr6, 50);
145  assert(std::is_sorted(arr6, arr6 + 50));
146  std::cout << "passed" << std::endl;
147 }
Here is the call graph for this function:
std::vector
STL class.
sorting::insertionSort
void insertionSort(T *arr, int n)
Insertion Sort Function.
Definition: insertion_sort.cpp:59
std::is_sorted
T is_sorted(T... args)
std::cout
create_random_array
static void create_random_array(T *arr, int N)
Create a random array objecthelper function to create a random array.
Definition: insertion_sort.cpp:101
std::rand
T rand(T... args)
std::endl
T endl(T... args)
std::begin
T begin(T... args)
tests
void tests()
Definition: insertion_sort.cpp:109
std::end
T end(T... args)
std::cin