1
\$\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\$ I think the title fails to name the distinguishing feature of this implementation: 3-way distributing values to Lists. You present uncommented/undocumented code. You needlessly forsake genericity. (I was tempted to down-vote the question out of considering the code presented abysmal - the voting hints stress usefulness of the question.) \$\endgroup\$ – greybeard Nov 24 '18 at 18:27
  • \$\begingroup\$ @greybeard I think code is self explained \$\endgroup\$ – gstackoverflow Nov 24 '18 at 20:21
  • \$\begingroup\$ Try using your method in a separate source file. See what tool support you get from your IDE of choice with or without doc comments. Revisit your code a couple of years later. \$\endgroup\$ – greybeard Nov 24 '18 at 21:00
  • \$\begingroup\$ @greybeard, could you provide concrete points you don't like? It is really unclear what you to say \$\endgroup\$ – gstackoverflow Nov 24 '18 at 21:17
  • \$\begingroup\$ could you provide concrete points you [have an opinion on]? I try to refrain from getting into details of uncommented code. \$\endgroup\$ – greybeard Nov 24 '18 at 21:19
0
\$\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.