QUICKSORT

QuickSort.java:

import java.util.*;

import java.io.*;

public class QuickSort{

private static Random random = new Random();

public static void main(String[] args) throws IOException {

int i,n;

// int[] array = {8,3,25,2,1,11,14,67,12,5};

InputStreamReader inp=new InputStreamReader(System.in);

BufferedReader br=new BufferedReader(inp);

System.out.println("Enter the No of values");

String input=br.readLine();

n=Integer.parseInt(input);

int array[]=new int[n];

System.out.println("Enter the Values");

for(i=0;i<n;i++)

{

System.out.println("Enter the value "+(i+1));

InputStreamReader inpval=new InputStreamReader(System.in);

BufferedReader brval=new BufferedReader(inpval);

String inputval=br.readLine();

array[i]=Integer.parseInt(inputval);

}

recursiveQuickSort(array, 0, array.length-1);

System.out.println("The following array should be sorted: ");

printList(array);

System.exit(0);

}

public static void recursiveQuickSort(int[] list, int first, int last) {

if(first < last)

{

int p = partition(list, first, last);

printList(list);

recursiveQuickSort(list, first, p-1);

recursiveQuickSort(list, p+1, last);

 }

}

public static int partition(int[] list, int first, int last) {

int p = first;

for(int n = p+1; n <= last; n++)

if(list[n] < list[p])

{

swap(list, n, p+1);

swap(list, p, p+1);

p++;

}

return p;

}

private static void swap(int[] list, int index1, int index2) {

int temp = list[index1];

list[index1] = list[index2];

list[index2] = temp;

}

protected static void printList(int[] list) {

for(int n = 0; n < list.length; n++)

System.out.print(list[n]+" ");

System.out.println();

}

}

OUTPUT:

C:\j2sdk1.4.2_02\bin>javac QuickSort.java

C:\j2sdk1.4.2_02\bin>java QuickSort

Enter the No of values

10

Enter the Values

Enter the value 1

10

Enter the value 2

45

Enter the value 3

34

Enter the value 4

76

Enter the value 5

88

Enter the value 6

34

Enter the value 7

90

Enter the value 8

55

Enter the value 9

77

Enter the value 10

22

10 45 34 76 88 34 90 55 77 22

10 34 34 22 45 76 90 55 77 88

10 22 34 34 45 76 90 55 77 88

10 22 34 34 45 55 76 90 77 88

10 22 34 34 45 55 76 77 88 90

10 22 34 34 45 55 76 77 88 90

The following array should be sorted:

10 22 34 34 45 55 76 77 88 90