2
\$\begingroup\$

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++)
            list.add(r.nextInt(range));
        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)
                lower.add(num);
            else
                higher.add(num);
        sort(lower);
        sort(higher);

        list.clear();
        list.addAll(lower);
        list.add(rotation);
        list.addAll(higher);
        return list;
    }
}
\$\endgroup\$
  • \$\begingroup\$ sidenote: instantiate arraylists as ``List<Integer> list = new ArrayList<>()` \$\endgroup\$ – Jeroen Vannevel Jun 27 '13 at 22:34
  • \$\begingroup\$ 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. \$\endgroup\$ – David Harkness Jul 1 '13 at 15:22
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Lee Allan Jun 28 '13 at 20:51
  • \$\begingroup\$ @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. \$\endgroup\$ – kuporific Jun 28 '13 at 20:56
  • \$\begingroup\$ @LeeAllan, As far as sorting the list in place, I will add a bit more code to try and clarify \$\endgroup\$ – kuporific Jun 28 '13 at 20:58
  • \$\begingroup\$ @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. \$\endgroup\$ – David Harkness Jul 1 '13 at 15:32
  • \$\begingroup\$ Minor note: You may as well change the parameter to the second method to ArrayList since the public API specifies this already. \$\endgroup\$ – David Harkness Jul 1 '13 at 15:33
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.