Quote (Minkomonster @ Oct 2 2014 01:17am)

This is exactly what I am talking about. You can do run-time analysis without scaring your students into thinking they did something wrong by requiring that their sorting algorithm "work" with an astronomically high set of data. You can teach the same concept with data orders of magnitude lower than that.

Quote (AbDuCt @ Oct 2 2014 12:23am)

Since we are talking about sorts. I have no idea what sort ruby uses for it's default sort() method. It's incredibly fast, so fast that in order to get results in my tests I have to bump up the test data set to 100,000 numbers which it finishes with 0.008 seconds. Radix sort on the same data does 0.0730001. It must be a bucket type of sort implemented in C or something.

edit:: Yep just checked rubys sort is implemented in C located in array.c, although I have no idea what method they use for sorting.

Quote (Minkomonster @ Oct 2 2014 01:29am)

It's a natively implemented quicksort with heavy optimizations.

Quote (AbDuCt @ Oct 2 2014 12:30am)

Interesting. It makes me all warm and fuzzy inside.

Quote (Minkomonster @ Oct 2 2014 01:29am)

It's a natively implemented quicksort with heavy optimizations.

Quote (carteblanche @ Oct 2 2014 12:33am)

i remember scratching my head when i was looking at java's internal array sort. iirc it used insertion sort for really small arrays. shit got real.

Quote (Minkomonster @ Oct 2 2014 01:02am)

You can do that simply by plugging in the array size to N^2 of O(N^2). You don't tell a bunch of freshmen that your implementation must work for 10^7 sized array. Because before you talk about run-time analysis of comparison based sorting algorithms, all they will think is "shit I ran the program and it froze...I must have messed up the implementation." So you end up having issues like what OP is having. His algorithm is a fine insertion sort, but he is too hung up on making it work for 10^7 because he hasn't been taught anything about the run-time of O(n^2) algorithms. This was a shitty assignment.

The correct way to do this would be to have him implement insertion sort and then give him sample test data. Then have him implement bubble sort, selection sort. Then have him implement mergesort or quicksort. Then after you have gone through all of those tell him to run each with new sample data. This time the data has the 10^7 array. Now he gets to see each sorting algorithm handle that data. After he does that he is to answer one question: Explain why quicksort and mergesort were able to sort this data but insertion and selection sort took ages. By then, in lecture, the professor would have already gone over each algorithm and explained its run-time and what it means. Now the student is equipped to handle this concept.

Do you see the difference?