Bubble sort

Bubble sort is a simple sorting algorithm with quadratic asymptotic complexity $O(n^{2})$ . Improved version of bubble sort is shaker sort (cocktail sort), which is a bidirectional version of this algorithm.

Description

We can imagine that sorted numbers are bubbles, the ones with lower value are lighter than the ones with higher value, hence they ascend to the surface faster.

Bubble sort advances similarly. In every step it compares two adjacent elements and if the lower value is on the left side of the higher, bubble sort swaps them (lighter value ascends to the end of the array) and with the same logic algorithm proceeds to the next item.

After one iteration the lowest value is located at the end of the array. Algorithm now repeats the procedure with reduced array (the last element is already sorted). After n-1 iterations is the array completely sorted, because the last bubble is sorted trivially.

Visualization

Example

(3 2 8 7 6) // initial array, sort the elements in descending order
(3 2 8 7 6) // 3 and 2 are in correct order, shift to the next index
(3 2 8 7 6) // 8 > 2, swap them
(3 8 2 7 6) // 7 > 2, swap them (the lightest bubble "2" is ascending)
(3 8 7 2 6) // 6 > 2, swap them
(3 8 7 6 2) // Second pass: the lightest bubble is at end of the array. The problem size is now reduced to n-1 elements. 8 > 3, swap them
(8 3 7 6 2) // 7 > 3, swap them
(8 7 3 6 2) // 6 > 3, swap them
(8 7 6 3 2) // sorted

Code

     function bubbleSort(array a)
         for i in 1 -> a.length - 1 do
             for j in 1 -> a.length - i - 1 do 
                 if a[j] < a[j+1] 
                     swap(a[j], a[j+1]);

     /**
      * Bubble sort (descending order)
      * @param array array to besorted
      */
     public static void bubbleSort(int[] array){
         for (int i = 0; i < array.length - 1; i++) {
             for (int j = 0; j < array.length - i - 1; j++) {
                 if(array[j] < array[j+1]){
                     int tmp = array[j];
                     array[j] = array[j+1];
                     array[j+1] = tmp;
                 }
             }
         }
     }

 /**
  * Bubble sort (ascending order)
  * @param array array to be sorted
  * @param size size of the array
  */
 void bubbleSort(int * array, int size){
     for(int i = 0; i < size - 1; i++){
         for(int j = 0; j < size - i - 1; j++){
             if(array[j+1] < array[j]){
                 int tmp = array[j + 1];
                 array[j + 1] = array[j];
                 array[j] = tmp;
             }   
         }   
     }   
 }

         /**
          * Bubble sort (ascending order)
          * @param arr array to be sorted
          * @author Thomas (www.adamjak.net)
          */
         static void BubbleSort(int[] arr)
         {
             for (int i = 0; i < arr.Length - 1; i++)
             {
                 for (int j = 0; j < arr.Length - i - 1; j++)
                 {
                     if (arr[j + 1] < arr[j])
                     {
                         int tmp = arr[j + 1];
                         arr[j + 1] = arr[j];
                         arr[j] = tmp;
                     }
                 }
             }
         }

 /**
  * Bubble sort (descending order)
  * @param array array to be sorted
  * @auhor Pavel Micka
  */
 function bubbleSort(array){
     for (var i = 0; i < array.length - 1; i++) {
         for (var j = 0; j < array.length - i - 1; j++) {
             if(array[j] < array[j+1]){
                 var tmp = array[j];
                 array[j] = array[j+1];
                 array[j+1] = tmp;
             }
         }
     }
 }

   procedure BubbleSort(var X : ArrayType; N : integer);
   var
     I,
     J : integer;
   begin
     for I := 2 to N do
       begin
         for J := N downto I do
           if (X[J] > X[J - 1]) then
             Swap(X[J - 1], X[J]);
       end
   end;
 
   procedure Swap(var X, Y : integer);
   var
     Temp : integer;
   begin
     Temp := X;
     X := Y;
     Y := Temp
   end;

 /**
  * Bubble sort (ascending order)
  * @param arr array to be sorted
  * @auhor Thomas (www.adamjak.net)
  */ 
 function bubble_sort(&$arr) {
 
     $count = count($arr);
 
     for($i = 0; $i < $count - 1; $i++) {
         for($j = 0; $j < $count - $i - 1; $j++) {
             if($arr[$j + 1] < $arr[$j]) {
                 $tmp = $arr[$j + 1];
                 $arr[$j + 1] = $arr[$j];
                 $arr[$j] = $tmp;
             }
         }
     }
 }

Analysis

There are n-1 outer iterations needed to sort the array, because every iteration puts one element to it's place. Every inner iteration needs one step less the previous one, since the problem size is gradually decreasing. Last part of the algorithm is a condition, which decides whether we should swap the adjacent elements.

Complexity

The complexity of the condition (and possible swap) is obviously constant ( O(1) ). The inner cycle will be performed

$(n-1) + (n-2) + (n-3) + \\cdots + (1)$

times.

Which is in total (according to the formula for arithmetic sequence):

$Total = number \\; of \\;sumands\\cdot{{first+last}\\over{2}}=(n-1)\\cdot{{n-1+1}\\over{2}}={{n^{2}-n}\\over{2}}$

Because this number represents the best and the worst case of algorithm behavior, it's asymptotic complexity after omitting additive and multiplicative constants is $\\Theta(n^{2})$ .