Created
July 17, 2017 20:37
-
-
Save ShaonBhattaShuvo/79034a09ba1716b50ef1bf241c0c264c to your computer and use it in GitHub Desktop.
QuickSort using Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Scanner; | |
/** | |
* | |
* @author SHUVO | |
*/ | |
public class QuickSort { | |
public static void main(String args[]){ | |
Scanner input = new Scanner(System.in); | |
int n; | |
System.out.println("Enter the size of the array:"); | |
n= input.nextInt(); | |
int a[] = new int[n]; | |
//taking array input | |
for (int i = 0; i < n; i++) { | |
a[i] = input.nextInt(); | |
} | |
//calling quickSort method where begin=0 and end = a.length-1 | |
quickSort(a,0,a.length-1); | |
//printing the array after sorting | |
for (int k = 0; k < a.length; k++) { | |
System.out.print(a[k]+" "); | |
} | |
} | |
//partition method | |
public static int partition(int a[], int begin1, int end1){ | |
int i=begin1-1; | |
int j=begin1; | |
int x = a[end1]; | |
for (; j < end1; j++) { | |
if(x>a[j]){ | |
i = i+1; | |
int temp = a[i]; | |
a[i] = a[j]; | |
a[j]=temp; | |
} | |
} | |
i = i+1; | |
int temp = a[i]; | |
a[i] = a[j]; | |
a[j]=temp; | |
//we can print the array and the value of i to check whether the partition method working properly or not | |
// for (int k = 0; k < a.length; k++) { | |
// System.out.print(a[k]+" "); | |
// } | |
// System.out.println("i="+i); | |
return i; | |
} | |
public static void quickSort(int a[], int begin, int end){ | |
if(begin<end){ | |
int pivot= partition(a, begin, end); | |
quickSort(a, begin, pivot-1); | |
quickSort(a, pivot+1, end); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment