Since the implementation of quicksort explained on the net did not come well, I will upload an article that I summarized myself. The algorithm policy adopts element decomposition and reaggregation, which is often taken up in the explanation of functional languages, and I will try to implement it in Java and see how troublesome it is to implement quicksort in imperative languages.

As an example, consider sorting a set of numbers [6,1,8,5,9]. When doing quicksort, we need a criterion to divide the elements, but here we will use the first element of the set as the criterion.

`Qsort.java`

```
package test;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
public class QSort {
public static void main(String args[]){
System.out.println(qsort(Arrays.asList(1,5,6,2,11,9,4)));
}
public static List<Integer> qsort(List<Integer>list){
if(list.size()==1){
//If the array contains one element, exit the recursive process
return new ArrayList<Integer>(list) ;
}else{
//Call the process to split the elements in the list
Divive div = splitList(list);
//Generate a list to store the split array
List<Integer>newList = new ArrayList<Integer>();
//Perform recursive processing to separate a small set of numbers again
newList.addAll(qsort(div.leftList));
//Perform recursive processing to isolate a large set again
newList.addAll(qsort(div.rightList));
return newList ;
}
}
//Function to split the list
public static Divive splitList(List<Integer>list){
int size =list.size();
Divive div = new Divive();
//When the number of elements is two, the size of the elements is compared and the elements are divided.
if(size==2){
if(list.get(0)<=list.get(1)){
div.leftList.add(list.get(0)) ;
div.rightList.add(list.get(1)) ;
}else{
div.leftList.add(list.get(1)) ;
div.rightList.add(list.get(0)) ;
}
return div;
}
int pivot = list.get(0);
List<Integer>smallIntList =new ArrayList<Integer>();
List<Integer>largeIntList =new ArrayList<Integer>();
//Divide the list given by the argument into a small set and a large set according to a predetermined criterion.
for(int i=0;i<size;i++){
//Generate a set of numbers smaller than the reference
if(pivot>=list.get(i))smallIntList.add(list.get(i));
//Generate a set of numbers larger than the reference
if(pivot<list.get(size - 1- i))largeIntList.add(list.get(size - 1- i));
}
//If the arguments of the list given in the argument do not match the small set, return the split list combination to the caller.
if(smallIntList.size()!=list.size()){
div.leftList.addAll(smallIntList);
div.rightList.addAll(largeIntList);
}
//If the argument of the list given by the argument matches the small set, the reference number is the smallest, so
//Split the list on the far left of the list and elsewhere
else{
Deque<Integer> que = new ArrayDeque<Integer>(smallIntList);
div.leftList.add(que.pop()) ;
div.rightList.addAll(new ArrayList<Integer>(que)) ;
}
return div;
}
//Since Java cannot set a binary value for the return value, it is necessary to define a data structure that represents the set after division.
static public class Divive{
List<Integer>leftList =new ArrayList<Integer>();
List<Integer>rightList =new ArrayList<Integer>();
}
}
```

Recommended Posts