#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_BOGO_SORT_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_BOGO_SORT_BASIC

namespace Sorting_algorithms {
	namespace Bogo_sort {
		class Basic {
			public:
				template <typename Type>
				static void sort( Type *array, int n ) {
					while ( is_unsorted( array, n ) ) {
						for ( int i = 0; i < n; ++i ) {
							int j = rand() % n;
							swap( array, i, j );
						}
					}
				}

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

					return false;
				}

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

#endif