0
$\begingroup$

I am given an array {1, 2, 3, 5, 4, 6} and I am asked

What sorting algorithm might you want to use to sort the given list, and why?

Initially I think using Bubble sort would be the best option due to it's best case linear ($O(n)$) complexity and due to the fact that you'd only need to use 1 swap. However, the more I look at the problem I am starting to think that Insertion Sort may also be efficient in this situation.

Insertion sort and Bubble sort both have the same best, average, and worst case time complexities as well as the same space complexities. Are neither one of these algorithms the proper one to be used on this array? If not, why not?

$\endgroup$
  • 2
    $\begingroup$ I think this is a bit vague. I mean really, for sorting a list of 6 elements, take any sensible sorting algorithm that solves the problem. It looks nearly sorted, so maybe the question is asking for a suitable sorting algorithm for such a case. $\endgroup$ – Juho Apr 13 '15 at 19:46
  • $\begingroup$ @Juho right, that's why I am having problems answering the question. It seems like there are many algorithms that would work just fine, therefore I'm not sure which one would be 'optimal' $\endgroup$ – Jaken Herman Apr 13 '15 at 19:47
  • 1
    $\begingroup$ I think there is a difference in the number of comparisons made by each. Is the number of comparisons made correct? $\endgroup$ – Jake Apr 13 '15 at 19:51
  • 2
    $\begingroup$ The question seems to be about what algorithm would be fastest for this specific example. In such a case, complexity does not matter. But your guess is as good as mine. $\endgroup$ – babou Apr 13 '15 at 21:32
  • 1
    $\begingroup$ Take all the algorithms you know (from class, I assume), execute them (on paper) and count comparisons, swaps, number of executed statements. Which wins? That one. $\endgroup$ – Raphael Apr 13 '15 at 22:02
5
$\begingroup$

An inversion in a permutation $\pi(1),\ldots,\pi(n)$ is a pair of indices $i < j$ such that $\pi(j) < \pi(i)$. Denote the number of inversions by $I(\pi)$. In your example, $I(123546) = 1$. It is well-known that insertion sort runs in time $O(I + n)$ on a permutation of length $n$ having $I$ inversions. Due to this guarantee, insertion sort is asymptotically optimal when the number of inversions is small, $I = O(n)$.

$\endgroup$
  • $\begingroup$ Bubblesort variants that notice if the array is already sorted attain the same bound (here and in many other cases), so why prefer Insertion Sort? I think a reasonable answer would cite more exact analyses, or calculate the numbers for this example explicitly. Asymptotics don't make sense here. $\endgroup$ – Raphael Apr 13 '15 at 22:00
  • $\begingroup$ Here is what Wikipedia has to say: The only significant advantage that bubble sort has over most other implementations, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted is efficiently built into the algorithm. ... However, not only does insertion sort have this mechanism too, but it also performs better on a list that is substantially sorted (having a small number of inversions). $\endgroup$ – Yuval Filmus Apr 13 '15 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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