**by BehindJava**

# 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.

- If ( BEG < END ) then
- Find the element that divides the array into two parts using subfunction
**Partition( )**. - Quick Sort ( Left Half )
- Quick Sort ( Right Half ).

[ End of If ] - Exit

**Partition ( ):**

- Set LEFT = BEG, RIGHT = END and LOC = BEG
- 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 ( ). - 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 ( ). - 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 `