## Quick Sort Program in java

Category : Data-structures-algorithms | Sub Category : Sorting Algorithms | By Prasad Bonam Last updated: 2020-11-05 10:51:24 Viewed : 753

Quick Sort

Quicksort is a fascinating sorting algorithm.

·        It belongs to the class of divide and conquer algorithms.

·        It sorts in place, meaning it would not require any extra memory space to complete the sorting, unlike mergesort which would need space equal to the size of array you want to get sorted.

1. Quick Sort Partition Algorithm:

quickSort(arr, beg, end)

if (beg < end)

pivotIndex = partition(arr,beg, end)

quickSort(arr, beg, pivotIndex)

quickSort(arr, pivotIndex + 1, end)

partition(arr, beg, end)

set end as pivotIndex

pIndex = beg - 1

for i = beg to end-1

if arr[i] < pivot

swap arr[i] and arr[pIndex]

pIndex++

swap pivot and arr[pIndex+1]

return pIndex + 1

2. Example:

QuickSort.java

` package runnerdev;`

import java.util.Arrays;

import java.util.List;

public class QuickSort {

public <T extends Comparable<T>> T[] sort(T[] array) {

doSort(array, 0, array.length - 1);

return array;

}

/**

* 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 = randomPartition(array, left, right);

doSort(array, left, pivot - 1);

doSort(array, pivot, right);

}

}

/**

* Ramdomize the array to avoid the basically ordered sequences

*

* @param array The array to be sorted

* @param left  The first index of an array

* @param right The last index of an array

* @return the partition index of the array

*/

private static <T extends Comparable<T>> int randomPartition(T[] array, int left, int right) {

int randomIndex = left + (int) (Math.random() * (right - left + 1));

SortUtils.swap(array, randomIndex, right);

return partition(array, left, 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) >>> 1;

T pivot = array[mid];

while (left <= right) {

while (SortUtils.less(array[left], pivot)) {

++left;

}

while (SortUtils.less(pivot, array[right])) {

--right;

}

if (left <= right) {

SortUtils.swap(array, left, right);

++left;

--right;

}

}

return left;

}

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 };

QuickSort quickSort = new QuickSort();

quickSort.sort(array);

System.out.print("Integer Array Sorting: ");

// Output => 0 1 1 2 2 3 4 5 5 5 7 8 9 12 32 44 111

for (Integer sort : array) {

System.out.print(sort+" ");

}

String[] stringArray = { "c", "a", "e", "b", "d" };

quickSort.sort(stringArray);

//SortUtils.print(stringArray);

System.out.print(" String Array Sorting: ");

// Output => a b c d e

for (String sort : stringArray) {

System.out.print(sort+" ");

}

}

}

class SortUtils {

/**

* 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 than the other element

*

* @param v first element

* @param w second element

* @return true if the first element is less than the second element

*/

static <T extends Comparable<T>> boolean less(T v, T w) {

return v.compareTo(w) < 0;

}

/**

* This method checks if first element is greater than the other element

*

* @param v first element

* @param w second element

* @return true if the first element is greater than the second element

*/

static <T extends Comparable<T>> boolean greater(T v, T w) {

return v.compareTo(w) > 0;

}

/**

* Prints a list

*

* @param toPrint - a list which should be printed

*/

static void print(List<?> toPrint) {

toPrint.stream().map(Object::toString).map(str -> str + " ").forEach(System.out::print);

System.out.println();

}

/**

* Prints an array

*

* @param toPrint - an array which should be printed

*/

static void print(Object[] toPrint) {

System.out.println(Arrays.toString(toPrint));

}

/**

* Swaps all position from {@param left} to @{@param right} for {@param array}

*

* @param array is an array

* @param left  is a left flip border of the array

* @param right is a right flip border of the array

*/

static <T extends Comparable<T>> void flip(T[] array, int left, int right) {

while (left <= right) {

swap(array, left++, right--);

}

}

}

Output:

Integer Array Sorting: 0 1 1 2 2 3 4 5 5 5 7 8 9 12 32 44 111

String Array Sorting: a b c d e