Quick Sort is a

**divide and conquer**algorithm which was developed by Tony Hoare in 1960.Quick Sort first divides a large list into two smaller sub-lists: the low elements and the high elements and then recursively sort the sub-lists.

The steps are:

- Pick an element, called a
**pivot**, from the list. - Reorder the list so that all elements with values less than the
pivot come before the pivot, while all elements with values greater than
the pivot come after it (equal values can go either way). After this
partitioning, the pivot is in its final position. This is called the
**partition**operation. - Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

Below Figure illustrates how to sort an array (5 2 9 3 8 4 0 1 6 7) using quick sort. Choose the first element 5 as the

The quick sort algorithm is implemented in below code Listing. There are two overloaded quickSort methods in the class. The first method is used to sort an array. The second is a helper method that sorts a partial array with a specified range.

Reference(s):

**pivot**. The array is partitioned into two parts, as shown in Figure (b). The highlighted pivot is placed in the right place in the array. Apply quick sort on two partial arrays (4 2 1 3 0) and then (8 9 6 7). The pivot 4 partitions (4 2 1 3 0) into just one partial array (0 2 1 3), as shown in Figure (c). Apply quick sort on (0 2 1 3). The pivot 0 partitions it to just one partial array (2 1 3), as shown in Figure (d). Apply quick sort on (2 1 3). The pivot 2 partitions it to (1) and (3), as shown in Figure (e). Apply quick sort on (1). Since the array contains just one element, no further partition is needed.Quick Sort Illustration |

The quick sort algorithm is implemented in below code Listing. There are two overloaded quickSort methods in the class. The first method is used to sort an array. The second is a helper method that sorts a partial array with a specified range.

**QuickSort.java**
public class QuickSort {

public static void quickSort(int[] list) {

*quickSort*(list, 0, list.length - 1);

}

private static void quickSort(int[] list, int first, int last) {

if (last > first) {

int pivotIndex =

*partition*(list, first, last);*quickSort*(list, first, pivotIndex - 1);

*quickSort*(list, pivotIndex + 1, last);

}

}

/** Partition the
array list[first..last] */

private static int partition(int[] list, int first, int last) {

int pivot = list[first];
//
Choose the first element as the pivot

int low = first + 1; // Index for
forward search

int high = last; // Index for
backward search

while (high > low) {

// Search forward
from left

while (low <= high
&& list[low] <= pivot)

low++;

// Search backward
from right

while (low <= high
&& list[high] > pivot)

high--;

// Swap two
elements in the list

if (high > low) {

int temp = list[high];

list[high]
= list[low];

list[low]
= temp;

}

}

while (high > first
&& list[high] >= pivot)

high--;

// Swap pivot with
list[high]

if (pivot >
list[high]) {

list[first]
= list[high];

list[high]
= pivot;

return high;

}
else {

return first;

}

}

/** A test method
*/

public static void main(String[] args)
{

int[] list = { 5, 2, 9,
3, 8, 4, 0, 1, 6, 7 };

*quickSort*(list);

for (int i = 0; i < list.length; i++)

System.

*out*.print(list[i] + " ");
}

}

The output of this program is:

**0 1 2 3 4 5 6 7 8 9**

Reference(s):

http://en.wikipedia.org/wiki/Quicksort

Introduction to JAVA by Y. Daniel Liang

## No comments:

## Post a Comment