Skip to content

Instantly share code, notes, and snippets.

@hobelinm
Created March 9, 2014 06:29
Show Gist options
  • Save hobelinm/9443685 to your computer and use it in GitHub Desktop.
Save hobelinm/9443685 to your computer and use it in GitHub Desktop.
Simple implementation of Insertion Sort algorithm in C++
// Fill an array with random numbers
template <typename Comparable>
void fillRandom(vector<Comparable> &iArray, Comparable range)
{
srand((unsigned)time(0));
for(Comparable i = 0; i < iArray.size(); i++)
{
iArray[i] = rand() % range;
}
}
// Insertion Sort Forwards
template <typename Comparable>
void insertionSort(vector<Comparable> &a)
{
for(int unsorted = 1; unsorted < a.size(); unsorted++)
{
int loc;
Comparable nextItem = a[unsorted];
for(loc = unsorted; loc > 0 && nextItem < a[loc - 1]; loc--)
{
a[loc] = a[loc - 1];
}
a[loc] = nextItem;
}
}
// Insertion Sort Backwards
template <typename Comparable>
void insertionSortInverted(vector<Comparable> &a)
{
for(int unsorted = a.size() - 2; unsorted >= 0; unsorted--)
{
int loc;
Comparable nextItem = a[unsorted];
for(loc = unsorted; loc < a.size() - 1 && nextItem > a[loc + 1]; loc++)
{
a[loc] = a[loc + 1];
}
a[loc] = nextItem;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment