# Bubble sort

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

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 n-1 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 n-1 passes even if the array is sorted already. Complexity of this implementation is O(n2-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(n2).

### 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 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 );
```