by BehindJava

Data Structures - Quick Sort Algorithm

Home » datastructures » Data Structures - Quick Sort Algorithm

In this tutorial, we are going to learn about quick sort in detail and its algorithmic implementation.

Quick Sort

• In-place algorithm.
• O(n log n) - base 2. we are repeatedly partitioning the array into two halves.
• Divide and Conquer algorithm.
• Recursive in structure.
• Uses a pivot element to partition the array into two parts.
• Elements < pivot to its left, elements > pivot to its right.
• Pivot will then be in its correct sorted position.
• Process is now repeated for the left array and right array.
• Eventually, every element has been the pivot. So every element will be in its correct sorted position.
• As with merge sort, we’ll end up partitioning the array into a series of 1- element arrays.
• Unstable algorithm.

Quick Sort Algorithm

Quick Sort ( A, BEG, END ):
Description: Here A is an unsorted array having N elements. BEG is the lower bound and END is the upper bound.

1. If ( BEG < END ) then
2. Find the element that divides the array into two parts using subfunction Partition( ).
3. Quick Sort ( Left Half )
4. Quick Sort ( Right Half ).
[ End of If ]
5. Exit

Partition ( ):

1. Set LEFT = BEG, RIGHT = END and LOC = BEG
2. Beginning with the element pointed by RIGHT, scan the array from right to left, comparing each element with the element pointed by LOC until:
a. Element smaller than the element pointed by LOC is found.
b. Interchange elements pointed by LOC and RIGHT.
c. If RIGHT becomes equal to LOC, terminate the subfunction Partition ( ).
3. Beginning with the element pointed by LEFT, scan the array from left to right, comparing each element with the element pointed by LOC until:
a. Element greater than the element pointed by LOC is found.
b. Interchange elements pointed by LOC and LEFT.
c. If LEFT becomes equal to LOC, terminate the subfunction Partition ( ).
4. Exit

Quick Sort Programmatic Implementation in Java

``````public class QuickSort {
public static void main(String[] args) {
int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

quickSort(intArray, 0, intArray.length);

for (int i = 0; i < intArray.length; i++) {
System.out.print(intArray[i]+ " ");
}
}
public static void quickSort(int[] input, int start, int end) {
if (end - start < 2) {
return;
}
int pivotIndex = partition(input, start, end);
quickSort(input, start, pivotIndex);
for (int i = 0; i < input.length; i++) {
//System.out.println(input[i]);
}
quickSort(input, pivotIndex + 1, end);
}
public static int partition(int[] input, int start, int end) {
// This is using the first element as the pivot
int pivot = input[start];
int i = start;
int j = end;
while (i < j) {
// NOTE: empty loop body
while (i < j && input[--j] >= pivot);
if (i < j) {
input[i] = input[j];
}
// NOTE: empty loop body
while (i < j && input[++i] <= pivot);
if (i < j) {
input[j] = input[i];
}
}
input[j] = pivot;
return j;
}
}``````

Output:

``-22 -15 1 7 20 35 55 ``