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?

Improve this question
$\endgroup$
8
  • 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, 2015 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$
    – Jud
    Apr 13, 2015 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, 2015 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, 2015 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, 2015 at 22:02

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
2
  • $\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, 2015 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, 2015 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.