Quick sort in Java is used to sort integer values of an array. It is a comparison sort. Quick sort is one of the fastest and simplest sorting algorithm in comparison to other sorting algorithms like bubble sort, insertion sort, heap sort, etc.
Quick sort in Java is used to sort integer values of an array. It is a comparison sort. Quick sort is one of the fastest and simplest sorting algorithm in comparison to other sorting algorithms like bubble sort, insertion sort, heap sort, etc.
The complexity of quick sort in the average case is Θ(n log n) and in the worst case is Θ(n2).
In quick sort algorithm, an element called "pivot" from the array is picked randomly. Then the left and right elements of the pivot is checked. All the smaller elements to pivot are kept on the left side of pivot and bigger elements than pivot are kept on the right side of the pivot. The list is then divided in two sub-arrays, one having small numbers than pivot and the other having bigger elements than pivot. A random pivot is again selected in both of these sub-arrays and the above procedure and partitioning is followed till all the numbers are sorted and merged into a sorted array.
Example of Quick Sort in Java:
public class QuickSort{
public static void main(String a[]){
int i;
int array[] = {42, 18, 23, 56, 17, 65, 34, 27};
System.out.println("\n\n RoseIndia\n\n");
System.out.println(" Quick Sort\n\n");
System.out.println("Values Before the sort:\n");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+" ");
System.out.println();
quick_srt(array,0,array.length-1);
System.out.print("Values after the sort:\n");
for(i = 0; i = n) {
return;
}
int mid = array[(lo + hi) / 2];
while (lo < hi) {
while (lo mid) {
hi--;
}
if (lo < hi) {
int T = array[lo];
array[lo] = array[hi];
array[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
quick_srt(array, low, lo);
quick_srt(array, lo == low ? lo+1 : lo, n);
}
}
Output:
C:\array\sorting>javac QuickSort.java
C:\array\sorting>java QuickSort
RoseIndia
Quick Sort
Values Before the sort:
42 18 23 56 17 65 34 27
Values after the sort:
17 18 23 27 34 42 53 65