This is the code for implementation of Quicksort
In this data structure quick sorting technique I have used algo as follows:
In partition method
pivot the first element and i=1 and j=last index
comparing element at i and j with pivoted element as follows
1.while(a[i]<a[p])
increment i
2.while(a[j]>a[p])
decrement j
3.if i<j:
swap a[i] and a[j]
4.if i<j:
GO TO 1
else:
swap a[pivot] and a[j]
In Sorting Method after partition let p(return of partition method) be position of pivoted element p=call partition method used recursion for sorting
import java.util.Scanner;
class Q_Sort {
int partition(int a[],int i,int j) {
int n=a.length;
int p=0;
i=1;
j=n-1;
while(i<j){
while(a[i]<a[p]) {
i++;
}
while(a[j]>a[p]) {
--j;
}
if(i<j) {
int t=a[j];
a[j]=a[i];
a[i]=t;
}
}
int temp=a[j];
a[j]=a[p];
a[p]=temp;
return j;
}
void Sort(int a[], int low, int high)
{
if(low<high)
{
int p = partition(a, low, high);
Sort(a,low,p-1);
Sort(a,p+1,high);
}
}
static void Display(int a[]) {
int l=a.length;
for(int i=0;i<l;i++) {
System.out.print(a[i]+" ");
}
}
public static void main(String args[]) {
int n;
Scanner s=new Scanner(System.in);
Q_Sort ob=new Q_Sort();
System.out.print("Enter no. of elements you want in array:");
n=s.nextInt();
int a[] = new int[n];
System.out.println("Enter all the elements:");
for(int i=0;i<n;i++) {
a[i]=s.nextInt();
}
System.out.println("Before Quick Sort" );
Display(a);
ob.Sort(a,0,n-1);
System.out.println("After Quick Sort ");
Display(a);
}
}
