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

using namespace std;


void insertionSort(vector<int>& numbers){

	typedef vector<int>::iterator iterator;		// 'typedef' allows you to save a large datatype name as another.
												// Therefore, 'iterator' = 'vector<int>::iterator'

	for(iterator I = numbers.begin()+1; I != numbers.end(); I++){	// The iteration through the memory addresses of each element of number start with the number after the first, since the
																	// first element is considered sorted

		iterator check = I;	// Initializing the check iterator's location to the current I iteration memory location

		while( (check != numbers.begin()) && (*check < *(check-1)) ){	// While the current value doesn't equal the beginning location of the vector, numbers, and the value being checked is less than the value to the left of it.

			swap(*check, *(check - 1));	// Swap the check value with the value before it.

			check = check - 1;	// We now want to change the value we will now check to the one before the current, in the sorted list.

		}

	}

}


int main(){

	vector<int> a;		// Vector a is <6, 10, 3, 100, -2, 5>
	a.push_back(6);
	a.push_back(10);
	a.push_back(3);
	a.push_back(100);
	a.push_back(-2);
	a.push_back(5);

	insertionSort(a);	// Sorting vector a with insertionSort function

	for(vector<int>::iterator I = a.begin(); I != a.end(); I++){	// Displays the now sorted vector.
		cout << *I << ' ';
	}

	cout << '\n';

	return 0;
}