Data Structure : Sorting Algorithm

Sorting is indispensable part of data structure and algorithm .

After almost 3-4 years, I was studying sorting for last 1 week. In this blog, I will be covering basic sorting algorithms for people like me who have been out of touch.

There are 3 basic sorting algorithms

1. Bubble Sort
2. Selection Sort
3. Insertion Sort

Bubble Sort
This is simplest and slowest of all the sorting algorithms. Its simplicity is the reason, I have thought of explaining this first.
This sorting algorithm can be explained in three simple steps

• Compare two number
• If X > Y and X is left Y in list, swap them
• Move 1 step right

After first round of iteration through list of N values, highest value bubbles up in the N-th position.

Similarly, after second round of iteration through list of N-1 values, 2nd highest value bubbles up in the N-1 th position and so on. So, if size of the list is N, all the items are sorted after N-1 iteration.

Efficiency of Bubble sort

As you can see, if number of items is N, there are N-1 comparisons in first pass, N-2 comparisons in second pass and so on. Hence total number of comparisons to sort N number of items is

(N-1)+(N-2)+(N-3)+...+1 = N*(N-1)/2

If the data is random, swap is necessary half the time, so there will be about (N^2)/4 swaps.

Java Code block for Bubble Sort

public void bubbleSort() {

int out, in;

for(out=nElems-1; out>1; out--) 

    for(in=0; in<out; in++)

          if( a[in] > a[in+1] ) swap(in, in+1);

} // end bubbleSort() 

Selection Sort

Selection sort improves on bubble sort by reducing the number of swap. Number of comparison remains the same as the bubble sort. Steps to execute the selection sort are as follows

• Select left most index of unsorted list and marked it as MIN
• Pass through the unsorted list of items and store the poistion of any item in IN if the value of the item is less than value at position MIN
• Swap values at IN and MIN

After first round of iteration, lowest value item is selected and placed in 1st position. Similarly after second pass, second lowest value is selected and placed in 2nd position and so on. So, if size of the list is N, all the items are sorted after N-1 iteration.

Efficiency of Selection Sort

The selection sort perform the same number of comparison as the bubble sort: N*(N-1)/2. But there is lesser number of swap than Bubble sort.

Java Code block for Selection Sort

public void selectionSort() {
   int out, in, min;
   for(out=0; out<nElems-1; out++) {
       min = out;
       for(in=out+1; in<nElems; in++)
             if(a[in] < a[min] ) min = in;
             swap(out, min);
   } // end for(out)
} // end selectionSort() 

Insertion Sort

Insertion Sort is faster than Bubble sort and Selection sort in almost all cases, though the number of comparisons is same. This sorting has a concept of partial sorting. It assumes that all the items in the left of a marked position M is partially sorted, i.e. sorted among themselves. 

In Bubble sort and Selection sort, a group of data item is completely sorted at any given time; in insertion sort a group of data is partially sorted. Steps to implement insertion sort are as follows

• Select item in Mth position, M-1 items in left of the M is partially sorted
• Insert the selected item in (M-1) sorted items at correct position, shift the items in the left of M to right to make place for insertion
• Now items in left of M+1 is partially sorted, increment the value of M and repeat unless all the items in the list is placed.s

As you can see, items at 1st and 2nd place are sorted amoung themselves after first round and item at poistions from 1-3 are partailly sorted after second round. So after N-1 round, all the N items are sorted.

Efficiency of Insertion sort

On the first pass it compares maximum 1 item, on second it comares maximum 2 and so on up to maximum comparison of N-1 on last pass. Hence total number of comparison is

1+2+3+4.... + (N+1) = N(N-1)/2

Number of copies to move and insert the data is almost same as numbers of comparison. However since, copying data takes less time than swap, so it is twice as fast as Bubble sort and faster than Selection sort for random data.

For the data that is already sorted or almost sorted this Sorting technique is much better. However for inversely sorted data, this is not better than Bubble Sort as every possible Shift and Comparison is carried out.

Java Code for Insertion Sort

public void insertionSort() {
    int in, out;
   for(out=1; out<nElems; out++) {

       long temp = a[out];
       in = out;
       while(in>0 && a[in-1] >= temp) // until one is smaller,

       {
                a[in] = a[in-1]; // shift item right,

                --in;
        }
    a[in] = temp; } // end for
} // end insertionSort()