java Sorting Algorithm

Selection Sort-

• in place algorithm
• O(n²)  time complexity - quadratic
• it will take 100 steps to sort 10 items, 10,000 steps to sort 100 items , 1,000,000 steps to sort 1000 items.
• Doesn't require as much swapping as bubble sort
• unstable algorithm

Ø  Devide array into sorted and unsorted part
Ø  Find smallest number in unsorted part
Ø  Swap it with first number in unsorted part
ØAdd the first number from unsorted part to the end of sorted part

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

                  //"i points at the first number behind the wall"

                  //we need to fetch smallest number in unsorted part and swap it with first number of unsorted part(behind wall) move the imaginary wall now will be i=1,2..n

                  int indexOfSmallest=i;

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

                        if(input[j]<input[indexOfSmallest]){

                              indexOfSmallest=j;

                        }

                  }

                  //swap

                  int temp =input[i];

                  input[i]=input[indexOfSmallest];

                  input[indexOfSmallest]=temp;

                 

            }

Complete code:

package algorithm.sorting;

public class Selection {

public static void selectionSort(int[] input) {

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

//"i points at the first number behind the wall"
//we need to fetch smallest number in unsorted part and swap it with first number of unsorted part(behind wall) move the imaginary wall now will be i=1,2..n
int indexOfSmallest=i;

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

if(input[j]<input[indexOfSmallest]){

indexOfSmallest=j;

}
}
//swap
int temp =input[i];
input[i]=input[indexOfSmallest];
input[indexOfSmallest]=temp;

}

System.out.println("sorted array is**************");
System.out.println(input);

}


public static void main(String args[]) {
int[] array=new int[]{2,1,6,5,1,9,2,18,12,4,12,4,1};

//calling method

Selection.selectionSort(array);
for(int x:array){
System.out.println(x);
}


}
}

}     
    Bubble sort

• in place algorithm
• O(n²)  time complexity - quadratic

Let the Biggest number “bubble” to end of an Array

         ü  Compare two number next to each other

      ü  If the first one is smaller we move to the next two numbers

      ü  If the first one is bigger we swap the first number with second then move on

Repeat step until the array is sorted

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

                  for(int j=0;j+1<arr.length;j++){

                        if(arr[j]>arr[j+1]){

                              int temp=arr[j];

                              arr[j]=arr[j+1];

                              arr[j+1]=temp;

                        }

                  }

            }

Merge Sort

 Recursively split until each array has only one number

 Merge these parts

Best, average and worst case time complexity: O(nlogn)
independent of distribution of data.

 public static void mergeSort(int[] input, int from, int to) {

            if (from < to) {

                  int middle = (from + to) / 2;

                  mergeSort(input, from, middle);

                  mergeSort(input, middle + 1, to);

                  merge(input, from, middle, to);

                                                                                  //System.out.println("after merge the                                             array is "+input);

                 

                                          }

           

                                           }

      public static void merge(int[] input, int from, int middle, int to) {

            int leftLength = middle - from + 1;

            int rightLength = to - middle;

            int[] left = new int[leftLength + 1];

            int[] right = new int[rightLength + 1];

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

                  left[i]=input[from+i];

            }

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

                  right[i]=input[middle+i+1];

            }

            left[leftLength]=Integer.MAX_VALUE;

            right[rightLength]=Integer.MAX_VALUE;

            int leftPointer=0;

            int rightPointer=0;

            for(int i=from ;i<=to;i++){

                  if(left[leftPointer]>right[rightPointer]){

                        input[i]=right[rightPointer];

                        rightPointer++;

                  }

                  else{

                        input[i]=left[leftPointer];

                        leftPointer++;

                  }

            }

           

      }



 Complete Code

  package algorithm.sorting;

public class MergeSort {
public static void mergeSort(int[] input, int from, int to) {
if (from < to) {
int middle = (from + to) / 2;
mergeSort(input, from, middle);
mergeSort(input, middle + 1, to);
merge(input, from, middle, to);
//System.out.println("after merge the array is "+input);

}

}

public static void merge(int[] input, int from, int middle, int to) {
int leftLength = middle - from + 1;
int rightLength = to - middle;
int[] left = new int[leftLength + 1];
int[] right = new int[rightLength + 1];
for (int i = 0; i < leftLength; i++) {
left[i]=input[from+i];
}
for (int i = 0; i < rightLength; i++) {
right[i]=input[middle+i+1];
}
left[leftLength]=Integer.MAX_VALUE;
right[rightLength]=Integer.MAX_VALUE;
int leftPointer=0;
int rightPointer=0;
for(int i=from ;i<=to;i++){
if(left[leftPointer]>right[rightPointer]){
input[i]=right[rightPointer];
rightPointer++;
}
else{
input[i]=left[leftPointer];
leftPointer++;
}
}

}

public static void main(String args[]){
int[] x=new int[]{2,12,0,1,3,9,5,28,81,2,67,5,12,1};
MergeSort.mergeSort(x, 0, x.length-1);

for(int x1:x){
System.out.println(x1);
}
}
}

Quick Short

• it is Recursive Algorithm
• it mainly follow divide and conquer
• use a pivot element to partition the array in two parts
• Element<pivot to its left,element>pivot to its right
• pivot will then be in its correct sorted position

  Characteristics of Quick Short algorithm:
  

•   in place algorithm
•   we are repeating partition into two half's
•   Complexity O(nlogn)-base 2
•   Unstable alogrithm

  Choose “Pivot”

    Move smaller numbers ont its left side and larger on its right side

    Recursively call quick sort on the left and right side.
 

  
It is a divide and conquer approach with recurrence relation:

 T(n) = T(k) + T(n-k-1) + cn

Worst case: when the array is sorted or reverse sorted, the partition algorithm divides the array in two subarrays with 0 and n-1 elements. Therefore,

T(n) = T(0) + T(n-1) + cn
Solving this we get, T(n) = O(n^2)

Best case and Average case: On an average, the partition algorithm divides the array in two subarrays with equal size. Therefore,

T(n) = 2T(n/2) + cn 

Solving this we get, T(n) = O(nlogn)

Que – . Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then, (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n

Solution: The complexity of quick sort can be written as:

T(n) = T(k) + T(n-k-1) + cn

As given in question, one list contains 1/5th of total elements. Therefore, another list will have 4/5 of total elements. Putting values, we get:

T(n) = T(n/5) + T(4n/5) + cn, which matches option (B).



 public static void quickSortEXicuter(int[] input) {

            quickSort(input,0,input.length-1);

      }

      private static void quickSort(int[] input, int from, int to) {

            if(from<to){

                  int indexOfPivot=partition(input,from,to);

                  quickSort(input,from,indexOfPivot-1);

                  quickSort(input,indexOfPivot+1,to);

            }

      }

      private static int partition(int[] input, int from, int to) {

            int pivot=to;

            int wall=from;

            for(int i=from;i<to;i++){

                  if(input[i]<=pivot){

                        int temp=input[wall];

                        input[wall]=input[i];

                        input[i]=temp;

                        wall++;

                  }

            }

            input[to]=input[wall];

            input[wall]=pivot;

            return wall;

      }

  Complete Code:

package algorithm.sorting;

public class Quick {

public static void quickSortEXicuter(int[] input) {

quickSort(input,0,input.length-1);

}

private static void quickSort(int[] input, int from, int to) {

if(from<to){

int indexOfPivot=partition(input,from,to);

quickSort(input,from,indexOfPivot-1);

quickSort(input,indexOfPivot+1,to);

}

}

private static int partition(int[] input, int from, int to) {

int pivot=to;

int wall=from;

for(int i=from;i<to;i++){

if(input[i]<=pivot){

int temp=input[wall];

input[wall]=input[i];

input[i]=temp;

wall++;

}

}

input[to]=input[wall];

input[wall]=pivot;

return wall;

}

public static void main(String args[]){

int[] x=new int[]{2,12,0,1,3,9,5,28,81,2,67,5,12,1};

Quick.quickSortEXicuter(x);

for(int x1:x){

System.out.println(x1);

}

}

}

Time and Space Complexity Comparison Table :

    Non-comparison based sorting –

   

• Radix sort –
  Best, average and worst case time complexity: nk where k is the maximum number of digits in elements of array.
• Count sort –
  Best, average and worst case time complexity: n+k where k is the size of count array.
• Bucket sort –
  Best and average time complexity: n+k where k is the number of buckets.
  Worst case time complexity: n^2 if all elements belong to same bucket.

Que – 1. Which sorting algorithm will take the least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.
(A) Insertion Sort
(B) Heap Sort
(C) Merge Sort
(D) Selection Sort

Solution: insertion sort will have the complexity of n when the input array is already sorted.