[JAVA] QuickSort

I wrote a program for QuickSort. It's convenient to use recursion.

Quicksort is

  1. Select Pivot from the data column
  2. Divide into larger and smaller Pivot
  3. Align each divided I will sort it like this.

If Pivot is located in the center of the data string, it is the least computationally expensive algorithm in the sort, and the computational complexity is O (nlogn). If Pivot comes to the very end, it will take O (n ^ 2).

QuickSort.java


import java.util.*;
public class QuickSort {
    public static boolean debug = false;
    private static int partition(int[] a,int l,int r){
	if(debug)System.out.print("partition l="+l+", r="+r);
	int pivot = a[r];
	int i = l;
	int j = r-1;
	for (;;) {
	    while (a[i] < pivot) ++i;
	    while (i<j && a[j] >= pivot) --j;
	    if(debug) System.out.println("check i="+i+" ,j="+j+" ,pivot="+pivot);
	    if(i>=j) break;
	    if(debug) System.out.println("change i="+i+" ,j="+j);
	    int tmp = a[i];
	    a[i] = a[j];
	    a[j] = tmp;
	}
	int tmp = a[i];
	a[i] = a[r];
	a[r] = tmp;
	return i;
    }
    private static void quickSort(int[] a,int l,int r){
	if(l >= r) return;
	int v = partition(a,l,r);
	if(debug) System.out.println("l="+l+", r="+r+", v"+v+": "+toString(a));
	quickSort(a,l,v-1);
	quickSort(a,v+1,r);
    }
    public static void sort(int[] a){
	quickSort(a,0,a.length-1);
    }
    public static String toString(int[] a){
	StringBuffer sb = new StringBuffer();
	for (int i = 0; i < a.length; i++) sb.append(a[i]+" ");
	return sb.toString();
    }
    public static void main(String[] args) {
	if(args.length > 0 && args[0].equals("-d")) debug = true;
	Scanner sc = new Scanner(System.in);
	System.out.print("Please enter the number of data");
	int n = sc.nextInt();
	int[] a = new int[n];
	for (int i = 0; i < n; i++) a[i] = sc.nextInt();
	sort(a);
	System.out.println(toString(a));
    }
}

Recommended Posts

QuickSort
Quicksort | Largest order
quicksort in python
Python beginners organize quicksort
Quicksort without using sort
Quicksort 2 | Easy list comprehension