Learn Java Java Tutoring is a resource blog on java focused mostly on beginners to learn Java in the simplest way without much effort you can access unlimited programs, interview questions, examples
Java algorithm to implement quick sort. In this topic, we will discuss the various methods by which a quick sort algorithm/Program can be done using Array & We have added compiler to each program along with sample outputs explaining a few examples. For More Java sortings you can visit here, The methods used here are:
- Quick Sort Algorithm – Using Array.
- Quick Sort Algorithm – Using Buffered Reader.
Implement Quick Sort – Using Array
1) In quick sort, divide the array into partitions and sort each partition, then we will get the sorted array. So quick sort is also called as divide and conquer algorithm.
2) In this program sort() method calls itself recursively then partition() method partitions the array, repeats until there is no possibility to partition the array. Partition method partitions the array and sorts them.
3) Partition method returns the m value. m indicates where the array will be divided into partitions. Array divided in to two partitions as (a,l,m-1), (a,m+1,h)
4) From the given example the array elements are 12, 0, -2, 54, -1, -10.
partition method returns m=4 and the array is sorted as-1,0,-2,-10,12,54.
5) Now the array from index 0 to 3 will be sorted by sort(a,0,3) method, the rest of the elements in the array from index 4 to 5 will not be sorted. The array from index 0 to 3 is sorted and divided into a partition, now the partition from 0 to 2 elements are sorted and divided into a partition, partition from 0,1 elements are sorted, and there is no possibility to next partition. now the array from index 0 to 3 is sorted array. The array after sort(a,l,m-1) is -10,-2,-1,0,12,54.
Sort(a,m+1,h) will sort the remaining unsorted array and partition method will partition the unsorted part of the array. After two sort methods the sorted array is -10,-2,-1,0,12,15.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
import java.util.Scanner; public class QSort { public static int partition(int a[],int l,int h) { int i=l+1 ,j=h,c=l,temp; for(; i<=j ;) { while(i<=h && a[i]<a[c] ) i++; while(a[j]>a[c] && j>l) j--; if(i<j) { temp=a[i]; a[i]=a[j]; a[j]=temp; } else break; } temp=a[c]; a[c]=a[j]; a[j]=temp; return j; } public static void Sort(int a[],int l,int h) { if(l<h) { int m=partition(a,l,h); Sort(a,l,m-1); Sort(a,m+1,h); } } public static void printarray(int a[]) { for(int i=0; i < a.length; i++) { System.out.print(a[i]+" "); } } public static void main(String[] args) { int n, res,i; Scanner s = new Scanner(System.in); System.out.print("Enter number of elements in the array:"); n = s.nextInt(); int a[] = new int[n]; System.out.println("Enter "+n+" elements "); for( i=0; i < n; i++) { a[i] = s.nextInt(); } System.out.println( "elements in array "); printarray(a); Sort(a,0,n-1); System.out.println( "\nelements after sorting"); printarray(a); } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Enter number of elements in the array:6 Enter 6 elements 12 0 -2 54 -1 -10 elements in array 12 0 -2 54 -1 -10 elements after sorting -10 -2 -1 0 12 54 |
Program – Using Buffered Reader
1) InputStreamReader reads the byte as character and BufferedReader reads the character as a string. BufferedReader class is available at java.io package.
2) Convert the string data into integer data using the wrapper class Integer, and the method is parseInt() of the Integer class.
3) In this program to sort the array elements, we are using the quick sort technique.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
import java.util.Scanner; import java.io.*; public class QSort { public static int partition(int a[],int l,int h) { int i=l+1 ,j=h,c=l,temp; for(; i<=j ;) { while(i<=h && a[i]<a[c] ) i++; while(a[j]>a[c] && j>l) j--; if(i<j) { temp=a[i]; a[i]=a[j]; a[j]=temp; } else break; } temp=a[c]; a[c]=a[j]; a[j]=temp; return j; } public static void Sort(int a[],int l,int h) { if(l<h) { int m=partition(a,l,h); Sort(a,l,m-1); Sort(a,m+1,h); } } public static void printarray(int a[]) { for(int i=0; i < a.length; i++) { System.out.print(a[i]+" "); } } public static void main(String[] args) throws IOException { int n,i; BufferedReader b=new BufferedReader(new InputStreamReader(System.in)); System.out.println("enter N: "); n=Integer.parseInt(b.readLine()); int a[] = new int[n]; System.out.println("enter "+n+" elements "); for(i= 0; i< n; i++) a[i] = Integer.parseInt(b.readLine()); System.out.println("elements in array "); printarray(a); Sort(a,0,n-1); System.out.println("\nelements after sorting"); printarray(a); } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Enter number of elements in the array:6 Enter 6 elements 12 20 -2 54 1 -10 elements in array 12 20 -2 54 1 -10 elements after sorting -10 -2 1 12 20 54 |
If you have any suggestion to improve or queries related to Quick Sort Java program do leave a comment here.
More Sorting Algorithms:
