In this article, we will discuss working and implementation of the Quick Sort algorithm.
Quick Sort is an example of a divide-and-conquer algorithmic technique. It is also called partition exchange sort. It uses recursive calls for sorting the elements, and it is one of the famous algorithms among comparison-based sorting algorithms.
Divide: The array A[low ...high] is partitioned into two non-empty sub-arrays A[low ...q] and A[q + 1... high], such that each element of A[low ... high] is less than or equal to each element of A[q + 1... high]. The index q is computed as part of this partitioning procedure.
Conquer: The two sub-arrays A[low ...q] and A[q + 1 ...high] are sorted by recursive calls to Quick sort.
Partition in Quick Sort
Following animated representation explains how to find the pivot value in an array.
The pivot value divides the list into two parts. And recursively, we find the pivot for each sub-lists until all lists contain only one element.
Algorithm
The recursive algorithm consists of four steps:
- If there are one or no elements in the array to be sorted, return.
- Pick an element in the array to serve as the “pivot” point. (Usually, the left-most element in the array is used.)
- Split the array into two parts – one with elements larger than the pivot and the other with elements smaller than the pivot.
- Recursively repeat the algorithm for both halves of the original array.
Let's write a simple logic for Quick Sort algorithm in Java.
Simple Implementation of Quick sort
import java.util.Arrays;
/**
* Java program for implementation of QuickSort
*
* @author Ramesh Fadatare
*
*/
public class QuickSort {
/*
* This function takes last element as pivot, places the pivot element at
* its correct position in sorted array, and places all smaller (smaller
* than pivot) to left of pivot and all greater elements to right of pivot
*/
private int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
/*
* The main function that implements QuickSort() arr[] --> Array to be
* sorted, low --> Starting index, high --> Ending index
*/
private void quickSort(int arr[], int low, int high) {
if (low < high) {
/*
* pi is partitioning index, arr[pi] is now at right place
*/
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static void main(String args[]) {
int arr[] = { 20,10,5,6,2,3,4};
QuickSort quickSort = new QuickSort();
System.out.println("Before Sorting an array : " + Arrays.toString(arr));
quickSort.quickSort(arr, 0, arr.length - 1);
System.out.println("After Sorting an array : " + Arrays.toString(arr));
}
}
Output:
Before Sorting an array : [20, 10, 5, 6, 2, 3, 4]
After Sorting an array : [2, 3, 4, 5, 6, 10, 20]
The above code sorts only integer array but what about if we want to sort Strings, Dates, Doubles etc. I have implemented a generic quick sort algorithm to sort any data type the implements Comparable interface.
Generic Implementation of Quick sort
Let's create a generic implementation of the Quick Sort algorithm so that we can sorting Integer, String, Double etc. This program sorts according to the natural ordering of its elements. Wrapper classes and String internally implement the Comparable interface.
This program demonstrates sorting Integer and String array using Quick Sort Algorithm.
import java.util.Arrays;
/**
* Generic implementation of Generic Quick Sort
* @author Ramesh Fadatare
*
*/
public class GenericQuickSort {
/**
* This method implements the Generic Quick Sort
*
* @param array The array to be sorted
* Sorts the array in increasing order
**/
public <T extends Comparable<T>> T[] quickSort(T[] array) {
doSort(array, 0, array.length - 1);
return array;
}
/**
* Helper method for swapping places in array
* @param array The array which elements we want to swap
* @param idx index of the first element
* @param idy index of the second element
*/
static <T> boolean swap(T[] array, int idx, int idy){
T swap = array[idx];
array[idx] = array[idy];
array[idy] = swap;
return true;
}
/**
* This method checks if first element is less then the other element
* @param v first element
* @param w second element
* @return true if the first element is less then the second element
*/
static <T extends Comparable<T>> boolean less(T v, T w) {
return v.compareTo(w) < 0;
}
/**
* The sorting process
*
* @param left The first index of an array
* @param right The last index of an array
* @param array The array to be sorted
*
**/
private static <T extends Comparable<T>> void doSort(T[] array, int left, int right) {
if (left < right) {
int pivot = partition(array, left, right);
doSort(array, left, pivot - 1);
doSort(array, pivot , right);
}
}
/**
* This method finds the partition index for an array
*
* @param array The array to be sorted
* @param left The first index of an array
* @param right The last index of an array
* Finds the partition index of an array
**/
private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
int mid = (left + right) / 2;
T pivot = array[mid];
while(left <= right) {
while(less(array[left], pivot)){
++left;
}
while(less(pivot, array[right])) {
--right;
}
if(left <= right) {
swap(array, left, right);
++left;
--right;
}
}
return left;
}
// Driver Program
public static void main(String[] args) {
// For integer input
Integer[] array = {3, 4, 1, 32, 0, 1, 5, 12 ,2, 5 ,7 ,8 ,9, 2, 44, 111, 5};
GenericQuickSort quickSort = new GenericQuickSort();
System.out.println("Before sorting the array elements : " +Arrays.toString(array));
quickSort.quickSort(array);
System.out.println("After sorting the array elements : " + Arrays.toString(array));
String[] stringArray = {"c", "a", "e", "b", "d"};
System.out.println("Before sorting the array elements : " +Arrays.toString(stringArray));
quickSort.quickSort(stringArray);
System.out.println("After sorting the array elements : " + Arrays.toString(stringArray));
}
}
Output:
Before sorting the array elements : [3, 4, 1, 32, 0, 1, 5, 12, 2, 5, 7, 8, 9, 2, 44, 111, 5]
After sorting the array elements : [0, 1, 1, 2, 2, 3, 4, 5, 5, 5, 7, 8, 9, 12, 32, 44, 111]
Before sorting the array elements : [c, a, e, b, d]
After sorting the array elements : [a, b, c, d, e]Performance
- Worst case complexity : O(n2)
- Best case complexity (Improved version) : O(nlogn)
- Average case complexity (Basic version) : O(nlogn)
- Worst case space complexity : O(1) auxiliary
Comments
Post a Comment
Leave Comment