1
$\begingroup$

I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an integer dataset. However, I am wondering if there are any other variables which I can modify, for example standard deviation, in the integer dataset itself that would be of any benefit to my comparison.

$\endgroup$
1
  • $\begingroup$ Range, and, related, multiplicity of item values. $\endgroup$
    – greybeard
    Commented Apr 11, 2021 at 7:32

2 Answers 2

1
$\begingroup$

Try these: Sorted. Reverse sorted. Two sorted halves. One half ascending, one half descending. Sorted with 0.1%, 1%, 10% random changes. Random. All values equal, 99% equal, 50% equal. Two different values only.

Unless you are 100% sure that one of these case cannot happen (and you are never 100% sure), all of these should run in a reasonable time. Some of them, like "Sorted" or "sorted with 0.1% random changes" can run much faster than others. If these cases are common, then you would want them to run faster.

$\endgroup$
0
$\begingroup$

The simplest is not doing a proper shuffle, that is having partially (reverse) sorted sequences, in extremis this can be the entire range is sorted except a few elements at the end that need to be inserted somewhere in the range.

For comparison sorts the distribution of elements doesn't make a difference, only how many duplicate values there are. This is something you can adjust as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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