# java. Quick sort QuickSort

### Record the differences and improvements of one-way quick sort, two-way quick sort and three-way quick sort

Basic idea: divide the records to be arranged into two independent parts through one-time sorting. If the keywords of one part of the records are smaller than those of the other part and larger than those of the other part, the records of the two parts can be sorted separately to achieve the order of the whole sequence.

## All the way quick sorting steps

1. Pick an element from the sequence and set it to V

2. Reorder the sequence. All elements smaller than V are placed in front of V, and all elements larger than V are placed behind V (the same number to the right). After this partition exits, V is in the middle of the sequence.

3. Recursively sort the subsequence less than V and the subsequence greater than v.

### code implementation

```public class QuickSort01 extends Sort{
public QuickSort01(int[] arr) {
super(arr);
}
@Override
public void sort() {
quickSort(0,arr.length - 1);
}

private void quickSort(int L, int R) {
if (L >= R) {
return;
}
//First divide the array and return the midpoint after division
int p = partition(L ,R);
quickSort(L, p - 1);//After the division, arrange it again
quickSort(p + 1, R);
}

private int partition(int L, int R) {
//Optimize the random number and change the following number with the first number
//Try to avoid extreme situations with a random corner mark
//L = 5 R = 10   [0,5] + 5 = [5,10]
swap(L, (int) (Math.random() * (R - L + 1) + L));
int v = arr[L];//Let the first continue in recursion

//arr[l+1 ~ j] < v < arr[j+1 ~ i)
int j = L;
for (int i = L + 1; i <= R; i++) {
if (arr[i] < v) {
swap(j + 1, i);
j++;
}
}
swap(L, j);//transposition
return j;
}
}```

## Two way quick sort

step

1. Pick an element from the sequence and set it to V

2. Reorder the sequence. There is a cursor on the left and right. When the left cursor i is greater than the current V, the right cursor j is traversed from the back. If it is smaller than V, it is exchanged with the current left cursor i. This is repeated until the two cursors meet. (in the code operation, the left i stops when it is not less than V, and the right j stops when it is not greater than V, and then exchange the two values and repeat)

3. Recursively and repeatedly sort the subsequence less than V and the subsequence greater than v.

### code implementation

```//Two way quick sort
public class QuickSort02 extends Sort {//Implement abstract classes
public QuickSort02(int[] arr) {//Reference parent class construction copy
super(arr);
}

@Override
public void sort() {
quickSort(0, arr.length - 1);
}

private void quickSort(int L, int R) {
if (L >= R) {//judge
return;
}
//Divide the array and return the midpoint after division
int p = partition(L, R);
quickSort(L, p - 1);
quickSort(p + 1, R);
}

private int partition(int L, int R) {
//Optimize the random number and change the following number with the first number
//Try to avoid extreme cases (ascending cases)
swap(L, (int) (Math.random() * (R - L + 1) + L));
int v = arr[L];
int i = L + 1;
int j = R;
while (true) {
while (i <= R && arr[i] < v) {//Judge that the corner mark of i does not cross the boundary and go to a stop not less than V
i++;
}
while (j >= L + 1 && arr[j] > v) {//Go to a stop not greater than V
j--;
}
if (i > j) {//Judge not to cross the line
break;
}
swap(i, j);
i++;
j--;
}
swap(L, j);//Change V to the middle
return j;
}
}```

## Three way quick sort

The biggest difference between the first two ways is to open up a separate middle area to store the same elements, and then traverse and exchange from both ends.

It's like making one-way fast platoon for the left area and the middle area, merging the left area with the middle area and making two-way fast platoon with the right area.

### The code is as follows

```//Three way quick sort
public class QuickSort03 extends Sort {
public QuickSort03(int[] arr) {
super(arr);
}

@Override
public void sort() {
quickSort(0, arr.length - 1);
}

private void quickSort(int L, int R) {
if (L >= R) {
return;
}//Random elements
swap(L, (int) (Math.random() * (R - L + 1) + L));
int v = arr[L];
int lt = L;
int gt = R + 1;
int i = L + 1;
while (i < gt) {
if (arr[i] < v) {//Left expansion
swap(i, lt + 1);
lt++;
i++;
} else if (arr[i] > v) {//Right expansion
swap(i,gt - 1);
gt--;
} else {//Intermediate zone
i++;
}
}
//Division area
swap(L,lt);
quickSort(L,lt - 1);
quickSort(gt, R);
}
}```

Keywords: Java Algorithm data structure

Added by canishk on Sat, 12 Feb 2022 18:19:30 +0200