#include <iostream>

using namespace std;

/*
 * Insertion sort, small (left) to large (right)
 *
 * This much of the program is designed to perform a single pass of
 * insertion sort. Call it multiple times, in multiple ways before
 * continuing the coding.
 */

int main(){

    int data[10] = {3,5,1,2,8,4,3,1,7,0};

    iSort(data, 1, 10);    

    return 0;
}

/*
 * This should only do one pass of insertion sort. TEST IT thoroughly
 * before incorporating it into something larger.
 *
 * Why is this a good step in coding an algorithm?
 *
 * This version needs exactly one line of code added to make it an
 * efficient recursive function. Alternatively, you could place a call
 * to this whole fcn inside a loop, or add a loop inside the fcn.
 */
void iSort(int data[], int sizeOfSorted, int size){

    if (sizeOfSorted == size)
	return;
    
    int i = sizeOfSorted;
    while(data[i] < data[i-1] && i > 0){
	swap(data, i, i-1);
	i--;
    }
    printArray(data, size);

    return;
}