Sorting is the process of arranging data in a certain order. Sorting is done by the value of the elements. Numbers, words, pairs, etc. can be sorted. Students can be sorted by their height; and cities can be sorted in alphabetical order by name, or by their numbers of citizens. The most-used orders are numerical order and alphabetical order. Consider a simple set, an array consisting of integers:

Sorting this array in ascending order, gives:

There are many sorting algorithms, and they differ considerably in terms of their time complexity and use of memory. Some are described in this lesson (tutorial).

Bubble Sort

The simplest sorting algorithm is the bubble sort algorithm. Given an unsorted list, and starting from the left end, the algorithm swaps the first two elements if they are not in order. It then swaps the next two elements if they are not in order. One element would be from the first swap, if swapping took place there. It swaps the following two elements; one element would be from the previous swap if swapping took place there. This continues until the element at the extreme right is addressed. The whole list is re-scanned in that fashion; over and over, until the list is completely sorted. In this section of the lesson (tutorial), sort ascending for bubble sort is considered.

Bubble Sort Illustration

Consider the following unsorted list:

R    X    F    S    U    Z    V    J

There are 8 elements, which need 8 complete scans, for bubble sort, resulting in

R    F    S    U    X    V    J    Z
F    R    S    U    V    J    X    Z
F    R    S    U    J    V    X    Z
F    R    S    J    U    V    X    Z
F    R    J    S    U    V    X    Z
F    J    R    S    U    V    X    Z
F    J    R    S    U    V    X    Z
F    J    R    S    U    V    X    Z

The final list arrangement is the complete sort.

Worst-Case Performance

The PHP code to sort the above eight characters, as explained above is:

<?php
    function bubbleSort($arr, $N) {
        global $arr;
        $counter = 0;
        for ($i = 0; $i < $N; $i++) {    //number of rows
            for ($j = 1; $j < $N; $j++) {
                if ($arr[$j] < $arr[$j - 1]) {
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j - 1];
                    $arr[$j - 1] = $temp;
                }
                $counter+=1;
            }
        }
        echo $counter . "\n";
    }

    $arr = ['R', 'X', 'F', 'S', 'U', 'Z', 'V', 'J'];
    bubbleSort($arr, 8);
    for ($i = 0; $i < 8; $i++)
        echo $arr[$i] . ', '; 
    echo "\n";
?>

The code for swapping is in the inner nested for-loop. The counter counts the number of basic (main) operations. The outer for-loop loops from 0 to 7, i.e., 8 times. The inner for-loop loops from 1 to 7, i.e., 7 times. The total number of basic operations (inner for-loop) is 8 x 7 = 56. The counter output is 56.