The idea of quicksort

At the beginning

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.

The idea of quicksort

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.

Disassembled image of the list

image

Image of aggregated list after decomposition

image

Implementation code

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

The idea of quicksort
The idea of jQuery
The secret to the success of IntelliJ IDEA
The world of clara-rules (2)
About the idea of anonymous classes in Java
Judgment of the calendar
The world of clara-rules (4)
The world of clara-rules (1)
The world of clara-rules (3)
The world of clara-rules (5)
I tried using the profiler of IntelliJ IDEA
I tried the new feature profiler of IntelliJ IDEA 2019.2.
About the handling of Null
Docker monitoring-explaining the basics of basics-
About the description of Docker-compose.yml
Understand the basics of docker
The play of instantiating java.lang.Void
Explanation of the FizzBuzz problem
The basics of Swift's TableView
Median of the three values
The illusion of object orientation
Switch the version of bundler
The idea of cutting off when the error is not resolved
The idea of C # (lambda expression, for statement) to chew
About the behavior of ruby Hash # ==
Continuation: The parable of OOP (omitted)
Try to imitate the idea of a two-dimensional array with a one-dimensional array
Qualify only part of the text
Understand the basic mechanism of log4j2.xml
About the basics of Android development
'% 02d' What is the percentage of% 2?
[Rails] Check the contents of the object
Replace the contents of the Jar file
[Java version] The story of serialization
Check the version of Cent OS
[Ruby] See the essence of ArgumentError
Explanation of the order of rails routes
I read the source of ArrayList I read
The basics of SpringBoot + MyBatis + MySQL
Note on the path of request.getRequestDispatcher
The basic basis of Swift dialogs
The basic basis of Swift's Delegate
I read the source of Integer
This and that of the JDK
Check the migration status of rails
The story of @ViewScoped consuming memory
Filter the fluctuations of raw data
A memorandum of the FizzBuzz problem
I read the source of Long
Official logo list of the service
Explain the column of Spree :: Product
Various methods of the String class
About the role of the initialize method
Think about the 7 rules of Optional
Get the ID of automatic numbering
[For beginners] Personally thinking about the cause of the error-the idea of ​​the solution
I read the source of Short
I read the source of Byte
Order of processing in the program
I read the source of String
The origin of Java lambda expressions