Select Page

Quick Sort in Java

Like merge sort, quick sort also uses the divide and conquer approach to sort the given array or list. In quick sort, the sorting of an array is achieved by taking an element from the input array as the pivot and then split the array using the pivot.

Algorithm

STEP 1: Take either the first or the last element as the pivot element.

STEP 2: Find and place the pivot element at its correct position, i.e., the elements that are on the left side of the pivot element must be less than the pivot element. Also, elements that are on the right side of the pivot element must be greater than the pivot element.

STEP 3: Recursively execute steps 1 and 2 till the whole array is sorted.

Pseudo Code

Java Program

The following Java program implements Quick sort using the pseudo-code defined above.

FileName: QuickSortExample.java

Output:

Explanation: All we have to take care is how elements less than the pivot element take the left side of the array. It is done by the for-loop present in the partition() method. When all the elements less than the pivot element take the left side of the array, the remaining elements automatically take the right side. These remaining elements are greater than the pivot element. The pivot element can then be placed just after the ending of elements that are smaller than the pivot element. Observe the following diagram.

Analysis of Quick Sort

One of the main advantages of the quick sort algorithm is that it is in-place sorting. It means that it does not require no extra space for sorting. Looking from this perspective, quick sort should be preferred over the merge sort. Also, this algorithm works as quickly as merge sort.

The downsides of the algorithm are that when a sorted array is given as input, the algorithm takes O(n2) time to process the sorted array. It is worse than merge sort. It takes O(nlog(n)) time to sort the array. Note that n is the size of the input array.

Conclusion

Between merge sort and quick sort, quick sort is the better choice when the array is not sorted. If, instead of an array, a linked list is given to be sorted, go for merge sort instead of quicksort. The reason behind this is, unlike an array, randomized access of elements is not possible in a linked list, and quick sort relies heavily on the random access of elements, whereas, merge sort does not.

Also, it is found that merge sort works well for larger data sets, and quick sort works well for smaller data sets.

Time Complexity

The average and best time complexity of the quicksort is O(nlog(n)), where n is the number of elements present in the array. For sorted arrays, this sorting algorithm gives the time complexity as O(n2). Hence, the worst time complexity of this sorting algorithm is O(n2).

Space Complexity

The space complexity of the merge sort algorithm is O(1), that is, constant space complexity. Observe the code; there is no auxiliary array or any additional space used to do the sorting.