kidzsearch.com > wiki Explore:web images videos games
Bubble sort
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.
Contents
Algorithm
The bubble sort algorithm compares every two items which are next to each other, and swaps them if they are in the wrong order. An array of n elements can be sorted within n1 passes. For example, in this array of 4 items:
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
Not optimized
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 n1 passes even if the array is sorted already. Complexity of this implementation is O(n^{2}n)
Pass optimized
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(n^{2}).
PHP Implementation
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 bestcase 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

