Selection Sort

    #include <iostream>
    using namespace std;
    
    void selectionSort(char arr[], int N) {
        int counter = 0;
        for (int i = 0; i < N; i++) {
            int minElemIndx = i;
            for (int j = i+1; j < N; j++) {
                if (arr[j] < arr[minElemIndx]) {
                    minElemIndx = j;
                }
                counter+=1;
            }
            //swapping code
            char temp = arr[minElemIndx];
            arr[minElemIndx] = arr[i];
            arr[i] = temp;
        }
        
        cout << counter << endl;
    }

    int main(int argc, char **argv)
    {
        char ar[] = {'R', 'X', 'F', 'S', 'U', 'Z', 'V', 'J'};
                
        selectionSort(ar, 8);
        for (int i = 0; i < 8; i++) 
            cout << ar[i] << ", ";
        cout << endl; 

        return 0;
    }

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 C++

    #include <iostream> 
    #include <vector>
    using namespace std;

    void insertionSort(vector<char> &A) {
        int n = A.size();
        
        for (int i=1; i<n; i++) {
            if (A[i] < A[i-1]) {    //first comparison
                char temp = A[i];
                int 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;
            }
        }
    }

    int main(int argc, char **argv) 
    {
        vector<char> A = {'Z', 'J', 'V', 'S', 'U', 'R', 'X', 'F'};
    
        insertionSort(A);

        for (int i=0; i<A.size(); i++)
            cout << A[i] << ' ';
        cout << endl;

        return 0; 
    }

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 C++

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

    #include <iostream>
    using namespace std;

    void countingSort(int arr[], int n, int max) {
        //m time complexity
        int count[max+1];
        for (int i = 0; i< max+1; i++)
            count[i] = 0;

        //n time complexity
        for (int 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
        int k = 0;  //index for given array
        for (int i=0; i<max+1; i++) {
            if (count[i] != 0) {
                for (int 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 C++ main() function is as follows:

    int main(int argc, char **argv)
    {
        int arr[] = {16, 20, 12, 10, 18, 8, 12, 18, 12, 14};
        countingSort(arr, 10, 20);
        for (int i=0; i<10; i++)
            cout << arr[i] << ", ";
        cout << endl;

        return 0;
    }

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 C++ 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 C++ language.

Divide-and-Conquer Algorithm, in its Broad Sense

In its broad sense, the array of elements are 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 statement to divide by 2 is: 

    int iMiddle = (iBegin + iEnd) / 2;

This is 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. iMiddle is the index for the middle element. 

For the above statement and the set, {‘Q’, ‘W’, ‘E’, ‘R’, ‘T’, ‘Y’, ‘U’, ‘I’, ‘O’, ‘P’}, iBegin = 0, iEnd = 10 (the number of elements in the list), iMiddle = 5. This is from (0+10)/2 = 5. This makes iMiddle 5, corresponding to the sixth element, ‘Y’, for the unsorted list. Note that iEnd here is 10 and not 9 as might be expected with other algorithms. [iMiddle] being equal to the sixth element is also exceptional here. With integer division, any fraction is thrown away. Though the last index is 9 and iEnd = 10 at the beginning, the iteration will never reach 10.

The code to merge/sort (conquer) is: 

Practical Mergesort Divide-and-Conquer Algorithm

The whole mergesort program can be written top-down or bottom-up. In this tutorial (lesson), the program is written, top-down.

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. 

With these two points, a given unsorted set is divided into two runs. Each of these two runs are recorded in memory for merging/sorting together, but not merged or sorted yet. Each run again on either side, is divided into two. The consecutive pairs of runs are recorded for merging/sorting together, but not merged or sorted still yet. This division into two and recording for merging/sorting of consecutive pairs are repeated until there is only one element per run.

The recording into memory for merging/sorting together of consecutive runs is done by calling the above sorting code recursively. 

When the division has reached the state of single element runs, the merging/sorting functions recorded in memory are called in reverse order in which they were recorded. It is one merge/sort function that was recorded in memory many times with different arguments. Consecutive pairs of single elements are first sorted, merging at the same time. The sorting and merging of consecutive runs continue until the whole set is sorted. So, the sorting is not really on the original arrangement of elements as was presented originally (as it is presented in theory).

In C++, there is a need for a second array, whose length is as long as the given array. Initially, all the elements for this second array has to be made, the default value of the data type. The elements of the given array are sorted into this second array. Then copied back to the given array, overriding the unsorted elements. 

For characters, this second array can be created and initialized as follows:

    char P[] = {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'};    //given array
    int sz = sizeof(P)/sizeof(P[0]);
    char Q[sz];    //second array
    for (int i=0; i<sz; i++) 
        Q[i] = ' ';

Note that the default values for array Q elements are not really necessary for the complete mergesort program as they will still be overridden by the elements of interest. Declaring array Q with its size, sz would still suffice.

The set, {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'}, is used to explain how mergesort is achieved practically, in this section. Giving array Q default values has been explained in this tutorial as extra knowledge. 

The set is divided into the two sets:

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

The above merging/sorting code is called as a function but sorting and merging do not take place. In the real program, the sorting and merging of these two runs are recorded in memory, first. The sorting and merging will not ultimately necessarily be done on these two particular arrangement of characters.

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 merging/sorting code is called as a function, for consecutive pairs of these new subsets. But sorting and merging does not take place immediately. The sorting and merging of these consecutive pairs of runs are recorded in the computer’s memory. The sorting and merging will not ultimately, necessarily be done, on the particular arrangement of characters of these consecutive pairs of runs.

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'}

The sorting and merging of consecutive pairs is recorded. 

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'} 

The sorting and merging of consecutive pairs is recorded.

The sorting and merging function is coded in a recursive manner. And so, it will be called in the reversed order, for the number of times, it was recorded. 

So, {'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'}. The above merge and sort function is used here; and it is used throughout.

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 above merge and sort function has been used here and is used throughout. 

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 C++

The complete program is as follows (the reader can really understand it, if he/she already understands recursive function in C++) :

Complete Practical Program for Mergesort

A complete mergesort program is as follows: 

    #include <iostream>
    using namespace std;
    
    void topDownMerge(char Q[], int iBegin, int iMiddle, int iEnd, char P[]) {
        int i = iBegin;
        int j = iMiddle;
        
        // While there are elements in the left or right runs...
        for (int k = iBegin; k < iEnd; k++) {
            // If left run head exists and is <= existing right run head.
            if (i < iMiddle && (j >= iEnd || P[i] <= P[j])) {
                Q[k] = P[i];
                i = i + 1;
            } else {
                Q[k] = P[j];
                j = j + 1;
            }
        }
    }
        
    void topDownSplitMerge(char Q[], int iBegin, int iEnd, char P[]) {
        if (iEnd - iBegin <= 1)
            return;    //one compound statement
            
        int iMiddle = (iBegin + iEnd) / 2;
        
        topDownSplitMerge(P, iBegin, iMiddle, Q); 
        topDownSplitMerge(P, iMiddle, iEnd, Q);

        topDownMerge(Q, iBegin, iMiddle, iEnd, P);
    }
    
    void copyArray(char P[], int iBegin, int iEnd, char Q[]) {
        for (int i = iBegin; i<iEnd; i++)
        Q[i] = P[i];
    }

    void topDownMergeSort(char P[], char Q[], int N) {
        copyArray(P, 0, N, Q);        // P[] is copied to Q[] once
        topDownSplitMerge(P, 0, N, Q);
    }
    
    int main(int argc, char **argv)
    {
        char P[] = {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'};
        int sz = sizeof(P)/sizeof(P[0]);
        char Q[sz];
        for (int i=0; i<sz; i++) 
            Q[i] = ' ';
        topDownMergeSort(P, Q, sz);

        for (int i=0; i<sz; i++) 
            cout << P[i] << ' ';
        cout << endl;

        return 0;
    }

The main() function creates the array Q, of the length of array P, which would have the unsorted characters initially. All the elements of Q are initialized to ' '. 

The mergesort code consists of the four functions: topDownMerge(), topDownSplitMerge(), copyArray() and topDownMergeSort(). The four functions are called beginning with, topDownMergeSort() in the C++ main() function.

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 C++ language:

        for (int i=0; i<8; i++) {
            int k = i + 1;
            cout << k << ' ';
        }
        cout << endl;

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:

            int k = i + 1;
            cout << 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 (int i=0; i<8; i++) {
            int k = i + 1;
            cout << k << ' ';
            if (k == 3) break;
        }
        cout << endl;

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:

            int k = i + 1;

            cout << 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.