Which of the sorting algorithm is (classical implementation with no enhancements) the fastest for a data set with all identical elements? And why?

How would one justify the answer to the above question logically? Logically as in without implementing the algorithms and finding the average time consumed for few sample data sets.

  • 3
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jul 4 '16 at 9:26
  • $\begingroup$ This is not homework. This was part of a question in an assignment I "did". I implemented all 3 algorithms in Python code. We were asked to justify our answer to this question and weren't allowed to run the algorithm for sets of data. I picked Insertion sort and gave some reasoning. My "underlying problem" is "Which is the most efficient out of Bubble Sort, Selection Sort, Insertion Sort for a identical set of elements?". I didn't include the code because I thought it would be redundant to write a python code for the most basic sorting implementations. Btw I don't think I violated any rules. $\endgroup$ – Ivantha Jul 4 '16 at 9:45
  • 1
    $\begingroup$ What have you tried towards an analysis of the algorithms? Where did you get stuck? What is this "reasoning" you speak of? $\endgroup$ – Raphael Jul 4 '16 at 11:50

All elements being the same is equivalent to data being sorted. The class of algorithms you are looking for is adaptive sort, which benefits from presortedness of the input data - this is the justification - since data is already sorted we have to find algorithm that uses this fact. The classic example is the insertion sort, but also Timsort (a variant of natural merge sort) and other exist. All adaptive algorithms should show the best case performance as $\mathcal{O}(N)$, which in case of insertion sort is exactly $N - 1$ comparisons, where $N$ is the length of input data.
There is no need to implement or run those algorithms, it is suficcient to show that part responsible for swapping elements is never executed, show that appropriate conditions are always true (or false depending on code) so analysis is easier.

From the possible algorithms you have provided the best cases are: Bubble sort - $\mathcal{O}(N)$, Selection Sort - $\mathcal{O}(N^2)$ and Insertion Sort - $\mathcal{O}(N)$.

| cite | improve this answer | |

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.