cortesi / sortvis Goto Github PK

sortvis.org has the same image for both merge sort and insertion sort. It looks like it was probably just a mistake of uploading or linking to the wrong image, rather than a bug in the code.

with trunk sortvis, pry, and scurve, the tests fail in scurve.Hilbert.fromSize. here's the traceback I get.

The first exception occurs because log2(16) == 4 and dimension == 3; I'll try to get clearer on what Hilbert is doing because I don't really understand what's going on there right now.

http://sortvis.org/ is gone?

There's been a particular flavor of Quicksort in the Java library for a few years. The design space of Quicksorts is huge, sure, but I think a (basic version of) this one deserves being included in your selection.

I've implemented it in your framework here. No attribution required.

Running

sortvis weave -x 850 -t -n 20 -c gradient

as given on your website, I get this:

    110 comparisons
    67 comparisons
    154 comparisons
Traceback (most recent call last):
  File "./sortvis", line 305, in <module>
    main()
  File "./sortvis", line 282, in main
    algos.algorithms[i](track)
  File "/.../sortvis/libsortvis/algos/bitonicsort.py", line 30, in bitonicsort
    assert math.modf(math.log(len(lst), 2))[0] == 0
AssertionError

I was trying to find an implementation of Timsort in Python, and came across the one in this repository. I decided to clone the sorting algorithms in the repo to benchmark an algorithm I came up with against others, and found that your implementation reaches a maximum recursion depth at N=1400.

	Time to sort N=1400 randomly generated values between 0 and 256 using skipsort: 0.023 secs

	Time to sort N=1400 randomly generated values between 0 and 256 using quicksort: 0.050 secs

	Time to sort N=1400 randomly generated values between 0 and 256 using mergesort: 0.085 secs

	Time to sort N=1400 randomly generated values between 0 and 256 using radixsort: 0.092 secs

Traceback (most recent call last):

  < omits unnecessary trace >

  File "/home/oleg/CLionProjects/CFastSort/src/sorting_algorithms.py", line 317, in timsort
    sorted_array = timsort_merge(sorted_array, run)
  File "/home/oleg/CLionProjects/CFastSort/src/sorting_algorithms.py", line 281, in timsort_merge
    return [left[0]] + timsort_merge(left[1:], right)
  File "/home/oleg/CLionProjects/CFastSort/src/sorting_algorithms.py", line 281, in timsort_merge
    return [left[0]] + timsort_merge(left[1:], right)
  File "/home/oleg/CLionProjects/CFastSort/src/sorting_algorithms.py", line 281, in timsort_merge
    return [left[0]] + timsort_merge(left[1:], right)
  [Previous line repeated 985 more times]
  File "/home/oleg/CLionProjects/CFastSort/src/sorting_algorithms.py", line 280, in timsort_merge
    if left[0] < right[0]:
RecursionError: maximum recursion depth exceeded in comparison

Just out of curiosity, it seems you compressed the graphs so they don't show actual comparisons but just swaps (i.e. successful comparisons, which lead to a change).
Is there an option to change this, maybe even showing the two elements being compared?
I think this would give a much more detailed view of the true nature of an algorithm, e.g. showing analyzing runs such as in timsort.

with the same error as the tests did, when you use the default options. Dimensions of 8, 64, and 512 work but the default of 256 doesn't. (Because math.log(256, 2) == 8 is not divisible by three in hilbert.py)