Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

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

Posted on Nov. 10, 2017
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!

Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

GET FREE UPDATES


RECOMMENDED POSTS FOR YOU


profile image

Kaushik Baruah


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