Bubble sort

From Wikipedia, the free encyclopedia
Jump to: navigation, search
A bubble sort illustrated

Bubble sort is a simple sorting algorithm. It is very simple for understanding and realization; therefore it is considered as a training algorithm. In real applications it is not used since it is not efficient.

Algorithm[change | change source]

Algorithm compares every two items which stands side by side and swapping them if they are in the wrong order. Array of n elements can be sorted within n-1 passes. For example:

First pass:
(4, 3, 1, 2) → (3, 4, 1, 2)
(3, 4, 1, 2) → (3, 1, 4, 2)
(3, 1, 4, 2) → (3, 1, 2, 4)

Second pass:
(3, 1, 2, 4) → (1, 3, 2, 4)
(1, 3, 2, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)

Third pass:
(1, 2, 3, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)
(1, 2, 3, 4) → (1, 2, 3, 4)

Implementation[change | change source]

Not optimized[change | change source]

static void BubbleSort(int[] array)
{
    int n = array.Length;
    for (int pass = 1; pass <= n - 1; pass++)
        for (int i = 0; i < n - 1; i++)
            if (array[i] > array[i + 1])
            {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
}

This is not an optimized implementation of the algorithm. It always does n-1 passes even if the array is sorted already. Complexity of this implementation is O(n2-n)

Pass optimized[change | change source]

static void BubbleSort(int[] array)
{
    int n = array.Length;
    bool swapped;
    do
    {
        swapped = false;
        for (int i = 0; i < n - 1; i++)
            if (array[i] > array[i + 1])
            {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = true;
            }
    } while (swapped);
}

This is pass optimized implementation of the algorithm. Obviously, there is no necessity to do passes if array was sorted or became sorted after one of the passes. So in this implementation there is a flag swapped which signalize whether was swapped elements in the current pass or not. If not then cycle is ended. In the best case, then array is sorted already, complexity of this implementation is O(n). In the worst case, then array sorted by descending, complexity is O(n2).

PHP Implementation[change | change source]

This implementation of bubble sort is optimized to require a decreasing number of iterations with every pass. In terms of performance, the logic in this code will produce in a best-case just under 50% less iterations to sort when compared to either of the above implementations.

function bubbleSort( &$arr, $asc = true ) {
	$iterations = 0;
	$len = count( $arr );
	$i = 0;
	$ordered = false;
	$newLen = $len;
	while ( !$ordered ) :
		$ordered = true;
		for ( $i = 1; $i < $len; $i++ ) :
			$iterations++;
			$a = $arr[ $i - 1 ];
			$b = $arr[ $i ];
			$comp = (float)( (float)$a - (float)$b );
			if ( ( $asc && $comp > 0 ) || ( !$asc && $comp < 0 ) ) :
			$arr[ $i - 1 ] = $b;
			$arr[ $i ] = $a;
			$ordered = false;
			$newLen = $i;
			endif;
		endfor;
		$len = $newLen;
	endwhile;
	return( $iterations );
}
$arr = array( 4, 4, 3, 2, 4, 5, 88, 3, 8448, 43, 2, 0, 480, 334, 1, 0 );
$iterations = bubbleSort( $arr );
echo( "\nIt took " . $iterations . " iterations to sort the array.\n\n" );
print_r( $arr );

Other websites[change | change source]