Quick Sorting Algorithms in Java

Quick sort in java, also known as the partition-exchange sort, is a divide and conquer sorting algorithm. Quick sort is a good example of an algorithm that best uses CPU caches because of its divide and conquers nature. Quicksort algorithm is one of the most used sorting algorithms, especially to sort large lists, and most of the programming languages have implemented it. The Quicksort algorithm divides the original data into two parts: individually sorted and then merged to produce sorted data.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

Let us consider that the array {8, 6, 3, 4, 9, 2, 1, 7} needs to be sorted using Quick Sort.

Steps to Implement Quick Sorting Algorithms

1. Choose an element called pivot from the array. Generally, the middle element is chosen as the pivot. Let us take 4 as the pivot.

2. Rearrange the array into two parts such that elements less than the pivot come before the pivot and elements greater than the pivot appears after the pivot. The following steps are followed:

• Pick the leftmost element, i.e. 8; since 4 is the pivot, and 8 is more than 4, 8 needs to be moved to the right of 4; on the right-hand side, we leave 7 since it is greater than 4 and pick 1 for swapping with 8 hence after swapping the array becomes: 1,6,3,4,9,2,8,7
• Pick the next left element, i.e. 6; since 4 is the pivot, and 6 is more than 4, 6 needs to be moved to the right of 4; on the right-hand side, we leave 7,8 since they are greater than 4 and pick 2 for swapping with 6 hence after swapping the array becomes: 1,2,3,4,9,6,8,7
• Now since all the elements to the left of the pivot are less than the pivot and all the elements to the right of the pivot are greater than the pivot, we are done with 4 as the pivot.

3. Recursively apply steps 1 and 2 for the left sub-array (array with elements less than the pivot) and for the right sub-array (array with elements more than the pivot). If the array contains only one or zero elements, then the array is considered assorted.

Program to Implement Quick Sorting Algorithms

Here is a java program to sort an array of integers using a quick sort algorithm.

Code:

import java.lang.*;
import java.util.*;
public class Main {
private int array[];
private int length;
public void sort(int[] inputArrayArr) {
if (inputArrayArr == null || inputArrayArr.length == 0) {
return;
}
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
}
private void performQuickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two subarrays
while (i <= j) {
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
}
private void swapNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String args[]){
Main quickSort = new Main();
int[] inputArray = {8,6,3,4,9,2,1,7};
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
}
}

Output:

Advantages of Quick Sorting Algorithms

The following are the advantages of the quick sort algorithm:

• Excellent Locality of Reference: The locality of reference is the ability of a processor to access the same memory location repetitively over a short period of time. Quick sort in java provides an excellent locality of Reference due to the very small number of cache misses, which on modern architectures is critical for performance.
• Quick Sort Is Parallelizable: Once the initial step of partitioning an array into smaller regions is completed, all the individual subarrays can be sorted independently in parallel. Due to this reason, quick sort performs better.

Complexity Analysis of Quick Sort

Quicksort is a fast and tail-recursive algorithm that works by the divide and conquer principle. Here is its complexity analysis in Best, Average and Worst Case:

• Best Case Complexity: If an array or a list contains n elements, then the first run will need O (n). Now Sorting the remaining two subarrays takes 2*O (n/2). This concludes the complexity of O (n logn) in the best case.
• Average Case Complexity: The average case of quicksort is O (n log n).
• Worst Case Complexity: Choosing first or last would cause worst-case performance for nearly-sorted or nearly-reverse-sorted data. Quick sort performs O (n^2) in the worst case.

 In Java, Arrays. Sort () method uses a quick sort algorithm to sort an array.

The above is the detailed content of Quick Sorting Algorithms in Java. For more information, please follow other related articles on the PHP Chinese website!