Quicksort program in java

Quicksort:

In quick sort one element is selected as a pivot from array.Using pivot array is divided into two parts elements less than pivot and greater than pivot. procedure is done until array get sorted

Worst case performance:     O(n2)
Best case performance:        O(n log n) (simple partition)  /  O(n) (three-way partition and equal keys)
Average case performance:  O(n log n)

 

quicksort in java

quicksort in java

import java.io.*;
class QuickSortRec
{
public static void main(String args[ ])throws IOException
{
int i,n=0;

DataInputStream in = new DataInputStream(System.in);

System.out.print("Enter how many numbers to be sorted : ");
n = Integer.parseInt(in.readLine());
int x[]=new int[n];
System.out.println("Enter numbers");
for(i=0;i<n;i++)
{
x[i] = Integer.parseInt(in.readLine());
}

quicksort(x,0,n-1,n);
System.out.println("\nSorted Elements are :");

display(x,n);

}
static void quicksort(int x[], int lb, int ub, int n)
{
int j=0;
if(lb>=ub)
return;
j=partition(x, lb, ub, j);
System.out.println("After partitioning array from index "+(lb+1)+" to "+(ub+1)+ " :\n ");
display(x,n);
quicksort(x, lb, j-1, n);
quicksort(x, j+1, ub, n);
}
static int partition(int x[], int lb, int ub, int pj)
{
int a, down, temp, up;
a=x[lb];
up=ub;
down=lb;
while(down<up)
{
while(x[down]<=a && down<up)
down=down+1;
while(x[up]>a)
up=up-1;
if(down<up)
{
temp=x[down];
x[down]=x[up];
x[up]=temp;
}
}
x[lb]=x[up];
x[up]=a;
pj=up;
return (pj);
}
static void display(int x[], int n)
{
int i;
System.out.println(" ");
for(i=0;i<n;i++)
System.out.print("\t"+x[i]+ " ");
System.out.println(" ");
}
}

/*OUTPUT:
Enter how many numbers to be sorted : 5
Enter 5 numbers in any order....
Element x[1]=5
Element x[2]=2
Element x[3]=34
Element x[4]=1
Element x[5]=9
After partitioning array from index 1 to 5 :
1 2 5 34 9
After partitioning array from index 1 to 2 :
1 2 5 34 9
After partitioning array from index 4 to 5 :
1 2 5 9 34

Sorted Elements are :
-----------------------------------

1 2 5 9 34
----------------------------------- */

Quicksort in C

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *