//
//	insertion sort algorithm
//
//	Described in Chapter 4 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//

# include <iostream.h>

void insertionSort (double v [ ], unsigned int n)
	// exchange the values in the vector v
	// so they appear in ascending order
{
	for (unsigned int i = 1; i < n; i++) {

		// move element v[i] into place
		double element = v[i];
		int j = i - 1;
		while (j >= 0 && element < v[j]) {
				// slide old value up
			v[j+1] = v[j];
				// decrement j
			j = j - 1;
			}
		// place element into position
		v[j+1] = element;
		}
}

void main () {
	double v[100];
	int i;
	for (i = 0; i < 100; i++)
		v[i] = rand();
	insertionSort (v, 100);
	for (i = 0; i < 100; i++)
		cout << v[i] << ' ';
	cout << "\n";
}