# Difference between revisions of "Bubble sort"

(→Pseudo-code) |
|||

Line 2: | Line 2: | ||

{{Stub}} | {{Stub}} | ||

− | '''Bubble sort''' is one of the most inefficient [[sorting]] algorithms. While asymptotically equivalent to the other <math>O(n^2)</math> algorithms, it will require <math>O(n^2)</math> swaps in the worst-case. However, it is probably the simplest to understand. At each step, if two adjacent elements of a list are not in order, they will be swapped. Thus, smaller elements will "bubble" to the front, (or bigger elements will be "bubbled" to the back, depending on implementation) and hence the name. This algorithm is almost never recommended, as [[insertion sort]] has the same asymptotic complexity, but only requires <math>O(n)</math> swaps. Bubble sort is stable, as two equal elements will never be swapped. | + | '''Bubble sort''' is one of the most inefficient [[sorting]] algorithms because of how simple it is. While asymptotically equivalent to the other <math>O(n^2)</math> algorithms, it will require <math>O(n^2)</math> swaps in the worst-case. However, it is probably the simplest to understand, which accounts for its lack in efficiency. At each step, if two adjacent elements of a list are not in order, they will be swapped. Thus, smaller elements will "bubble" to the front, (or bigger elements will be "bubbled" to the back, depending on implementation) and hence the name "bubble sort". This algorithm is almost never recommended, as [[insertion sort]] has the same asymptotic complexity, but only requires <math>O(n)</math> swaps. Bubble sort is stable, as two equal elements will never be swapped. |

== Pseudo-code == | == Pseudo-code == | ||

Line 15: | Line 15: | ||

end func | end func | ||

</pre> | </pre> | ||

− | + | ||

== C++ == | == C++ == |

## Revision as of 10:56, 5 December 2017

Sorting
| |

Algorithms
| |

Bubble sort
| |

Insertion sort | |

Selection sort | |

Quicksort | |

Merge sort | |

Heap sort | |

Introsort | |

Counting sort | |

Problems
| |

Problems solvable using sorting |

This is a stub or unfinished. Contribute by editing me. |

**Bubble sort** is one of the most inefficient sorting algorithms because of how simple it is. While asymptotically equivalent to the other algorithms, it will require swaps in the worst-case. However, it is probably the simplest to understand, which accounts for its lack in efficiency. At each step, if two adjacent elements of a list are not in order, they will be swapped. Thus, smaller elements will "bubble" to the front, (or bigger elements will be "bubbled" to the back, depending on implementation) and hence the name "bubble sort". This algorithm is almost never recommended, as insertion sort has the same asymptotic complexity, but only requires swaps. Bubble sort is stable, as two equal elements will never be swapped.

## Pseudo-code

a is an array size n

func bubblesort( var a as array ) for i from 1 to N for j from 0 to N - 1 if a[j] > a[j + 1] swap( a[j], a[j + 1] ) end func

## C++

a is an array,n is the size of the array

void bubblesort( int *a , int n ) { int temp; //for swapping for (int i = 0 ; i < n - 1 ; i++) { for (int j = 0 ; j < n - 1 ; j++) { if ( a[j] > a[j + 1] ) { temp = a[j]; a[j]=a[j + 1]; a[j + 1] = temp; } } } }

## C#

bool swapped = true; while (swapped == true) { swapped = false; for (int y = 0; y < array.Length - 1; y++) { if (numbers[y] > array[y + 1]) { swapped = true; int temp = array[y]; array[y] = array[y + 1]; array[y + 1] = temp; } } }

## Optimizations

A small improvement can be made if each pass you keep track of whether or not an element was swapped. If not, you can safely assume the list is sorted.

**Pseudo-code**

func bubblesort2( var a as array ) for i from 2 to N swaps = 0 for j from 0 to N - 2 if a[j] > a[j + 1] swap( a[j], a[j + 1] ) swaps = swaps + 1 if swaps = 0 break end func

**C++**

void bubblesort2( int * a , int n ) { int temp,swaps; for( int i = 0 ; i < n - 2 ; i++ ) { swaps=0; for ( int j = 0 ; j < n - 1 ; j++ ) { if ( a[j] > a[j + 1] ) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; swaps++; } } if( swaps == 0 ) { break; } } }

A second optimization can be made if you realize that at the end of the i-th pass, the last i numbers are already in place. Consider the sequence {3, 9, 1, 7}. After the first pass, the 9 will end up in the final position; we need not consider it on subsequent passes.

**Pseudo-Code**

func bubblesort3( var a as array ) for i from 1 to N swaps = 0 for j from 0 to N - i if a[j] > a[j + 1] swap( a[j], a[j + 1] ) swaps = swaps + 1 if swaps = 0 break end func

**C++**

void bubblesort3( int * a , int n) { int temp,swaps; for( int i = 0 ; i < n - 2 ; i++ ) { swaps=0; for ( int j = 0 ; j < n - i - 1 ; j++ ) { if ( a[j] > a[j + 1] ) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; swaps++; } } if( swaps == 0 ) { break; } } }

One can still improve the above optimization a little bit. Let a[k] and a[k+1] be the last two numbers swapped in the i-th pass. Then surely the numbers a[k+1] to a[n] are already in their final positions. In the next pass we only need to consider the numbers a[1] to a[k], i.e., loop from 1 to k-1. The above optimization only lets us ignore the last number of each pass; this optimization can ignore potentially many numbers in each pass.

**Pseudo-Code**

func bubblesort4( var a as array ) bound = N-1 for i from 1 to N newbound = 0 for j from 0 to bound if a[j] > a[j + 1] swap( a[j], a[j + 1] ) newbound = j - 1 bound = newbound end func

**C++**

void bubblesort4( int * a , int n ) { int temp,j,bound = n - 1, new_bound = 0; for( int i = 0 ; i < n - 1 ; i++ ) { for ( j = 0 ; j < bound ; j++ ) { if ( a[j] > a[j + 1] ) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; new_bound = j; } } bound = new_bound; } }

## Java

This code asks for the no. of elements in the array and then you can enter unsorted array. It prints sorted array using BubbleSort

import java.util.Scanner; public class BubbleSort { static void bubblesort(Integer[] ar) { for (int i = 0 ; i < ar.length - 1 ; i++) for (int j = 0 ; j < ar.length - 1 ; j++) { if ( ar[j] > ar[j + 1] ) { int temp = ar[j]; ar[j] = ar[j + 1]; ar[j + 1] = temp; } } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); Integer[] ar = new Integer[n]; for (int i = 0; i < n; i++) ar[i] = in.nextInt(); bubblesort(ar); for (Integer v : ar) System.out.print(v+" "); System.out.println(""); } }

A further improvement can be doing successive passes in opposite directions. This ensures that if one small number is at the end or one large number is at the beginning it reaches its final position in one pass.

## Implementations

- C iterative