Learn Simpli

Free Online Tutorial For Programmers, Contains a Solution For Question in Programming. Quizzes and Practice / Company / Test interview Questions.

 

Bubble Sort

How bubble sort

How it works
  1. Sorts an array of n elements in ascending or descending order,
  2. It swaps the element if the right element is smaller than the left element

Ascending order:
In ascending order, starts comparing the first element of an array with the second element. If the first element is greater than the second element, then it will shift the first element to the position of the second element. Keeps repeating until all element is sorted. For every iteration, the largest element will be moved at the end.

Descending order:
In ascending order, starts comparing the first element of an array with the second element. If the first element is smaller than the second element, then it will shift the first element to the position of the second element. Keeps repeating until all element is sorted. For every iteration, the smallest element will be moved at the end.

Performance:

  1. “Best case performance: Time complexity O(n) for sorted array”,
  2. “Average case performance: Time complexity O(n2) for unsorted array”,
  3. “Worst-case performance: Time complexity O(n2) for unsorted array”,

Advantage:

  1. Easy and simple to implement
  2. Best suited for sorted array

Disadvantage:

  1. It is not best suited for a large number of elements to be sorted.
  2. It has worst-case time complexity for the unsorted array.

Source code:

Bubble Sort algorithm can be implemented in the following way

function bubbleSort(array) 
{
    var isElementSwapped;
    do {

        isElementSwapped = false;
        for (var i=0; i < array.length-1; i++) 
        {
            if (array[i] > array[i+1]) 
            {
                var temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
                isElementSwapped = true;
            }
        }

    } while (isElementSwapped);
}

var array = [5,1,8,10,9,4,3];
bubbleSort(array);
console.log(array);
// output
// [1, 3, 4, 5, 8, 8, 9, 10]
function bubbleSortPHP($array) {
    $sizeOfArray = count($array)-1;
    for ($i=0; $i < $sizeOfArray; $i++) {
        for ($j=0; $j&lt;$sizeOfArray-$i; $j++) {
            $k = $j+1;
            if ($array[$k] &lt; $array[$j]) {
                // Swap elements at indices: $j, $k
                list($array[$j], $array[$k]) = array($array[$k], $array[$j]);
            }
        }
    }
    return $array;
}
$array = array(5,6,2,3,7,1,9,8);

$array = bubbleSortPHP($array);
echo json_encode($array);
// output
// [1,2,3,5,6,7,8,9]

Also read, Sorting algorithms