Examples suggest wrong time complexity

[wnesensohn]

trafficstars

Selection Sort, for example, makes the algorithm look extremely (impossibly) good at first glance - O(n) - because it's not showing the majority of the steps.

Instead of

    for (var j = i + 1; j < D.length; j++) {
        if (D[j] < D[minJ]) {
            tracer._select(j);
            minJ = j;
            tracer._deselect(j);
        }
    }

it has to be more like

    for (var j = i + 1; j < D.length; j++) {
        tracer._select(j);
        if (D[j] < D[minJ]) {
            minJ = j;
        }
        tracer._deselect(j);
    }

Bubble Sort has the same problem, as do Quicksort and Mergesort.

Normally I wouldn't mind, as showing time complexity is probably not the scope of these examples or your visualization, but the examples suggest that this is intended for beginners, and it might give them a false sense of the time complexity of these basic algorithms.

By the way, I really like the visualization, I think it could be quite helpful to aid teaching about algorithms.

[64json]

@wnesensohn That makes sense!

@TornjV Thanks a lot for concerning this issue, but the pull request is reverted. (#32) _notify method should only be used for the changed values, so that I think we should wrap up if statement with _select/_deselect and call _notify only in the if statement. I hope you understand me.

[TornjV]

#93

[64json]

Frankly, I'm not sure regarding time complexity is effective for our project. It makes harder to understand the fundamental concept of the algorithm.

[wnesensohn]

I'm not here to tell you what your project should or should not be, but consider this: Is it helpful for understanding Selection Sort by hiding the one step which defines this algorithm? Right now it visualizes like an oracle selection sort, where it automatically picks always the right value. Of course you and I know that there is no oracle, and that it has to iterate over every unsorted element. I doubt that a novice will always get this, though. On May 28, 2016 05:02, "Jason Park" [email protected] wrote:

Frankly, I'm not sure regarding time complexity is effective for our project. It makes harder to understand the fundamental concept of the algorithm.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/parkjs814/AlgorithmVisualizer/issues/28#issuecomment-222286680, or mute the thread https://github.com/notifications/unsubscribe/ABdHaqKFfZKHX8JUvvtyvpz_-24zGfQZks5qF7BQgaJpZM4IkwPJ .

[64json]

I totally agree with you for the case of Insertion Sort. In regard to time complexity, _wait() method should be called exactly once in one iteration (for statement or recursive function). Here is one of examples why that can be harder for learners to understand.

For the Binary Search algorithm, it currently calls _wait() methods twice — once after selecting range and once after selecting the middle index. If you remove _wait() method after selecting range, it may confuse learners to notice what each of steps is doing.

• (called twice) http://jasonpark.me/AlgorithmVisualizer/#scratch-paper=d2c4ad43f01813846b8d77fdde12bb7f
• (called once) http://jasonpark.me/AlgorithmVisualizer/#scratch-paper=d388613417375dbb9a85a2ed2ad961ef

It would be awesome if we can explain the concept of the algorithm as well as time complexity of it. I have gone through all the algorithms and thought that it could be worthy to take a risk of reducing some _wait() methods. Since it is kind of big deal, I want to reopen this issue and gather more opinions from others. Thanks.