Bubble sort (C Sharp)

From LiteratePrograms

Other implementations: C | CLIPS | C++ | C# | Eiffel | Erlang | Io | Java | Lisp | Smalltalk

This article covers an implementation of bubble sort in C#.

Bubble sort is an inefficient but very simple - perhaps even the simplest - sorting algorithm, which uses one straightforward rule for its work: while there remains an i^th element that is greater than the (i+1)^th element, swap them.

Thus, elements with greater values will 'float' to the end of the array, like bubbles.

Integer arrays (C# 1.0)

Firstly, let's write a function which sorts a simple array of integer values:

<<integer array sort>>=
static void bubble_sort( int[] array )
{
	long right_border = array.Length - 1;
	do
	{
		long last_exchange = 0;
		for (long i = 0; i < right_border; i++)
		{
			if (array[i] > array[i + 1])
			{
				int temp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = temp;
				last_exchange = i;
			}
		}
		right_border = last_exchange;
	}
	while (right_border > 0);
}

In this function you may see one little improvement over the 'classic' bubble sort. The 'right_border' variable keeps an index to where the last exchange happened at the previous iteration of the 'do' cycle. This variable keeps a right border of the not yet sorted sequence in the array. If it has value of i, it means that no exchanges were made within elements with indices from i to the end of the array. That is possible only if these elements are placed in the correct order, if they are sorted. Thus it is not necessary to check them at the next iteration. It is then simple to decide when to stop sorting - when there were no exchanges at all and the right border is 0 we can say that the array is sorted.

Generic implementation (C# 2.0)

The generic implementation of bubble sort takes advantages of 'generics' in C# 2.0: now our function can sort not only integers but anything that supports the IComparable interface. This interface is needed because there is no other way to decide if one element is greater or less than another while operating with unknown, 'generic', types.

<<generic array sort>>=
static void bubble_sort_generic<T>( T[] array ) where T : IComparable
{
	long right_border = array.Length - 1;
	do
	{
		long last_exchange = 0;
		for ( long i = 0; i < right_border; i++ )
		{
			if ( array[i].CompareTo(array[i + 1]) > 0 )
			{
				T temp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = temp;
				last_exchange = i;
			}
		}
		right_border = last_exchange;
	}
	while ( right_border > 0 );
}

Files

Let's combine those methods with a test Main function to make a working program:

<<BubbleSortExample.cs>>=
using System;
class BubbleSortExample
{
    integer array sort
    generic array sort
    static void Main(string[] args)
    {
        // create test array and fill it with random values
        int[] array = new int[1024];
        Random rnd = new Random( Environment.TickCount );
        for ( int i = 0; i < array.Length; i++ ) array[i] = rnd.Next();
        // sort our array
        bubble_sort_generic( array );
        // check if it really sorted now
        bool sorted = true;
        for ( int i = 0; sorted && (i < array.Length - 1); i++ )
        {
             if ( array[i] > array[i + 1] ) sorted = false;
        }
        Console.WriteLine( sorted ? "array sorted" : "something wrong" );
    }
}