Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Insertion Sort Algorithm (Insertion Sort) More...
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
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) |
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 () |
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
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:
\begin{bmatrix}4 &3 &2 &5 &1\end{bmatrix}
\begin{bmatrix}3 &4 &2 &5 &1\end{bmatrix}
\begin{bmatrix}2 &3 &4 &5 &1\end{bmatrix}
\begin{bmatrix}1 &2 &3 &4 &5\end{bmatrix}
|
static |
Create a random array objecthelper function to create a random array.
T | type of array |
arr | array to fill (must be pre-allocated) |
N | number of array elements |
int main | ( | void | ) |
Main Function
Running predefined tests to test algorithm
For user insteraction
void tests | ( | ) |
Test Cases to test algorithm