insertion_sort_recursive.cpp File Reference

Insertion Sort Algorithm. More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for insertion_sort_recursive.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)
	Helper function to create a random array.
static void	tests ()
	self test implementation
int	main ()
	Main function.

Detailed Description

Insertion Sort Algorithm.

Author

Dhanush S

Insertion sort is a simple sorting algorithm that builds the final sorted array one element 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:

• Easy to implement.
• Efficient for small data sets.
• More efficient than other O(n²) algorithms like selection sort or bubble sort.
• Stable: it does not change the relative order of elements with equal keys.

Insertion sort works similarly to how people sort playing cards in their hands. The algorithm iterates through the list and inserts each element into its correct position in the sorted portion of the array.

The time complexity of the algorithm is \(O(n^2)\), and in some cases, it can be \(O(n)\).

Example execution:

1. Start with the array [4, 3, 2, 5, 1].
2. Insert 3 in its correct position: [3, 4, 2, 5, 1].
3. Insert 2: [2, 3, 4, 5, 1].
4. Continue this until the array is sorted: [1, 2, 3, 4, 5].

Definition in file insertion_sort_recursive.cpp.

Function Documentation

create_random_array()

template<typename T >

static void create_random_array ( T * arr, int N )

static

Helper function to create a random array.

Template Parameters

T	Type of the array elements

Parameters

arr	Array to fill (must be pre-allocated)
N	Number of elements in the array

Definition at line 94 of file insertion_sort_recursive.cpp.

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

main()

int main

(

void

)

Main function.

Returns

0 on successful exit.

run self test implementations

Definition at line 149 of file insertion_sort_recursive.cpp.

           {
    tests(); 
    return 0;
}

tests()

static void tests ( )

static

self test implementation

Returns

void

Definition at line 105 of file insertion_sort_recursive.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;
}