Overview and explanation of the most common sorting algorithms. Learn about Bubble sort, Insertion sort, Merge sort, Quick sort algorithms.

The need to sort data

Before we look at sorting algorithms, let’s understand why we need to sort the data.

At first glance, it’s much easier to find someone’s name if you look through an alphabetical list.

Using ordered data also speeds up searching for and finding elements in Arrays, Lists, Sets, Collections etc.

Reduced time leads to the use of less computing power in computing machines, which in turn consume less electricity. Try to create and use efficient algorithms (not just sorting) to save natural resources – they are not endless.

Sorting can be done in ascending or descending order of elements (in value of numbers, in alphabetical order of words and expressions) or by other criteria.

If we are looking for an item in an unsorted list L(n) and the list is in computer memory, we will need to perform a Linear search. If the searched element is in the last place we will have to make n number of comparisons.

If the list is sorted, we can use Binary Search. By Binary Search the number of comparisons will be log₂​n.

To put it more clearly, binary search will take significantly less time than linear search.

Sorting algorithms

Sorting is any process of arranging items systematically. It has two meanings:

  – Ordering, which is arranging items in a sequence ordered by some criterion.

  – Categorizing, which is grouping items with similar properties.

Classification of sorting algorithms

Time complexity

This is the ratio of execution time to the input parameter (input unsorted data).

Logarithmic function F(N) = LOG N. Strictly increasing function and has a vertical asymptote along the Y-axis (N=0).

This is also called „logarithmic time “.

Linear function F(N) = N. Incerase as increase its argument.

This is also called „linear time “.

Square function F(N) = N². Its range is the non-negative real numbers: [0, +∞).

This is also called „quadratic time “.

Space complexity (memory usage) of the sorting algorithms

This is the amount of memory used in conjunction with the input parameter. There are two subsets of sorting algorithms by space complexity:

      – In-place algorithms, which use constant amount of memory.

      – Out-of-place algorithms, which use extra amount of memory, according to input parameter.

Stability of the sorting algorithms

This is the ability of the algorithm to keep the order of the items in the sorted list relative to their order in the unsorted list. This characteristic is related to the Permutations of the elements. If we have several identical elements, the Stable Algorithm will maintain their relative sequence with respect to the index. The unstable one will not keep the order of the index.

Type of memory usage

      – If the algorithm use only Main memory (RAM), it is classified as an internal sort algorithm.

      – If the algorithm use also Auxiliary memory (ssd, hdd, database), it is classified as an external sort algorithm.

Method of achieving the result

      – Iterative algorithms.

      – Recursive algorithms.

  You can see differences between iterative and recursive algorithms.

I will present several sorting algorithms written in PHP and also consider their action and evaluation.

Selection sort algorithm

Selection sort is probably the easiest algorithm to understand. The idea is to compare the first element of an list with all other elements until a smaller one is found. If smaller is found, it is established as the smallest and its place is exchanged with the first element. If smaller is not found the first become smallest. This comparison is repeated for the second, third, etc. to the penultimate element. Selection sort characteristics:

  – Time complexity O(n²).

  – Space complexity In-place O(1).

  – Unstable algorithm.

  – Internal sort algorithm.

  – Iterative algorithm.

Example of PHP program to demonstrate Selection sort algorithm

namespace IterativeSortingAlgorithms;

// You can use the conventional format without a reference.
// function selectionSort($array)

// Selection Sort function using a reference to save memory and time.
function selectionSort(&$testArray)
{
    $arrayLength = count($testArray);
    $timeStart = microtime(true);
    
    // $arrayLength - 1, because the last element will be auto sorted.
    for ($i = 0; $i < $arrayLength - 1; $i++) {
        $smallestElementIndex = $i;
        for ($j = $i + 1; $j < $arrayLength; $j++) {
            if ($testArray[$j] < $testArray[$smallestElementIndex]) {
                $smallestElementIndex = $j;
            }
        }
        $temporaryElement = $testArray[$i];
        $testArray[$i] = $testArray[$smallestElementIndex];
        $testArray[$smallestElementIndex] = $temporaryElement;
    }
    $timeEnd = microtime(true);
    
    // Add 1 second to convert from scientific notation.
    $timeExecution = ($timeEnd - $timeStart) + 1;
    echo "Execution time: " . round($timeExecution, 10) . " seconds \n";
    
    // return $testArray; Uncomment if You use the conventional format.
}

$testArray = array(4, 56, 89, 0, 23, 11, 64);
$testArrayLength = count($testArray);
$sortedArray = selectionSort($testArray);

// You can test more options.
// $testArray = range(0, 1000);
// shuffle($testArray);
// $testArrayLength = count($testArray);
// $sortedArray = selectionSort($testArray);

echo "Sorted array:";
for ($i = 0; $i < $testArrayLength; $i++) {
    echo ' ' . $testArray[$i];
}

Output:
Execution time: 1.0000140667 seconds.
Sorted array: 0 4 11 23 56 64 89.

Run

Bubble sort algorithm

Bubble sort algorithm is similar to Selection sort. It has a comparison of neighboring elements. The comparison starts from the first element of the list with the second element.

  – If the first element is larger, swap their places.

  – If the first element is smaller, move on to the second as the main one for comparison.

The second is compared to the third… and the comparison is repeated until the last element. In this series of comparisons, the largest element goes to the end of the list. It emerges like a bubble of air from the water. This algorithm is repeated until all elements are shifted to the right (emerge) according to their value.

Bubble sort characteristics:

  – Time complexity O(n²).

  – Space complexity In-place O(1).

  – Stable algorithm.

  – Internal sort algorithm.

  – Iterative and recursive algorithm.

Example of PHP program to demonstrate Bubble sort algorithm

namespace IterativeSortingAlgorithms;

function bubbleSort(&$testArray)
{
    $arrayLength = count($testArray);
    $timeStart = microtime(true);
    for ($i = 0; $i < $arrayLength - 1; $i++) {
    
        // $arrayLength - $i - 1, because every last element will be sorted.
        for ($j = 0; $j < $arrayLength - $i - 1; $j++) {
            if ($testArray[$j + 1] < $testArray[$j]) {
                $temporaryElement = $testArray[$j];
                $testArray[$j] = $testArray[$j + 1];
                $testArray[$j + 1] = $temporaryElement;
            }
        }

    }
    $timeEnd = microtime(true);
    
    // Add 1 second to convert from scientific notation.
    $timeExecution = ($timeEnd - $timeStart) + 1;
    echo "Execution time: " . round($timeExecution, 10) . " seconds \n";
    return $testArray;
}

$testArray = array(4, 56, 89, 0, 23, 11, 64);
$testArrayLength = count($testArray);
$sortedArray = bubbleSort($testArray);

// You can test more options.
// $testArray = range(0, 1000);
// shuffle($testArray);
// $testArrayLength = count($testArray);
// $sortedArray = selectionSort($testArray);

echo "Sorted array:";
for ($i = 0; $i < $testArrayLength; $i++) {
    echo ' ' . $testArray[$i];
}

Output:
Execution time: 1.000451088 seconds.
Sorted array: 0 4 11 23 56 64 89.

Run

Example of PHP program to demonstrate recursive Bubble sort algorithm

namespace IterativeSortingAlgorithms;

function recursiveBubbleSort(&$testArray, $arrayLength, $memoryStart)
{
    if ($arrayLength == 1) {
    	$memoryEnd = memory_get_usage();
    	echo "Memory used: " . abs($memoryEnd - $memoryStart) . " bytes\n";
        return;
    }
    for ($i = 0; $i < $arrayLength - 1; $i++) {
        if ($testArray[$i + 1] < $testArray[$i]) {
            $temporaryElement = $testArray[$i];
            $testArray[$i] = $testArray[$i + 1];
            $testArray[$i + 1] = $temporaryElement;
        }
    }
    recursiveBubbleSort($testArray, $arrayLength - 1, $memoryStart);
}

$testArray = array(4, 56, 89, 0, 23, 11, 64);
$testArrayLength = count($testArray);
$memoryStart = memory_get_usage();
$timeStart = microtime(true);
recursiveBubbleSort($testArray, $testArrayLength, $memoryStart);
$timeEnd = microtime(true);

// Add 1 second to convert from scientific notation.
$timeExecution = ($timeEnd - $timeStart) + 1;
echo "Execution time: " . round($timeExecution, 10) . " seconds\n";
echo "Sorted array:";
for ($i = 0; $i < $testArrayLength; $i++) {
    echo ' ' . $testArray[$i];
}

Output:
Memory used: 400 bytes.
Execution time: 1.0000619888 seconds.
Sorted array: 0 4 11 23 56 64 89.

Run

Insertion sort algorithm

Insertion sort algorithm is similar to Selection sort and Bubble sort.

This sorting algorithm divides the list into two subsets. A subset of unsorted items and a subset of sorted items. In the beginning, all elements are in the set of unsorted elements. The first element is taken and placed in the subset of sorted elements. Then the second element is taken and compared with the elements of the sorted subset (in this case only one).

  – If the item being compared is smaller than the one in the sorted set, go one position to the left.

  – If the item being compared is larger than the one in the sorted set, it goes one position to the right.

This algorithm is repeated with each element of the unsorted set until it is compared with each element of the sorted set and finds its place.

Insertion sort characteristics:

  – Time complexity O(n²).

  – Space complexity In-place O(1).

  – Stable algorithm.

  – Internal sort algorithm.

  – Iterative algorithm.

Example of PHP program to demonstrate Insertion sort algorithm

namespace IterativeSortingAlgorithms;

function insertionSort(&$testArray)
{
    $arrayLength = count($testArray);
    $timeStart = microtime(true);
    for ($i = 1; $i < $arrayLength; $i++) {
        $temporaryElement = $testArray[$i];
        $hole = $i;
        while ($hole > 0 && $temporaryElement < $testArray[$hole - 1]) {
            $testArray[$hole] = $testArray[$hole - 1];
		        $hole--;
		    }
		    $testArray[$hole] = $temporaryElement;
		}
    $timeEnd = microtime(true);
    
    // Add 1 second to convert from scientific notation.
    $timeExecution = ($timeEnd - $timeStart) + 1;
    echo "Execution time: " . round($timeExecution, 10) . " seconds\n";
    return $testArray;
}

$testArray = array(4, 56, 89, 0, 23, 11, 64);
$testArrayLength = count($testArray);
$sortedArray = insertionSort($testArray);

// You can test more options.
// $testArray = range(0, 1000);
// shuffle($testArray);
// $testArrayLength = count($testArray);
// $sortedArray = selectionSort($testArray);

echo "Sorted array:";
for ($i = 0; $i < $testArrayLength; $i++) {
    echo ' ' . $testArray[$i];
}

Output:
Execution time: 1.000013113 seconds.
Sorted array: 0 4 11 23 56 64 89.

Run

Merge sort algorithm

The basic concept in the recursive execution of a function is to divide the task into smaller tasks until the smallest indivisible task is reached. A strategy known in history as „Divide and Conquer “. A function if it calls itself until it reaches a certain threshold (fulfillment of a certain condition) is called a recursive function. Each time the function is called, the task is broken down into smaller tasks, at the expense of increasing the occupied stack memory.

Merge sort is a recursive sorting algorithm. This sorting algorithm divides the input list into two parts. Each part into two more parts… so until you reach lists with one item. Obviously a list of one item is always sorted.

Merge sort characteristics:

  – Time complexity O(n*log n).

  – Space complexity Not In-place O(n).

  – Stable algorithm.

  – Internal sort algorithm.

  – Recursive algorithm.

Example of PHP program to demonstrate Merge sort algorithm

namespace IterativeSortingAlgorithms;

// Function mergeSort splits the array and calls function merge to sort and merge the array.
function mergeSort(&$array, $left, $right, $memoryStart) {
    if ($left < $right) {
    	$i = 0;
        $middle = $left + (int)(($right - $left)/2);
        mergeSort($array, $left, $middle, $memoryStart);
        mergeSort($array, $middle + 1, $right, $memoryStart);
        merge($array, $left, $middle, $right);
    }
    $memoryEnd = memory_get_usage();
    echo "Memory used: " . abs($memoryEnd - $memoryStart) . " bytes\n";
}

// Merge function performs sort and merge operations or mergeSort function.
// Creates two temporary arrays to hold split elements of main array.
function merge(&$array, $left, $middle, $right) {
    $leftElements = $middle - $left + 1;
    $rightElements = $right - $middle;
    $leftArray = array_fill(0, $leftElements, 0); 
    $rightArray = array_fill(0, $rightElements, 0);
    for($i=0; $i < $leftElements; $i++) { 
        $leftArray[$i] = $array[$left + $i];
    }
    for($i=0; $i < $rightElements; $i++) { 
      $rightArray[$i] = $array[$middle + $i + 1];
    }

    // Here x, y and z represents index number
    // of left array, right array and full array.
    $x = 0;
    $y = 0;
    $z = $left;
    while($x < $leftElements && $y < $rightElements) {
        if($leftArray[$x] < $rightArray[$y]) { 
            $array[$z] = $leftArray[$x]; 
            $x++; 
        }
        else { 
            $array[$z] = $rightArray[$y];  
            $y++; 
        }
        $z++;
    }

    // Copy the remaining elements of left array.
    while($x < $leftElements) { 
        $array[$z] = $leftArray[$x];  
        $x++;  
        $z++;
    }

    // Copy the remaining elements of right array
    while($y < $rightElements) { 
        $array[$z] = $rightArray[$y]; 
        $y++;  
        $z++; 
    }
}

$testArray = array(4, 56, 89, 0, 23, 11, 64);
$testArrayLength = count($testArray);
$memoryStart = memory_get_usage();
$timeStart = microtime(true);
mergeSort($testArray, 0, $testArrayLength - 1, $memoryStart);
$timeEnd = microtime(true);
$timeExecution = ($timeEnd - $timeStart) + 1;

echo "Execution time: " . round($timeExecution, 10) . " seconds\n";
echo "Sorted array:";
for ($i = 0; $i < $testArrayLength; $i++) {
    echo ' ' . $testArray[$i];
}

Output:
Memory used: 432 bytes.
Execution time: 1.0001189709 seconds.
Sorted array: 0 4 11 23 56 64 89.

Run

Quick sort algorithm

The Quick sort algorithm defines one of the elements of the list as a pivot and distributes the other elements to this pivot. The smaller items are placed on the left and the larger ones on the right. Of course, there can be more than one possible arrangement for elements smaller than the pivot, as well as for elements larger than the pivot. The next step in the algorithm is to split this list into two parts. The left part will be with the smaller elements and the right part with the larger ones. The algorithm marks the beginning and end of each segment. In the same way, each segment is called recursively and is divided into left and right segments until a segment containing one element remains. This is the condition for exiting recursion for the current segment.

Note that this algorithm works with only one list (array), using its indexes and shifting the locations of the elements.

Quick sort algorithm also uses the strategy „Divide and Conquer“.

Quick sort characteristics:

  – Time complexity O(n²).

  – Time complexity  O(n*log n) for the randomized version of Quick sort algorithm.

  – Space complexity In-place O(log n).

  – Space complexity Not In-place O(n).

  – Stable algorithm.

  – Internal sort algorithm.

  – Recursive algorithm.

Example of PHP program to demonstrate Quick sort algorithm

namespace RecursiveSortingAlgorithms;

function quickSort(&$workArray, $leftIndex, $rightIndex, $memoryStart)
{
    $index = partition($workArray, $leftIndex, $rightIndex);
    if ($leftIndex < $index - 1)
        quickSort($workArray, $leftIndex, $index - 1, $memoryStart);
    if ($index < $rightIndex)
        quickSort($workArray, $index, $rightIndex, $memoryStart);
    $memoryEnd = memory_get_usage();
    return $memoryEnd - $memoryStart;
}

function partition(&$workArray, $leftIndex, $rightIndex)
{
    $pivot = $workArray[($leftIndex + $rightIndex) / 2];
    while ($leftIndex <= $rightIndex) {        
        while ($workArray[$leftIndex] < $pivot)            
                $leftIndex++;
        while ($workArray[$rightIndex] > $pivot)
                $rightIndex--;
        if ($leftIndex <= $rightIndex) {  
                $temporary = $workArray[$leftIndex];
                $workArray[$leftIndex] = $workArray[$rightIndex];
                $workArray[$rightIndex] = $temporary;
                $leftIndex++;
                $rightIndex--;
        }
    }
    echo implode(", " , $workArray) . " @pivot $pivot\n";
    return $leftIndex;
}

$testArray = array(4, 56, 89, 0, 23, 11, 64);
echo implode(", " , $testArray) . " @unsorted\n";
$memoryStart = memory_get_usage();
$timeStart = microtime(true);
$memory = quickSort($testArray, 0, count($testArray) - 1, $memoryStart);
$timeEnd = microtime(true);
echo implode(", " , $testArray) . " @sorted\n\n";
echo "Memory used: " . abs($memory) . " bytes\n";
$timeExecution = ($timeEnd - $timeStart) + 1;
echo "Execution time: " . round($timeExecution, 10) . " seconds\n";

Output:
4, 56, 89, 0, 23, 11, 64 @unsorted
0, 56, 89, 4, 23, 11, 64 @pivot 0
0, 4, 89, 56, 23, 11, 64 @pivot 4
0, 4, 11, 23, 56, 89, 64 @pivot 23
0, 4, 11, 23, 56, 89, 64 @pivot 11
0, 4, 11, 23, 56, 64, 89 @pivot 89
0, 4, 11, 23, 56, 64, 89 @pivot 56
0, 4, 11, 23, 56, 64, 89 @sorted

Memory used: 400 bytes.
Execution time: 1.0000579357 seconds.

Run

Notes to remember about sorting algorithms

• Binary search takes significantly less time than linear search.
• Selection sort, Bubble sort and Insertion sort are slow iterative sorting algorithms.
• Merge sort and Quick sort are recursive algorithms.

Recommended References

• Linear Time vs. Logarithmic Time
• Sorting algorithms visualization
• Sorting algorithms comparison
• Sorting algorithm

Conclusion

In this paper we have compared the performance of several popular sorting algorithms using various metrics such as time complexity, space complexity and memory usage.

Check other useful posts from our blog What is an SSL Certificate, how to debug PHP code, The fastest sorting algorithm.