Placement Interview Package - I - Quick Sort, Heap Sort, Insertion Sort and Merge Sort - All in one place

Posted on April 14, 2016
quick-sort-merge-sort-heap-sort-insertion-sort

This is the part - I of the Placement Interview package. This contains all the sorting algorithms with running code so that one can quickly refer to all the sorts in one place.


Insertion Sort






    public void insertionSort(int [] A){
for(int i=1;i<A.length;i++){
int j = i;
while(j-1>=0 && A[j-1]>A[j]){
int temp = A[j];
A[j] = A[j-1];
A[j-1] = temp;
j--;
}
}
}


Quick Sort






    public int partition(int [] A,int low,int high){
int x = A[high];
int i = low-1;
for(int j=low;j<high;j++){
if(A[j]<=x){
i++;
int temp = A[j];
A[j] = A[i];
A[i] = temp;
}
}
A[high] = A[i+1];
A[i+1] = x;
return i+1;
}
public void quickSort(int [] A,int low,int high){
if(low<high){
int q = partition(A,low,high);
quickSort(A,low,q-1);
quickSort(A,q+1,high);
}
}


MergeSort






    public void mergeSort(int [] A,int low,int high){
if(low>=high)
return;
int mid = low + (high-low)/2;
mergeSort(A,low,mid);
mergeSort(A,mid+1,high);
int [] C = new int[high-low+1];
int count = 0;
int i=low,j = mid+1;
while(i<=mid && j<=high){
if(A[i]<=A[j]){
C[count++] = A[i++];
}
else{
C[count++] = A[j++];
}
}
while(i<=mid)
C[count++] = A[i++];
while(j<=high)
C[count++] = A[j++];
int index = 0;
for(i=low;i<=high;i++)
A[i] = C[index++];
}


Heap Sort




    public void maxHeapify(int [] A,int i,int n){
int left = 2*i+1;
int right = left+1;
int largest = i;
if(left<n && A[largest]<A[left])
largest = left;
if(right<n && A[largest]<A[right])
largest = right;
if(i!=largest){
int temp = A[i];
A[i] = A[largest];
A[largest] = temp;
maxHeapify(A,largest,n);
}
}
public void heapSort(int [] A){
int n = A.length;
while(n>0){
for(int i=n/2-1;i>=0;i--)
maxHeapify(A,i,n);
int temp = A[n-1];
A[n-1] = A[0];
A[0] = temp;
n--;
}
}





All Sorts




For convenience, I have put all the sorting code in a single class. You can uncomment the appropriate sorting method of your choice and run the code.


class Solution{
/************** INSERTION SORT BEGINS ******************/
public void insertionSort(int [] A){
for(int i=1;i<A.length;i++){
int j = i;
while(j-1>=0 && A[j-1]>A[j]){
int temp = A[j];
A[j] = A[j-1];
A[j-1] = temp;
j--;
}
}
}
/************** INSERTION SORT ENDS ******************/
/************** QUICK-SORT BEGINS ******************/
public int partition(int [] A,int low,int high){
int x = A[high];
int i = low-1;
for(int j=low;j<high;j++){
if(A[j]<=x){
i++;
int temp = A[j];
A[j] = A[i];
A[i] = temp;
}
}
A[high] = A[i+1];
A[i+1] = x;
return i+1;
}
public void quickSort(int [] A,int low,int high){
if(low<high){
int q = partition(A,low,high);
quickSort(A,low,q-1);
quickSort(A,q+1,high);
}
}
/************** QUICK-SORT ENDS ******************/
/************** HEAP-SORT BEGINS ******************/
public void maxHeapify(int [] A,int i,int n){
int left = 2*i+1;
int right = left+1;
int largest = i;
if(left<n && A[largest]<A[left])
largest = left;
if(right<n && A[largest]<A[right])
largest = right;
if(i!=largest){
int temp = A[i];
A[i] = A[largest];
A[largest] = temp;
maxHeapify(A,largest,n);
}
}
public void heapSort(int [] A){
int n = A.length;
while(n>0){
for(int i=n/2-1;i>=0;i--)
maxHeapify(A,i,n);
int temp = A[n-1];
A[n-1] = A[0];
A[0] = temp;
n--;
}
}
/************** HEAP-SORT ENDS ******************/
/************** MERGE-SORT BEGINS ******************/
public void mergeSort(int [] A,int low,int high){
if(low>=high)
return;
int mid = low + (high-low)/2;
mergeSort(A,low,mid);
mergeSort(A,mid+1,high);
int [] C = new int[high-low+1];
int count = 0;
int i=low,j = mid+1;
while(i<=mid && j<=high){
if(A[i]<=A[j]){
C[count++] = A[i++];
}
else{
C[count++] = A[j++];
}
}
while(i<=mid)
C[count++] = A[i++];
while(j<=high)
C[count++] = A[j++];
int index = 0;
for(i=low;i<=high;i++)
A[i] = C[index++];
}
/************** MERGE-SORT ENDS ******************/
public void print(int [] A){
for(int i=0;i<A.length;i++)
System.out.print(A[i] + " ");
}
public void run(){
int [] A = {8,4,3,6,1,9,3,2,5};
insertionSort(A);
//quickSort(A,0,A.length-1);
//mergeSort(A,0,A.length-1);
//heapSort(A);
print(A);
}
public static void main(String [] args){
new Solution().run();
}
}

Sharing is Caring!

GET FREE UPDATES


RECOMMENDED POSTS FOR YOU


profile image

Kaushik Baruah

Research Engineer @XRCI


ABOUT

My name is Kaushik Baruah and I am the chief blogger on this Blog and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects. You can follow me on Twitter, Facebook and Google+

GET FREE UPDATES

POPULAR POSTS

Copyright © 2016
About Us

My name is Kaushik Baruah and I am the chief blogger on this Blog and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects.

Get Free Updates