Selection Sort

<?php
    function selectionSort($arr, $N) {
        global $arr;
    
        $counter = 0;
        for ($i = 0; $i < $N; $i++) {
            $minElemIndx = $i;
            for ($j = $i+1; $j < $N; $j++) {
                if ($arr[$j] < $arr[$minElemIndx]) {
                    $minElemIndx = $j;
                }
                $counter+=1;
            }
            //swapping code
            $temp = $arr[$minElemIndx];
            $arr[$minElemIndx] = $arr[$i];
            $arr[$i] = $temp;
        }
        
        echo $counter . "\n"; 
    }

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

Insertion Sort

Well, with insertion sort the comparison is considered as one main operation and the displacement and insertion is also considered as one main operation. For simplicity, in this document, both are considered as one main operation. So the number of main operations in this case is 28, which is greater than 24 = 8.log₂8 and less than 64 = 8². The time complexity for the worse case performance is O(n²). Remember that the official value is the maximum, O(n²).

Average case performance occurs when the unsorted array has some intersperse sorting already. In this situation, A[i] is not always less than A[i-1] in the sorting algorithm. The time complexity for average case performance is O(n²/2). Since it is the maximum that is considered, the time complexity for average case performance is taken as O(n²).

Best case performance occurs when the given list is already sorted. In this situation only the comparisons are made, and no displacement and insertion is made. The time complexity here is O(n), i.e. linear (actually O(n-1), for example, 7 out of 8 comparisons above). For 8 elements, 7 comparisons is slightly less than 8, and so the maximum, O(8) is chosen for time complexity.

Insertion Sort in PHP

<?php
    function insertionSort($A) {
        global $A;
    
        $n = count($A);
        
        for ($i=1; $i < $n; $i++) {
            if ($A[$i] < $A[$i-1]) {    //first comparison
                $temp = $A[$i];
                $j = $i;
                
                do {
                    $A[$j] = $A[$j-1];    //shifting (displacement)
                    --$j;
                
                } while ($temp < $A[$j-1]&&($j>0));  //comparison continuous while j>0
                $A[$j] = $temp;
            }
        }
    }

    $A = ['Z', 'J', 'V', 'S', 'U', 'R', 'X', 'F'];
    
    insertionSort($A);

    for ($i=0; $i < count($A); $i++)
        echo $A[$i] . ' '; 
    echo "\n";  
?>

Counting Sort

What is Counting Sort?

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

This list is to be sorted in ascending order. It can be given (to a sorting program) as an array. It consists of positive numbers greater than or equal to 0.

Notice here that the highest integer is 20. So, 20 + 1 = 21 new array locations have to be provided. The extra 1 is for the possibility that, in the given array, one of the integers to be sorted is 0. Remember that the sorting program does not know the numbers to be sorted in advance. So, the possibility of having 0 should be made (21 new array locations instead of 20). 

For each index of the new array that is a value in the given list, the number of occurrence of that value in the given list is assigned as the value for that new array cell. That is, the new array consists of counters. The previous unsorted list is represented as follows, in the new array:

 The total number of counts gives the number of elements in the unsorted list. This table represents the second array which is the new array of counters. At this stage, there are two arrays: the given array of the unsorted list and the array of counters, called the count array. 

In the table, the second row has the indexes, which are values of the given array. The first row has the counts. Each count is the number of occurrence of the corresponding index in the new array, that is found as value in the unsorted list.

For the indexes 0 to 7 (inclusive), each count is 0. This is because none of these indexes is a value in the given unsorted list. The index 8 occurs once in the given list, so its count is 1. The index 9 occurs zero time in the given list, so its count is 0. The index 10 occurs once in the given list, so its count is 1. The index 12 occurs three times in the given list, so its count is 3. The index 13 occurs zero time in the given list, so its count is 0. This continues until the index 20 with a count of 1, while the index 18 has a count of 2. There are actually 21 cells in the table, due to the included 0. 

The sorted list is as follows:

    8, 10, 12, 12, 12, 14, 16, 18, 18, 20 

This is obtained from the count (new) array as follows:

Moving from left to right of the second array, if the count value of an index is 0, then that index as value, is not in the given unsorted list (array), and should not appear in the sorted list. If the value is 1, write the index once, for the sorted list. If the value is 2, write the index twice, for the sorted list. If the value is 3, write the index three times. If the value is 4, write the index 4 times, and so on. 

Counting Sort Algorithm

    • Create an array whose length is the maximum number in the unsorted list, plus 1 (to account for a possible 0 in the given list). An index of this array is a possible value in the unsorted list. This new (second) array is the count array, where the value in each of its cells, is the number of occurrence of the value in the unsorted aarray.

    • Read the count array from left to right, while writing the index whose cell value is not 0, the number of times, it occurs in the given array. The number of times is the count in the count array. This is sort ascending.

Operations

For the above given unsorted list, the maximum value is 20. So the new array has to be given 21 values (the extra 1 being for a possible 0 unsorted values). Creating this array with its values initialized to 0, consists of 21 main operations. 

Time Complexity for Counting Sort

The time complexity is given in general terms as,

    O(n+m) 

In the above case, m is 21. In practice, the new array is said to be created and all elements initialized to 0 in m time. The counts (number of occurrences for each unsorted value), are given to the new array in n time; where n is the total number of elements in the unsorted list (array). Each count that is more than 1 is done by incrementing, the number of times the value repeats in the unsorted list, as the unsorted list itself is scanned (from left to right).

Memory Space

Notice that in the above count array, all the counts of 0 are redundant. Though their spaces are redundant in memory, they have to be there. The counting sort takes unnecessary memory space in general. Nothing is normally done to avoid the redundant locations. 

Note: There is also space complexity, but that is not addressed in this tutorial (lesson).

Coding in PHP

A Counting Sort function in the PHP computer language is as follows: 

<?php
    function countingSort($arr, $n, $max) {
        global $arr;
    
        //m time complexity
        $count = array_fill(0, $max+1, 0);

        //n time complexity
        for ($i = 0; $i < $n; $i++) {
            $count[$arr[$i]] = $count[$arr[$i]] + 1;  //add 1 for each occurrence of same value
        }

        //optional additional m time complexity
        $k = 0;  //index for given array
        for ($i=0; $i < $max+1; $i++) {
            if ($count[$i] != 0) {
                for ($j=0; $j < $count[$i]; $j++) {  //accounting for repetition where necessary
                    $arr[$k] = $i;  //putting back sorted value into given array
                    $k++;
                }
            }
        }
    }

n is the number of elements in the given array. max is the maximum element in the given array.

A suitable PHP calling function code segment is as follows:

    $arr = [16, 20, 12, 10, 18, 8, 12, 18, 12, 14];
    countingSort($arr, 10, 20);
    for ($i=0; $i < 10; $i++)
        echo $arr[$i] . ', '; 
    echo "\n"; 

The output is:

    8 10 12 12 12 14 16 18 18 20

Merge Sort

Many computer languages today have a general-purpose sort() function in their library. This function is used for commercial applications. Many programmers use the sort function provided by the language library, whenever they need a sort function.

The mergesort program, written normally, is comparable (in terms of speed) to the sort() function provided by PHP in its algorithm library. Merge-sort is also a general purpose commercial program.

This section of the tutorial (lesson) explains how to write the mergesort program in the PHP language.

Divide-and-Conquer Algorithm, in its Broad Sense

In its broad sense, the array of elements is divided into two halves: the left half and the right half. If the total number of elements to be sorted is odd, then the left half is bigger than the right half, by 1 unit, as a result of integer division. Otherwise, both halves are of the same length. The two halves are then merged while sorting to form one sorted array. The merging/sorting is conquering. Consider the following characters to be sorted: 

    Q W E R T Y U I O P

Dividing this set of alphabetic characters into two halves, gives:

    Q W E R T        Y U I O P 

A sub array is called a run. So the left sub array, “Q W E R T” is a run and the right sub array, “Y U I O P” is also a run. A run can only finally consist of one element.

Merging/sorting (conquering) both halves into one set gives: 

    E I O P Q R T U W Y

The code segment to divide by 2 is: 

    $mid = (int)($n / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);

This uses integer division. So, the whole number part of the result is taken. With this, if the total number of elements in the set is odd then the left half would be bigger than the right half, by 1 unit for zero based indexing.

Practical Mergesort Divide-and-Conquer Algorithm

A mergesort operates conceptually in the following way:

1) Divide the unsorted set into N subsets (runs), where each has one element. Note that a set with only one element is considered sorted.

2) Repeatedly merge subsets to obtain new sorted subsets, until only one subset is left, which is the whole sorted set. 

The set, {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'}, is used to explain how mergesort is achieved practically, in this section.

The set is divided into the two sets:

    {'Q', 'W', 'E', 'R', 'T'} and {'Y', 'U', 'I', 'O', 'P'} 

The above two subsets are each, further divided into two, to have: 

    {'Q', 'W', 'E'} and {'R', 'T'} and {'Y', 'U', 'I'} and {'O', 'P'}

Note that for each new division here, the left subset is longer than the right subset by one unit. 

The above subsets are each, further divided into two, to have: 

    {'Q', 'W'} and {'E'} and {'R'} and {'T'} and {'Y', 'U'} and {'I'} and {'O'} and {'P'}

Here, some subsets cannot be divided any more because they each consists of one element. After that, division of the more than one length subsets above, leads to:

    {'Q'} and {'W'} and {'E'} and {'R'} and {'T'} and {'Y'} and {'U'} and {'I'} and {'O'} and {'P'} 

From here, {'Q'} and {'W'} will be sorted and merged into {'Q', 'W'}. {'E'} and {'R'} will be sorted and merged into {'E', 'R'}. {'T'}. {'Y'} will be sorted and merged into {'T', 'Y'}. {'U'} and {'I'} will be sorted and merged into {'I', 'U'}. {'O'} and {'P'} will be sorted and merged into {'O', 'P'}.

Next: {'Q', 'W'} and {'E', 'R'} will be sorted and merged into {'E', 'Q', 'R', 'W'}. {'T', 'Y'} and {'I', 'U'} will be sorted and merged into, {'I', 'T', 'U', 'Y'}. At this stage, {'O', 'P'} is not joined with any previous subsets of two.

The next stage: {'E', 'Q', 'R', 'W'} and {'I', 'T', 'U', 'Y'} are sorted and merged into {'E', 'I', 'Q', 'R', 'T', 'U', 'W', 'Y'}. At this stage, {'O', 'P'} again is not joined with any of the previous subsets.

The last stage: {'E', 'I', 'Q', 'R', 'T', 'U', 'W', 'Y'} and {'O', P'} are sorted and merged into 

        {'E', 'I', 'O', 'P', 'Q', 'R', 'T', 'U', 'W', 'Y'}.

The unsorted set has been sorted. 

Coding mersort in PHP

A complete mergesort program is as follows: 

<?php

function mergeSort(array $arr): array
{
    $n = count($arr);

    // Base case: if the array has 0 or 1 element, it's already sorted
    if ($n <= 1) {
        return $arr;
    }

    // Divide the array into two halves
    $mid = (int)($n / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);

    // Recursively sort both halves
    $left = mergeSort($left);
    $right = mergeSort($right);

    // Merge the sorted halves
    return merge($left, $right);
}

function merge(array $left, array $right): array
{
    $result = [];
    $leftIndex = 0;
    $rightIndex = 0;

    // Compare elements from both arrays and add the smaller one to the result
    while ($leftIndex < count($left) && $rightIndex < count($right)) {
        if ($left[$leftIndex] <= $right[$rightIndex]) {
            $result[] = $left[$leftIndex];
            $leftIndex++;
        } else {
            $result[] = $right[$rightIndex];
            $rightIndex++;
        }
    }

    // Add any remaining elements from the left array
    while ($leftIndex < count($left)) {
        $result[] = $left[$leftIndex];
        $leftIndex++;
    }

    // Add any remaining elements from the right array
    while ($rightIndex < count($right)) {
        $result[] = $right[$rightIndex];
        $rightIndex++;
    }

    return $result;
}

// Example usage:
$testArray = ['Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'];
echo "Original Array: " . implode(", ", $testArray) . "\n";

$sortedArray = mergeSort($testArray);
echo "Sorted Array: " . implode(", ", $sortedArray) . "\n";
?>

The output is:

Original Array: Q, W, E, R, T, Y, U, I, O, P
Sorted Array: E, I, O, P, Q, R, T, U, W, Y

Merge Sort Time Complexity

Time complexity is the relative running time of a program. It can be seen as the number of the main operations of a program.

Integer Division by Two

Integer division is necessary when doing a merge sort. 

Now,

    6 ÷ 2 = 3 R 0 

    7 ÷ 2 = 3 R 1

When an even number is divided by 2, the remainder is 0. When an odd number is divided by 2 the remainder is 1. With integer division, the whole number is taken and the remainder is abandoned. 

Merge Sort Algorithm

Merge Sort is a divide and conquer sorting algorithm. A simplified explanation is as follows: In this algorithm, the unsorted list is divided into two halves using the integer division. Each of the halves is further divided into two halves again using the integer division. This division continues until the list is considered as single separate elements.

Beginning from the left, the consecutive elements are then paired in a sorted manner. The paired elements are then paired again in a sorted form. This grouping by pairs continues until the whole list is reformed and sorted. 

Linear and Logarithmic Time Complexity

Consider the following code in the PHP language:

        for ($i=0; $i < $8; $i++) {
            $k = $i + 1;
            echo $k . ' '; 
        }
        echo "\ns"; 

The output is:

    1 2 3 4 5 6 7 8 

The code is a for-loop (ignoring the print statement just after the for-loop). It prints the integers from 1 to 8, for a total of 8 numbers. The content of the body of the for-loop is:

            $k = $i + 1;
            echo $k . ' '; 

These two statements are considered as one main operation in this situation. There are 8 operations, with the 8 iterations. Let n be 8. This is a linear time complexity and it is written as follows: 

    O(n)

where n is the possible maximum number of operations. This is the Big-O notation. It begins with O in uppercase and followed by parentheses. Inside the parentheses is the maximum possible number of operations. 

Consider now the following code where out of 8 numbers, 3 numbers are printed:

        for ($i=0; $i<8; $i++) {
            $k = $i + 1;
            echo $k . ' '; 
            if ($k == 3) break;
        }
        echo "\n"; 

The output is:

    1 2 3 

The code is a for-loop (ignoring the print statement just after the for-loop). It prints the integers from 1 to 3 out of 8 numbers. The content of the body of the for-loop is:

            $k = $i + 1;
            echo $k . ' '; 
            if ($k == 3) break;

Still, these three statements are considered as one main operation in this situation. There are 3 main  operations out of 8, with three iterations.

Now,

        8 = 2³

    => 3 = log₂(8) 

So, the number of main operations carried out by the previous code is 3 (out of 8).

Let n be 8. This is a logarithmic time complexity and it is written as:

    O(log₂n) 

where (log₂ n) means 3 for the above code.

Example of Unsorted and Sorted List

An example of an unsorted list is as follows: 

    P    V    D    Q    S    X    T    B

There are eight elements in the list. When this list is sorted, it becomes: 

    B    D    P    Q    S    T    V    X

Counting the Number of Main Operations in the Merge Sort 

The following list:

    P    V    D    Q    S    X    T    B   

is used to count the number of the main operations in merge sort.

The integer division by two gives the following result: 

    P    V    D    Q        S    X    T    B

This is one operation. Another division of both parts by two gives the following result: 

    P    V        D    Q    S    X        T    B

These are three operations so far (one plus two). Another division of each new part by two gives the following result: 

    P        V        D        Q        S        X        T        B

These are seven operations so far (three plus four). The list of the eight elements are now considered as eight separate elements with a total of seven operations so far. The next phase is to pair while (arranging) sorting, beginning from the left. So, the next result is: 

    P    V        D    Q        S    X        B    T

There are two changes in position for the last pair. Two changes are two operations. This makes a total of nine operations so far (seven plus two). 

The pairing and sorting continues, always beginning from the left to give the following result:

    D    P    Q    V        B    S    T    X 

Each of these two groups had four changes in position, making eight operations. There are seventeen operations so far (nine plus eight). The pairing and sorting continues and lastly, to give the following result:

    B    D    P    Q    S    T    V    X 

There are seven changes in position here, making seven operations. This makes twenty-four operations (seventeen plus seven) for the complete sorting.

Time Complexity Proper, for Merge Sort

The previous counting (illustration) is used to quote the time complexity for the mergesort. There are twenty-four operations. 

    24 = 8 x 3

That is: 

    24 = 8 x log₂(8)

because log₂(8) is 3. 

Let 8 be n. With that, the mergesort time complexity is given by:

    O(n.log₂n) 

where the dot means multiplication.

In practice, out of 8 elements, the number of operations is approximately 24 or 24. 

Conclusion for Mergesort Time complexity

The mergesort is a particular divide and conquer sorting algorithm. It is a very efficient sorting algorithm. Its time complexity is very satisfactory, compared to the other sorting algorithms. Its time complexity is:

    O(nlog₂n) 

Note: The number of operations must not necessarily be exactly n.log₂n . However, it can be slightly less.

Coding mergesort needs recursive functions. It is not too difficult to code it once the algorithm has been understood. 

General Remark

In sorting, the term “non-descending” is normally used instead of ascending, to allow for duplicate values.  The term “ascending” has been used above, for easy understanding. 

Thanks for reading. Now go ahead and practice the next four tasks; solutions and their explanations are given.