#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BOZO_SORT_ARRAY
#define CA_UWATERLOO_ALUMNI_DWHARDER_BOZO_SORT_ARRAY

namespace Sorting_algorithms {
	namespace Bozo_sort {
		class Array {
			public:
				template <typename Type>
				static void sort( Type *const array, int const n ) {
					sort( array, 0, n - 1 );
				}

				template <typename Type>
				static void sort( Type *const array, int const a, int const b ) {
					int range = b - a + 1;

					while ( is_unsorted( array, a, b ) ) {
						int i = a + ( rand() % range );
						int j = a + ( rand() % range );

						swap( array, i, j );
					}
				}

			private:
				template <typename Type>
				inline static int is_unsorted( Type *const array, int const a, int const b ) {
					for ( int i = a; i < b; ++i ) {
						if ( array[i] > array[i + 1] ) {
							return true;
						}
					}

					return false;
				}

				template <typename Type>
				inline static void swap( Type *const array, int i, int j ) {
					Type tmp = array[i];
					array[i] = array[j];
					array[j] = tmp;
				}
		};
	}
}

#endif