Bubble sort in PHP

Udemy Generic 728x90

Overview

In bubble sort, it compare each pair of adjacent items and swapping them if they are in the wrong order. Then the list is repeated until no swaps are needed, which indicates that the list is sorted.

 

Before we go further, to know more about bubble sore let understand the basic of data structure and algorithm on which it is based on

 

Data Structure – Array

This algorithm use array as a data structure so that we can access the data randomly as per need.

 

Algorithm – Sorting Algorithm

It is an algorithm which put all the elements of an input array in a sequential order

 

Description -

Among various other sorting algorithm, bubble sort algorithm is one of the popular and frequently used algorithm to sort elements either in ascending or descending order.

Bubble sort algorithm starts by comparing the first two elements of an array and swapping if necessary, i.e., if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, if the first element is smaller than second, you mustn’t swap the element. Then, again second and third elements are compared and swapped if it is necessary and this process go on until last and second last element is compared and swapped. This completes the first step of bubble sort.

If there are n elements to be sorted then, the process mentioned above should be repeated n-1 times to get required result. But, for better performance, in second step, last and second last elements are not compared because, the proper element is automatically placed at last after first step. Similarly, in third step, last and second last and second last and third last elements are not compared and so on.

Sometimes referred to as sinking sort. The algorithm gets its name from the way smaller elements “bubble” to the top of the list.

Logical Approach

  1. Begin with the first element, compare it to element adjacent to it.
  2. Then swap it, according to your choice ascending or descending order. For this, you might move the first one out of its position temporarily, move the second one in its place, then move the first one to the new empty position(or the position of second one).
  3. Now repeat the step 1 for the second element, and step 3 for swapping it and move to the end of array of elements.
  4. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

 

Performance

 

  • Worst case: O(n2)
  • Average case: O(n2)
  • Best case: O(n)

Step-by-step example

Let us take the array of numbers “5 1 4 2 8″, and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.

First Pass:

( 51 4 2 8 ) → ( 15 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 54 2 8 ) → ( 1 45 2 8 ), Swap since 5 > 4

( 1 4 52 8 ) → ( 1 4 25 8 ), Swap since 5 > 2

( 1 4 2 58 ) → ( 1 4 2 58 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:

( 14 2 5 8 ) → ( 14 2 5 8 )

( 1 42 5 8 ) → ( 1 24 5 8 ), Swap since 4 > 2

( 1 2 45 8 ) → ( 1 2 45 8 )

( 1 2 4 58 ) → ( 1 2 4 58 )

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

( 12 4 5 8 ) → ( 12 4 5 8 )

( 1 24 5 8 ) → ( 1 24 5 8 )

( 1 2 45 8 ) → ( 1 2 45 8 )

( 1 2 4 58 ) → ( 1 2 4 58 )

 

Example of Bubble sort in PHP

 

&lt;/span&gt;</p>
<p>function bubbleSort(array $arr)</p>
<p>{</p>
<p>    $n =sizeof($arr);</p>
<p>    for($i =1; $i &lt; $n; $i++) {</p>
<p>        $flag =false;</p>
<p>        for($j = $n -1; $j &gt;= $i; $j--) {</p>
<p>            if($arr[$j-1]&gt; $arr[$j]) {</p>
<p>                $tmp = $arr[$j -1];</p>
<p>                $arr[$j -1]= $arr[$j];</p>
<p>                $arr[$j]= $tmp;</p>
<p>                $flag =true;</p>
<p>            }</p>
<p>        }</p>
<p>        if(!$flag) {<br />
            break;<br />
        }<br />
    }</p>
<p>    return $arr;</p>
<p>}</p>
<p>// Example:</p>
<p>$arr = array(255,1,22,3,45,5);</p>
<p>$result = bubbleSort($arr);</p>
<p>print_r($result);</p>
<p>

Output

Array 
(
    [0] => 1
    [1] => 3
    [2] => 5
    [3] => 22
    [4] => 45
    [5] => 255
)
Udemy Generic 728x90

Spread the word. Share this post!