2
\$\begingroup\$

I read quick sort algorhitm and implemented in like this:

public List<Integer> sort(List<Integer> list) {
    if (list.size() <= 1) {
        return list;
    }

    int pivotalValue = list.get(list.size() / 2);

    List<Integer> left = new ArrayList<>();
    List<Integer> pivotalValues = new ArrayList<>();
    List<Integer> right = new ArrayList<>();
    for (Integer element : list) {
        if (element < pivotalValue) {
            left.add(element);
        } else if (element > pivotalValue) {
            right.add(element);
        } else {
            pivotalValues.add(element);
        }
    }
    List<Integer> sortedLeft = sort(left);
    List<Integer> sortedRight = sort(right);
    sortedLeft.addAll(pivotalValues);
    sortedLeft.addAll(sortedRight);
    return sortedLeft;

}

What do you think about my implementation?

\$\endgroup\$
  • \$\begingroup\$ Once upon a time Niklaus Wirth said: "Algorithms + Data Structures = Programs". Your code is a nice example how forcing an algorithm on an inappropriate data structure leads to inefficient program. Quicksort is for arrays, not for lists. Use any kind of merge sorting for lists, they need less memory and are more bad-data-proof. \$\endgroup\$ – CiaPan Apr 24 '19 at 11:21
  • \$\begingroup\$ For comparison, you might want to look at a similar code review question I posted a while back: codereview.stackexchange.com/questions/226467/… \$\endgroup\$ – markspace Dec 20 '19 at 3:07
1
\$\begingroup\$

What do you think about my implementation?

To tell you the truth, I don't think much of your implementation. Instead of in-place swaps you're creating a bunch of temporary lists and combining them after. It probably more closely resembles a merge sort than a quick sort.

Creating all those lists and merging them together requires many more iterations than the usual quick sort.

Altogether, it seems to me, that both the time and space complexity is worse than the usual quick sort.

\$\endgroup\$
  • \$\begingroup\$ I am agree about memory complexity, but I don't understand why time complexity worse than usual quick sort \$\endgroup\$ – gstackoverflow Oct 25 '18 at 17:22
  • \$\begingroup\$ @gstackoverflow - merging the lists together requires extra iterations over the data. \$\endgroup\$ – tinstaafl Oct 25 '18 at 17:25
  • \$\begingroup\$ Are you sure? lists are not arrays \$\endgroup\$ – gstackoverflow Oct 25 '18 at 17:33
  • \$\begingroup\$ @gstackoverflow - a quote from the addAll doc page The new elements will appear in this list in the order that they are returned by the specified collection's iterator. \$\endgroup\$ – tinstaafl Oct 25 '18 at 17:41
  • \$\begingroup\$ @gstackoverflow re. I don't understand why time complexity worse than usual quick sort Did you test it? What kind of run time to you get? How does that compare to Collections.sort()? \$\endgroup\$ – markspace Dec 20 '19 at 3:15

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.