Types of Sorting Algorithm and Example.

Bucket Sort

• Suppose we need to sort an array of positive integers {3,11,2,9,1,5}. A bucket sort works as follows: create an array of size 11. Then, go through the input array and place integer 3 into a second array at index 3, integer 11 at index 11 and so on. We will end up with a sorted list in the second array.
• We immediately see two drawbacks to this sorting algorithm. Firstly, we must know how to handle duplicates. Secondly, we must know the maximum value in the unsorted array. Thirdly, we must have enough memory - it may be impossible to declare an array large enough on some systems.
• The first problem is solved by using linked lists, attached to each array index. All duplicates for that bucket will be stored in the list. Another possible solution is to have a counter. As an example let us sort 3, 2, 4, 2, 3, 5. We start with an array of 5 counters set to zero.

0	1	2	3	4	5
0	0	0	0	0	0

• Moving through the array we increment counters:

0	1	2	3	4	5
0	0	2	2	1	1

• Next,we simply read off the number of each occurrence: 2 2 3 3 4 5.

Bubble Sort

• The algorithm works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm will be repeats the process until it makes a pass all the way through the list without swapping any items.

void bubbleSort(int ar[])
{

   for (int i = (ar.length - 1); i >= 0; i--)
   {
      for (int j = 1; j ≤ i; j++)
      {

              int temp = ar[j-1];
         if (ar[j-1] > ar[j])
         {
              ar[j-1] = ar[j];

   } } } }

              ar[j] = temp;

Example. 

• Here is one step of the algorithm. The largest element - 7 - is bubbled to the top:

7, 5, 2, 4, 3, 9

5, 7, 2, 4, 3, 9

5, 2, 7, 4, 3, 9

5, 2, 4, 7, 3, 9

5, 2, 4, 3, 7, 9

5, 2, 4, 3, 7, 9

Selection Sort

• The algorithm works by selecting the smallest unsorted item and then swapping it with the item in the next position to be filled.
• The selection sort works as follows: you look through the entire array for the smallest element, once you find it you swap it (the smallest element) with the first element of the array. Then you look for the smallest element in the remaining array (an array without the first element) and swap it with the second element. Then you look for the smallest element in the remaining array (an array without first and second elements) and swap it with the third element, and so on. 

void selectionSort(int[] ar){

   for (int i = 0; i ‹ ar.length-1; i++)
   {
      int min = i;

      for (int j = i+1; j ‹ ar.length; j++)
            if (ar[j] ‹ ar[min]) min = j;
      int temp = ar[i];

} }
      ar[i] = ar[min];

      ar[min] = temp;

Example.

29, 64, 73, 34, 20, 

20, 64, 73, 34, 29, 

20, 29, 73, 34, 64 

20, 29, 34, 73, 64 

20, 29, 34, 64, 73 

Insertion Sort

• To sort ordered list of elements, we remove its entries one at a time and then insert each of them into a sorted part (initially empty):

void insertionSort(int[] ar)
{

   for (int i=1; i ‹ ar.length; i++)
   {

      while (j > 0 && ar[j-1] > index)
      int index = ar[i]; int j = i;

           j--;
      {
           ar[j] = ar[j-1];
      }

} }

      ar[j] = index;

Example. 

• The color a sorted part in green, and an unsorted part in black. Here is an insertion sort step by step. We take an element from unsorted part and compare it with elements in sorted part, moving form right to left.

29, 20, 73, 34, 64 

29, 20, 73, 34, 64 

20, 29, 73, 34, 64 

20, 29, 73, 34, 64 

20, 29, 34, 73, 64 

20, 29, 34, 64, 73 

Merge sort

• Merge-sort is based on the divide-and-conquer paradigm. It involves the following three steps:

1. Divide the array into two (or more) subarrays
2. Sort each subarray (Conquer)
3. Merge them into one (in a smart way!)

Example. 

Consider the following array of numbers

27  10  12  25  34  16  15  31

divide it into two parts

27  10  12  25            34  16  15  31

divide each part into two parts

27  10            12  25            34  16            15  31

divide each part into two parts

27       10       12       25       34       16       15       31



merge (cleverly-!) parts

10  27            12  25            16  34            15  31

merge parts

10  12  25  27                 15  16  31  34

merge parts into one

10  12  15  16  25  27  31  34

How do we merge two sorted subarrays? We define three references at the front of each array.

We keep picking the smallest element and move it to a temporary array, incrementing the corresponding indices.