Bubble Sort Algorithm

Bubble Sort algorithm is a sorting technique in which we choose the smallest element from the array and keep that element at first position, then we choose the next smallest element in remaining part of array, we keep that at 2nd position, then we choose next element for 3rd position and we continue these steps till the last element, and finally we will have a sorted Array.

Average Case Complexity : O(n^2)
Worst Case Complexity : O(n^2)

Basic Idea : 

For every position in array starting with 0th position, find the smallest element in list (from current position to end), and place the element at the current position, continue this till end of array is reached.

Java Code : 

package Sorting;

public class BubbleSort {

      // method to be called to Apply sort, method returns a sorted array

            public static int[] Sort(int[] array){

                  //for every element from 0 to length-1

                  for(int i = 0; i<array.length; i++){

                        int minIndex = i;

                        //find min value element in array from position i to length-1

                        for(int j=i+1; j<array.length; j++){

                              if(array[j] < array[minIndex]){

                                    minIndex = j;

                              }

                        }

                        //if min value element is not at position i

                        //swap the min value element with the element at i

                        if(minIndex!=i){

                              int temp = array[minIndex];

                              array[minIndex] = array[i];

                              array[i] = temp;

                        }

                  }// end for loop

                  return array;

            }// end sort method

}

Radix Sort Algorithm

Radix sort is a Radix-Based sorting algorithm. This sorting algorithm is useful when number of elements are very large as compared to the number of digits used to represent those elements of the array.

Average Case Complexity : O(b n)
Worst Case Complexity : O(b n)

Basic Idea : 

we sort all the numbers according to the unit place digit, then further we sort the same list according to the tens place digit and we continue doing this and finally after we sort the array as per left-most digit, we will have a sorted array.

Note:- Its important to start the sorting from least significant digit to most significant digit, and NOT the other way to get correct results.

Java Code : 

package Sorting;

import java.util.ArrayList;

public class RadixSort {

      // method to be called to Apply sort, method returns a sorted array

      public static int[] Sort(int[] array){

           

            //find maximum value element in array

            int max = getMaxNum(array);

            //find the number of digits in max number

            int digitCounts = getNumberOfDigits(max);

            //initialize sortIndex

            int SortIndex = 1;

           

            //Continue below procedure till digit count becomes 0

            while(digitCounts !=0){

                 

                  //Initialize radixBucket

                  ArrayList[] RadixBucket = new ArrayList[10];

                  for(int i = 0; i<10; i++){

                        ArrayList<Integer> list = new ArrayList<Integer>();

                        RadixBucket[i] = list;

                  }

                  //for every element of input array

                  for(int i= 0; i<array.length; i++){

                        int number = array[i];

                        int index = 0;

                        //calculate index i.e the digit at SortIndex's place

                        for(int j=SortIndex; j!=0; j--){

                              index = number%10;

                              number = number/10;

                        }

                        //fill the element in Bucket at calculated index

                        RadixBucket[index].add(array[i]);

                  }

                  //fill elements back in array in the same order they are filled in Buckets

                  for(int i=0,j=0; j<10; j++){

                        if(RadixBucket[j].size() != 0){

                              for(int k=0; k<RadixBucket[j].size() ; k++){

                                    array[i] = (int) RadixBucket[j].get(k);

                                    i++;

                              }

                        }

                  }

                  //Increase SortIndex and decrease digitCounts

                  SortIndex++;

                  digitCounts--;

            }//repeat the procedure till digitCounts become 0

           

            //now the array is sorted, return the array

            return array;

      }

     

      //method to find the max value element in array

      private static int getMaxNum(int[] array){

            int num = array[0];

            for(int i = 1; i<array.length; i++){

                  if(array[i] > num){

                        num = array[i];

                  }

            }

            return num;

      }

      //method to find Number of digits in given number

      private static int getNumberOfDigits(int num){

            int numDigits = 0;

            do{

                  num = num/10;

                  numDigits++;

            }while(num != 0);

           

            return numDigits;

      }

}

Merge Sort Algorithm

Merge Sort is a sorting technique, it follow divide and conquer approach. Merge sort algorithm is highly efficient Considering time complexity, but it uses extra memory space which is why quick sort is many times preferred over it.

Average Case Complexity : O(n logn)
Worst Case Complexity :  O(n logn)

Basic Idea :

we divide the array into two parts, we sort the divided parts individually and then we combine the two sorted parts.

In the diagram above red blocks denotes the two divided unsorted arrays, Green denoted the sorted sub arrays and their merge results. Note- arrays having size 1 are considered sorted.

Pseudo code : 

1) Devide array in leftArray and RightArray
2) Sort leftArray
3) Sort RightArray
4) Combine leftArray and RightArray and return the result.
    01) Initialize Combined array
    02) Initialize position counters for leftArray (k) and RightArray (l)
    03) If Both leftArray and RightArray has elements left in them
               Compare the two elements and add the smaller element in Combined array at
               current location
               Update the location counters
          Else if only leftArray has elements
                Add the leftArray elements in Combined array at current location
                Update the location counters
          Else if only RightArray has elements
                Add the RightArray elements in Combined array at current location
                Update the location counters
    04) return Combined array


Java Code : 

package Sorting;

public class MergeSort {

      // method to be called to Apply sort, method returns a sorted array

      public static int[] Sort(int[] array){

            return Devide(array);

      }

     

      //Devide array, sort its parts, combine and return result

      private static int[] Devide(int[] array){

            // if array has more than one element

            if(array.length > 1){

                  int newArrayLength = array.length/2;

                  //devide array into leftArray and RightArray

                  int[] leftArray = new int[newArrayLength];

                  int[] RightArray = new int[array.length - newArrayLength];

                 

                  //fill elements in leftArray

                  for(int i = 0; i< leftArray.length; i++){

                        leftArray[i] = array[i];

                  }

                  //fill elements in RightArray

                  for(int i = 0; i< RightArray.length; i++){

                        RightArray[i] = array[i+newArrayLength];

                  }

                  //sort left part

                  leftArray = Devide(leftArray);

                  //sort right part

                  RightArray = Devide(RightArray);

                  //Combine the two sorted parts and return the result

                  return Combine(leftArray, RightArray);

            }

            //if array size = 1, consider it sorted and return it

            return array;

           

      }

      //Combine two sorted array and return sorted combined result

      private static int[] Combine(int[] leftArray, int[] rightArray){

            //Initialize the Combined array

            int[] Array = new int[leftArray.length + rightArray.length];

            //Initialize k and l counters for leftArray and RightArray

            int k = 0;

            int l = 0;

            //Run loop to fill Array

            for(int i = 0; i<Array.length; i++){

                  //if both leftArray and RightArray has elements in it

                  if(k<leftArray.length && l<rightArray.length){

                        //Compare the elements and save the smaller in Array

                        //at "i" position

                        if(leftArray[k] < rightArray[l]){

                              //if element of leftArray is smaller

                              Array[i] = leftArray[k]; //save element from leftArray

                              k++; //increment the counter of leftArray

                        }else{

                              Array[i] = rightArray[l]; //save element from RightArray

                              l++; //increment the counter of RightArray

                        }

                  }else if(k<leftArray.length){ //if only leftArray has elements

                        Array[i] = leftArray[k];//save element from leftArray

                        k++;//increment the counter of leftArray

                  }else{

                        Array[i] = rightArray[l]; //if only RightArray has elements

                        l++;//increment the counter of RightArray

                  }

            }

            return Array; //return the merged sorted array

      }

     

}

Quick Sort Algorithm

Quick sort is a sorting technique, widely used for sorting. It is a Divide-and-conquer approach.
The quick sort algorithm is widely used as it is space efficient, i.e it does not require additional storage space and it is sufficiently fast and quick algorithm.

Average Case Complexity :  O(n logn)
Worst Case Complexity : O(n^2)

Basic Idea :

We randomly choose a pivot element (any random element in array) then we divide the input array into three parts.
1) Left array - having all elements smaller than pivot.
2) Pivot Element
3) Right array - having all elements greater than pivot.

Then we repeat the same procedure of choosing pivot and dividing in parts and then re-applying the steps in sub parts, till we get the sub-arrays of zero size.

Pseudo code :

1) p  <--  Partition(start,end)
   01) pivot  <--  Array[start + (end-start /2)]
   02) i  <--  start
   03) j  <--  end
   04) run for loop from start to end
         repeat i <--  i+1 until Array[i] > pivot
         repeat j <--  j-1 until Array[j] < pivot
         if i < j
         then exchange Array[i] and Array[j]
         else return j

2) applyQuickSort(start, p-1)
3) applyQuickSort(p+1, end)

Java Code :

package Sorting;

public class QuickSort {

                // private static member to store input array

                private static int[] Array;

                // method to be called to Apply sort, method returns a sorted array

                public static int[] Sort(int[] array){

                                Array = array;

                                applyQuickSort(0, Array.length-1);

                                return Array;

                }

                //method quick sort which apply quicksort in input array from start to end.

                private static void applyQuickSort(int start, int end){

                                // find position such that element at this place has

                                // (all elements smaller to it at its left)  and (all elements larger to it at its right).

                                int partitionIndex = Partition(start, end);

                                // now if left divided part has some elements, apply Quick sort in that part.

                                if(start < partitionIndex-1){

                                                applyQuickSort(start, partitionIndex-1);

                                }

                                // and if right divided part has some elements, apply Quick sort in that part.

                                if(partitionIndex+1 < end){

                                                applyQuickSort(partitionIndex+1, end);

                                }

                }

                // method to partition a given subarray (Specified by start and end index),

                // into 3 parts (unsorted left array, sorted element, unsorted right array).

                public static int Partition(int Start, int end){

                                int pivot = Array[(Start + (end-Start)/2)]; //initialize pivot

                                int i = Start; //initialize i

                                int j = end;// initialize j

// run loop from start to end-1

                                for(int loop = Start; loop<end-1; loop++ ){

                                                while(Array[i] < pivot){

                                                                i++;

                                                }

                                                while(Array[j] > pivot){

                                                                j--;

                                                }

                                                //if i<j swap Array[i] and Array[j]

                                                if(i<j){

                                                                int temp = Array[i];

                                                                Array[i] = Array[j];

                                                                Array[j] = temp;

                                                }else{

                                                                break; //break for loop

                                                }

                                }//end for loop

                                return j;

                }//end partition method

}//end class