Results 1 to 18 of 18
  1. Default Quicksort implementation issue - Java


    Update: Working on a void method now to preserve the in-place operation.
    Update 2: Working alternative, doesn't seem to help enough, though. Previous implementation sorted a 6-million-index array in 45+ seconds, this one 10~15 seconds. Merge Sort takes 1.3~1.6 seconds.

    proper in-place implementation


    This is my attempt at an in-place randomized Quick Sort implementation. As it turns out, the code works fine, just too very slowly compared with Merge Sort.

    From what I do know, the run time is expected to be O(nlogn), practically better than Merge Sort due to smaller coefficients and in-place swapping.

    So, what am I doing so too horribly wrong to have jeopardized the algorithm so badly? Aside from maybe building two copies of the array itself and rebuilding into a brand new array, which kinda destroys the whole in-place thing.

    Code:
    outdated sauce


    The recursion doesn't seem to be faulty, the work outside of each recursion step is as expected: splitting the array into two subproblems, then re-combine their sorted versions. I just can't figure out where the issue might be.

    EDIT: There's also a minor Stack Overflow issue with inputs of size larger than 6,000,000. Seems to have something to do with the process of generating random integers.

    console
    Last edited by Kalovale; 2012-04-27 at 07:55 PM.

  2. Default Re: Quicksort implementation issue - Java


    Hmm. So, is it just slower by a constant factor? It looks to me like you're doing maybe ~4 times as many array accesses as you need to, so you could speed it up by a small constant factor by being a bit more clever (e.g. by storing A[from] in a temporary variable and eliminating some unnecessary swaps).

    But I don't see anything fundamentally wrong here that would make it more than about 10x slower than it should.

    Also is the merge sort you're comparing to one that you wrote in Java too?

  3. Default Re: Quicksort implementation issue - Java


    Yes, here's the merge sort, there should be plenty of things to improve on, but I'll save that for after I get quick sort to work:

    sauce


    I'll run a few tests with different input sizes and see how the run time grows.

    EDIT:
    results


    Obviously it's not just off by a constant.

    The boolean check is indicative of a successful sort, it's done outside of the timing period.
    main()
    Last edited by Kalovale; 2012-05-02 at 02:01 AM.

  4. Default Re: Quicksort implementation issue - Java


    This is because of your choice of array to be sorted. You're using random numbers less than 1000 to fill your 6 million size array. This is going result in a lot of ties, which is quick sort's worst case situation.

    If you change the RNG.nextInt(1000) to RNG.nextInt(size), you will see quick sort being faster than merge sort.

  5. aka ClawofBeta Straight Male
    Corn's Avatar [Jr. Event Coordinator]

    IGN: ClawofBeta
    Server: LoL.NA
    Level: 30
    Job: Bot Lane
    Guild: N/A
    Alliance: N/A
    New_Jersey

    Default Re: Quicksort implementation issue - Java


    Was going to mention this. Quicksort is only faster than mergesort in certain scenarios.

    Also an FYI quicksort has to sort completely random situations. If there's any semblance of order mergesort can be faster.

  6. Default Re: Quicksort implementation issue - Java


    I'm not convinced that is the case, for three possibly related reasons:

    1. I neglected to mention that I copied someone's implementation and it ran quicker than my merge_sort on this same input.

    2. As well as I can remember my own code, I do nothing in the case of ties; It's just one check, move on. Swaps only happen when the accessed index has smaller value than the pivot, which is why I also believe that my code is doing the (almost) minimum number of swaps necessary (one swap for each index less than pivot lying on the right side of pivot).

    3. quickSort's worst case involves choosing pivot values on either extreme ends, thus ending up doing the maximum number of swaps, i.e. n-1. E.g. Choosing 9 or 1 in the [9;8;7;6;5;4;3;2;1] array will both result in 8 swaps for the partitioning step; whereas choosing 4 in [4;4;4;4;4;4;4;4;4] will result in no swaps at all (just linear scan and comparison).

    @ Corn: Randomized quickSort makes no assumptions about the input's order, due to the internal randomization step. (Random + more random = random // deterministic + random = random). Its runtime is "on average" O(nlogn) regardless what input is given, with a smaller constant coefficient than mergeSort's. Theoretically, quickSort's worst runtime is O(n^2), but this almost never happens (regardless of input). I still haven't quite mastered the proof, though.
    Last edited by Kalovale; 2012-05-04 at 01:42 PM.

  7. Default Re: Quicksort implementation issue - Java


    1. Maybe you should paste their code here then.

    2.3. The whole point is that quicksort is only fast when two partitions are roughly the same size. When you have a large number of duplicate values one partition will be much larger than the other, causing more recursive calls. In the case of the entire array being duplicates, it becomes the same as selection sort, i.e. O(n^2). You should be counting the number of comparisons there, not number of swaps.

    When people discuss sorting algorithms, they generally assume there are no duplicate values.

  8. Default Re: Quicksort implementation issue - Java


    When the array is passed into the function, does it passed as reference or by value?
    If the array is cloned many times, it would slow down a lot; delete the intermediate arrays immediately when it become useless (vs. waiting for garbage collection) will help speeding up the recursive process;

    I haven't deal with java for a long time, so I could be wrong.

  9. Default Re: Quicksort implementation issue - Java


    It's passed by reference in Java so there's no problem there.

  10. Default Re: Quicksort implementation issue - Java


    Merge sort is supposed to be faster than quick sort.
    On worst case scenarios quick sort is O(n^2) while Merge sort is O(nlogn).

  11. Default Re: Quicksort implementation issue - Java


    Profile your code. Find a Java profiler or use the poor man's profiler: run your code in the debugger, hit break a few times, see where it usually is when you break. Performance problems are often not where you think.

  12. aka ClawofBeta Straight Male
    Corn's Avatar [Jr. Event Coordinator]

    IGN: ClawofBeta
    Server: LoL.NA
    Level: 30
    Job: Bot Lane
    Guild: N/A
    Alliance: N/A
    New_Jersey

    Default Re: Quicksort implementation issue - Java


    That's only in worst case.

  13. Default Re: Quicksort implementation issue - Java


    http://www.algolist.net/Algorithms/Sorting/Quicksort

    sauce


    I think I get what you're trying to say, which is essentially the same thing I said, just from a different perspective. To put it into my language:

    "When dealing with complete duplicates, any values chosen to be pivot will end up being the extreme value that quickSort sucks at dealing with. In the same manner, with a large number of duplicates, the probability of picking a good pivot (one that gives a 25-75 split or better) becomes significantly smaller when the duplicates happen to be a bad pivot choice. With no duplicates, this probability is 50%."

    This is the new execution time for quick_sort where possible values are of the range [0, 100000+):
    results


    merge_sort did not benefit from this change.
    merge_sort run time


    I would call this a satisfactory result, thanks happylight, though two issue remain:

    1. Why is their implementation efficient even in the case of duplicates?

    2. Why did I get StackOverFlow errors?

  14. Default Re: Quicksort implementation issue - Java


    1. The magic is in this segment:
    Code:
          while (i <= j) {
                while (arr[i] < pivot)
                      i++;
                while (arr[j] > pivot)
                      j--;
                if (i <= j) {
                      tmp = arr[i];
                      arr[i] = arr[j];
                      arr[j] = tmp;
                      i++;
                      j--;
                }
          };
    It moves any value less than the pivot to one partition and any value larger than the pivot to the other partition. So any value equal to the pivot stays where they were. Whereas your code would move all values equal to the pivot to a single partition. I've never actually seen quick sort implemented their way. It's quite cool.


    2. Essentially each duplicate value causes an extra recursive call. You ran out of memory for function stacks.

  15. Default Re: Quicksort implementation issue - Java


    I can see how that makes sense. Leaving the equal values in both arrays lowers their concentration, which in turn lowers their probability of being picked, and even if they are picked, their effects are lowered due to low concentration. It's quite cool.

    This would mean that for arrays of exact duplicates, this implementation would take just as long to run as mine does.

  16. Default Re: Quicksort implementation issue - Java


    Er no? With an array of all duplicates, their implementation would still run as fast as merge sort whereas yours would be as slow as selection sort.

  17. Default Re: Quicksort implementation issue - Java


    Let's see.

    Theirs does:
    - n comparisons
    - n/2 swaps
    - (50<>50) split
    - The total work done outside of the recursion is O(n), and they have logn number of recursion layers.

    Mine does:
    - n comparisons
    - no swaps
    - (1<>n-1) split
    - The total work done outside of the recursion is O(n) -albeit with a lower coefficient-, and I have n-1 number of recursion layers.

    Seems to be the case. I should somehow circumvent this.

  18. Default Re: Quicksort implementation issue - Java


    Ah, yes. Duplicate values would do it.

    The other thing is, if you anticipate having to sort arrays with many duplicate values, you can also treat values equal to the pivot as a third "partition" and not recurse on it at all. This requires a bit more overhead but would yield O(n) time on an array of all duplicates, which is the best possible result.

  19.  

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •