Moving onto the second sorting algorithm, Bogo Sort. Maybe I should have named this segment on sorting algorithms “10 Weeks of Sorting Algorithms” instead of 10 days. I do apologize for the delay for these posts, I have been quite busy the past week or so. Anyways, let’s get rolling with the Bogosort.

The Bogosort is a very ineffective sorting algorithm. This sorting algorithm is primarily used for educational purposes because it is very useful for developing and learning useful and realistic algorithms. According to Wikipedia, if the bogosort was used for sorting a deck of cars, it would consist of checking if the cards were in order and if not, the deck would be thrown into the air and then picked up in random. This process is repeated until the deck of cards were
sorted in order.

The pseudo code for this sorting algorithm is:

procedure BogoSort( A )
    while not Sorted( A )
        Randomize( A )

This algorithm for sorting is probabilistic in nature. If all elements are sorted by distinct, the expected number of comparisons in the average case is asymptotically equivalent to (e – 1)n!, and the expected number of swaps in the average case equals (n – 1)n!.

The best case for this algorithm occurs if the list given is already sorted; in this case the expected number of comparisons is n – 1, and no swaps at all carried out.

The actual implementation of this algorithm to sort a Vector is available below.

template<typename T>
void BogoSort(std::vector<T> *A)
{
	bool isSorted = false;

	while( !isSorted )
	{
		for( std::vector<T>::size_type i = 0; i < A->size(); ++i )
		{
			std::swap(A->at(rand() % (A->size() - 1)), A->at(i));
		}

		isSorted = true;
		for( std::vector<T>::size_type i = 0; i < A->size() - 1; ++i )
		{
			if( A->at(i) > A->at(i + 1) )
			{
				isSorted = false;
				break;
			}
		}
	}
}