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:

Go to the source code of this file.

Namespaces
namespace	sorting
	for working with vectors

Functions
template<typename T >
void	sorting::insertionSort (T *arr, int n)
	Insertion Sort Function.
template<typename T >
void	sorting::insertionSort (std::vector< T > *arr)
	Insertion Sort for a vector.
template<typename T >
static void	create_random_array (T *arr, int N)
	Create a random array objecthelper function to create a random array.
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}

Definition in file insertion_sort.cpp.

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

T	type of array

Parameters

arr	array to fill (must be pre-allocated)
N	number of array elements

Definition at line 101 of file insertion_sort.cpp.

                                               {
    while (N--) {
        double r = (std::rand() % 10000 - 5000) / 100.f;
        arr[N] = static_cast<T>(r);
    }
}

main()

int main

(

void

)

Main Function

Running predefined tests to test algorithm

For user insteraction

Definition at line 150 of file insertion_sort.cpp.

           {
    tests();
 
    size_t n;
    std::cout << "Enter the length of your array (0 to exit): ";
    std::cin >> n;
    if (n == 0) {
        return 0;
    }
 
    int *arr = new int[n];
    std::cout << "Enter any " << n << " Numbers for Unsorted Array : ";
 
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }
 
    sorting::insertionSort(arr, n);
 
    std::cout << "\nSorted Array : ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
 
    std::cout << std::endl;
    delete[] arr;
    return 0;
}

tests()

void tests

(

)

Test Cases to test algorithm

Definition at line 109 of file insertion_sort.cpp.

             {
    int arr1[10] = {78, 34, 35, 6, 34, 56, 3, 56, 2, 4};
    std::cout << "Test 1... ";
    sorting::insertionSort(arr1, 10);
    assert(std::is_sorted(arr1, arr1 + 10));
    std::cout << "passed" << std::endl;
 
    int arr2[5] = {5, -3, 7, -2, 1};
    std::cout << "Test 2... ";
    sorting::insertionSort(arr2, 5);
    assert(std::is_sorted(arr2, arr2 + 5));
    std::cout << "passed" << std::endl;
 
    float arr3[5] = {5.6, -3.1, -3.0, -2.1, 1.8};
    std::cout << "Test 3... ";
    sorting::insertionSort(arr3, 5);
    assert(std::is_sorted(arr3, arr3 + 5));
    std::cout << "passed" << std::endl;
 
    std::vector<float> arr4({5.6, -3.1, -3.0, -2.1, 1.8});
    std::cout << "Test 4... ";
    sorting::insertionSort(&arr4);
    assert(std::is_sorted(std::begin(arr4), std::end(arr4)));
    std::cout << "passed" << std::endl;
 
    int arr5[50];
    std::cout << "Test 5... ";
    create_random_array(arr5, 50);
    sorting::insertionSort(arr5, 50);
    assert(std::is_sorted(arr5, arr5 + 50));
    std::cout << "passed" << std::endl;
 
    float arr6[50];
    std::cout << "Test 6... ";
    create_random_array(arr6, 50);
    sorting::insertionSort(arr6, 50);
    assert(std::is_sorted(arr6, arr6 + 50));
    std::cout << "passed" << std::endl;
}