I recently did an exercise where I had to distinguish between randomised quicksort and selection sort using only the executable. This was easy because they both have different average case time complexities.
However, I tried doing the same exercise where I theoretically had one of mergesort, randomised quicksort, median of three quicksort, naive quicksort, selection sort, bubble sort, insertion sort, heapsort, and needed to distinguish between them. Bubble sort could be either bubble up or bubble down.
If I consider just the asymptotic runtime, I can separate them into two categories: nlogn algorithms and n^2 algorithms.
within n^2 algorithms, selection sort is not stable and not adaptive, so it is easy to identify. However, I cannot think of any specific charactertistics or inputs that would help me distinguish between bubble sort and insertion sort.
within nlogn algorithms, naive quicksort has a worst case complexity of n^2, so it is easy to identify. However, how do I differentiable between randomised quicksort and median of three quicksort, as both are nlogn on average and have no specific best-worst case that are easy to construct? I can differentiate mergesort from memory usage, but what about heapsort, since it can be done in place? It is not stable, but it could be confused for quicksort?
So in summary my questions are:
- how to distinguish between bubble sort and insertion sort
- how to distinguish between the 3 types of quicksort and heapsort.
Thanks!
I have tried constructing different inputs that could differentiate them but to no avail. I have looked at this post (Distinguishing between sorting algorithms) but it does not answer my questions about the specific sorting algorithms.