# Simplest quick sort using one 19-line function

This will later be be posted on my website to explain quick sort so I would like how I could improve the readability and simplicity of this demo class. I do not like my use of the stack (meaning this recursion cannot process a list with millions of values).

How could I reduce the stack impact? I think the best way would be not to use as many ArrayList instances. However, I don't know how else because I cannot use lists like int[] list because I do not know their size and surely if I just make it too big the loops will be bigger and take longer.

Here is the class in question:

import java.util.ArrayList;
import java.util.Random;

public class QuickSort {

static Random r = new Random();

public static void main(String[] args) {
int listsize = 100000, range = 100000;
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i=0; i<listsize; i++)
sort(list);
System.out.println(list);
}

public static ArrayList<Integer> sort(ArrayList<Integer> list) {
if (list.size() <= 1)
return list;
int rotationplacement = r.nextInt(list.size());
int rotation = list.get(rotationplacement);
list.remove(rotationplacement);
ArrayList<Integer> lower = new ArrayList<Integer>();
ArrayList<Integer> higher = new ArrayList<Integer>();
for (int num : list)
if (num <= rotation)
else
sort(lower);
sort(higher);

list.clear();
return list;
}
}

• sidenote: instantiate arraylists as List<Integer> list = new ArrayList<>() – Jeroen Vannevel Jun 27 '13 at 22:34
• BTW, recursion here won't be a problem. Each 3 digits of values adds 10 to the stack depth since the depth is log(n). A billion values will require only 30 stack frames at the most. – David Harkness Jul 1 '13 at 15:22

Rather than creating new Lists, your method could sort the list in place. The method you call recursively could take the list and index values; the methods would look something like this:

/**
* sorts the {@code list} in place
*/
public static void sort(ArrayList<Integer> list) {
sort(list, 0, list.size());
}

/**
* Sorts the {@code list} from {@code fromIndex} to {@code toIndex} - 1.
*/
private static void sort(List<Integer> list, int fromIndex, int toIndex) {

if (fromIndex == toIndex - 1) {
return;
} else {
// find the pivot, Collections.swap elements, etc...
// recursively call self.
}

}


Sorting the list in place reduces the amount of memory on the stack.

Also, to make the code more generic, perhaps you could sort lists of Comparable instead of Integer.

• I don't think I see how that would improve the stack, for the first function why should I sort a copy of the list? and surely the extra two params for the second are redundant because it will always sort from 0 to list.size(), otherwise its sending a too big list. I think you mean to put the lists in a non-recurring function? Please could you explain more on what you meant by "sort the list in place" (in place?). Thanks for introducing me to comparable though. – Lee Allan Jun 28 '13 at 20:51
• @LeeAllan I was incorrectly assuming your original function returned a new list and left the original unmodified. Since that is not true, I would recommend copying the Collections.sort API which returns void. – kuporific Jun 28 '13 at 20:56
• @LeeAllan, As far as sorting the list in place, I will add a bit more code to try and clarify – kuporific Jun 28 '13 at 20:58
• @LeeAllan - Passing the list to each successive call only adds a reference to the stack. The list values remain in the heap and don't get copied from call-to-call. Sorting in-place is the right way to go for an ArrayList. – David Harkness Jul 1 '13 at 15:32
• Minor note: You may as well change the parameter to the second method to ArrayList since the public API specifies this already. – David Harkness Jul 1 '13 at 15:33

Apart from the sorting in place already mentioned by @kuporific, you should

• provide comments in your code about assumptions, at least on the parameters of sort()`
• you should very clearly mark this as example code and what (standard) functions should be used in real sorting
• you should include in this code an appropriate reference to Sir Tony Hoare.

All that could be done in the context of a website, but cut-and-pasted code has a life of its own, so get these comments in the class.