Tuesday, July 5, 2016

Quick Sort Program in java using Array

Hello Guys,
Today after almost 1 month I am posting about Quick Sort.As Quick Sort is much better than merge sort as both of them are of the Complexity of logn but the Constant factor in quick sort is much lesser than merge sort and the quick sort is in place sort algorithm

In my earlier post I have talked about Tower of Hanoi problem
You can also see other Sorting program
Bubble Sort
Selection Sort
Insertion Sort

Why Quick Sort is better than merge sort ??

• The Time Complexity of both is logn but the constant factor of quick sort is much lesser than merge sort
• Quick Sort is in place algorithm i.e it do not require extra array/linkedlist to sort the list
Java Program of Quick Sort

package com.vp.sort;

public class QsortDemo {
public static void main(String[] args) {
int[] a={10,23,43,2,5,6,12};
quickSort(a,0,a.length-1);
display(a);
}
public static void display(int[] a)
{
String result="[";
for(int sData:a)
{
result+=sData+",";
}
result+="]";
System.out.println(result);
}
public static void quickSort(int[] a,int start, int end)
{
int pivot=0;
if(start<end)
{
pivot = partition(a,start,end);
quickSort(a, start, pivot-1);
quickSort(a, pivot+1, end);
}
}
public static int partition(int[] a , int start , int end )
{
int pivot =a[end];
int i =start;
for(int j=start;j<end;j++)
{
if(a[j]<=pivot)
{
int temp =a[j];
a[j]=a[i];
a[i]=temp;
i++;
}
}
int temp  =a[end];
a[end] =a[i];
a[i] =temp;
display(a);
return i;
}

}

Output-
[10,2,5,6,12,23,43,]
[2,5,6,10,12,23,43,]
[2,5,6,10,12,23,43,]
[2,5,6,10,12,23,43,]
[2,5,6,10,12,23,43,]

Time Complexity - O(logn)

Guys if you are facing any problem in understanding the program do let me know , I will try my best to help you in understanding the program logic