Bubble, selection and insertion sort

Looks like this blog is becoming all about revising for a test, but it’s only going to be for Computer Science.

So, there are several techniques in sorting an array. We’re going to be discussing only three in this post, though:

1. Bubble sort
2. Selection sort
3. Insertion sort

First, we’re doing to discuss the technique behind each sort, and then present the C++ corresponding to each sort.

Like in my previous post, all C++ will correspond to the compiler Turbo C++ 3.0, released in 1991-92.

In addition, I’ve written all code on the spot (without actually running it), so please read all code carefully for mistakes. Write code that you think is right, and if you think the above code is wrong, please contact me and tell me (so I can fix it), and under no condition should you copy any code that you’re, even if partially, sure is (even partially) wrong.

Now let’s get to business. All sorts discussed are to arrange an array in ascending order. Suitable modifications can be made to arrange it in descending order.

1. Bubble sort #

In above image describes how bubble sort works. The algorithm is as follows:

1. Compare the first and second elements, the second and third elements, and so on till the end of the array.

2. Switch the two elements when those two elements are in descending order, in order to make them in ascending order.

3. At the end of one cycle, the largest element is the rightmost in the array. Repeat the previous two steps, but this time, exclude the last element.

4. The number of cycles is equal to the number of elements in the array.

The image shows one cycle (the first one, in this case).

And now the C++ code corresponding to bubble sort:

void bubbleSort(int A[], s) //(array, size)
{
    int i=0, j=0, temp=0;

    for(i=0; i<s; i++)
        for(j=0; j<=(s-1)-i; j++)
            if(A[i}>A[i+1])
            {
                temp = A[i];
                A[i] = A[i+1];
                A[i+1] = temp;
            }
}

2. Selection sort #

In this sort, the array is traversed and the smallest element is selected. It is then swapped with the first element. Then, the rest of the elements are traversed, and the largest among them is selected and swapped with the second element. This process continues as many number of times as there are elements in the array.

I won’t be discussing the algorithm for this, but will directly go into C++ code.

void selectionSort(int A[], s) //(array, size)
{
    int i=0, j=0, pos=0, min=0, temp=0;

    for(i=0; i<s; i++)
    {
        pos=i; min=A[i]; temp=A[i];

        for(j=i+1; j<s; j++)
            if(A[j]<min)
            {
                min=A[j];
                pos=j;
            }

        temp = A[i];
        A[i] = A[pos];
        A[pos] = temp;
    }
}

I think the procedure is pretty clear from the code.

3. Insertion sort #

There are few new concepts here. One is the use of a sentinel element. But before telling you why such an element is useful, let’s see the algorithm for insertion sort.

1. State of array: COMPLETELY UNSORTED.
   
   The array is traversed, and the smallest element is inserted at that location that would make the already-sorted part of the array remain sorted after the addition of this new element. At this step, the already-sorted part of the array is no part, so we keep a sentinel element that has the smallest possible value (ideally –∞) as the first element, so that there is a finite part of the array already sorted at any moment.
   
   State of the array: FIRST ELEMENT SORTED.

2. The unsorted part of the array is traversed, and the smallest element chosen here is inserted in the sorted part (currently having two sorted elements, one of which was the predefined sentinel element) so that the sorted part remains sorted, albeit with the addition of another element.

3. This process is continued as many number of times as there are elements in the array. In the last iteration, the last element is left. This is the largest element because all smaller elements have been inserted in the sorted part of the array, which is now all elements except this last one. This last element is chosen and inserted in its own place, to complete the sort.

Another use of the sentinel element is that when, in one of the iterations taking place, the smallest element of the unsorted part of the array is also the smallest element of the whole array (if proper mathematical treatment to this sort is given, it can be proved that the smallest element of the array will never remain in the unsorted part of the array after the first iteration), then it will be inserted in front of (i.e, just after) the sentinel element. Otherwise, we’d always have to check whether the we have reached one of the ends of the sorted part of the array separately, and in each iteration.

A useful tip for you

When you have to merge two sorted arrays into one sorted array, one way is to simply append one to the other, and then arrange both. But this doesn’t take advantage of the fact that both arrays are already individually sorted.

So a better way is to insert elements from the second array in appropriate places in the first array. But there is an even better way, that puts the array elements in the correct order while combining both of the arrays by element. What you do is aim to traverse through a number of elements equal to the sum of the number of elements of the two arrays to be merged. For the largest element in one array, check the element below it and the largest element in the other array. Put these three, in the correct order, in the blank array having that number of empty elements that is equal to the sum of the number of elements of the two arrays. Make the iterator (the thing that increases as the loop progresses) skip an appropriate number of increases, by directly increasing it by more than 1 inside the loop (make sure you account for the fact that the iterator will also be incremented by 1 in the next iteration of the loop).

Now, to the C++ code for insertion sort:

#include <limits.h> //needed for INT_MIN
//...
void insertionSort(int A[], int s) //(array, size [excluding sentinel element])
{
    int temp, j;
    A[0] = INT_MIN;

    for(int i=1; i<=s; i++)
    {
        temp = A[i];
        j = i-1;

        while(temp<A[j])
        {
            A[j+1] = A[j];
            j--;
        }

        A[j+1] = temp;
    }
}

Now, giving a sort-of animation for the above code is needed, in order to make one understand how it works. The execution of the code line by line needs to be shown alongside the status of all the variables. In other words, a dry run with “processing” needs to be shown. So here it is, below (it’s 5 minutes long, so you might just want to play it till you understand the concept well enough, though in the video I’ve sorted the whole array):

The above video was made in the form of a presentation in Keynote, and the total number of slides I had to manually make were 171. I really hope you derive benefit from it. Please share it with others if you think it’ll help them (even if only in the smallest way). Thanks in advance.

Well, I think that’s all I need to know for that test coming up tomorrow.