0

I've been studying sorting algorithms and had a question about the number of comparisons in each sorting algorithm.

Let's say we have a sorting algorithm (insertion sort, quicksort, anything). Then I want to count the number of comparisons using different files. These files have items that are randomized and not in order. For example, file 1 has 10 items, containing letters a to j. Then we have another file (again, 10 items) containing integers 1 to 10. Then we have another file (10 items), containing float numbers 1.1111111111 to 10.1111111111. If we want to sort these using any sorting algorithm (for the first one we sort in alphabetical order and others from smallest to largest number).

If we count the number of comparisons (in a quicksort algorithm, for example) in each file, would they be the same since we are comparing the same number of items, or does the length of the items change the number of comparisons (a vs 10.1111111)? If they are the same, is it the case for all sorting algorithms (at least the ones I mentioned) or just some? I don't think it's a hard question (sorry), but I'm over-thinking as usual. I'm guessing that they would be the same, but I'm not really. Would someone care to explain?

Improve this question

2 Answers 2

Reset to default
1

The number of comparisons depends on the initial state. the sorting algorithm and the specific implementation.

For example:

  • The implementation could make a first pass to check if the set is already sorted up or down to avoid unnecessary work or even a worst case scenario. This has a small cost but can avoid a pathological case. The number of comparisons will be very different for the same set between an implementation that does and one that does not.

  • Some implementation choices such as which element to select as a pivot in qsort() will greatly impact the number of comparisons for identical sets.

  • Even worse: to avoid quadratic worst case in qsort() that can be triggered more of less easily as described in Kernighan's paper anti qsort, one can implement qsort() to make non deterministic choices of pivot values, using some source of randomness. For such an implementation, the number of comparisons may vary, even for sorting the same set repeatedly. Note that this can produce a different order if some elements compare equal, due to qsort()s unstability.

Your teacher's question cannot be answered precisely unless you know both the initial state and the sorting algorithm specific implementation. Even best case and worst case numbers depend on the implementation details.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

You are considering performance of algorithm with varies in input files. To standardize this kind of problems, scientist already gave three types of performance for every algorithm :

  1. Best Case - Lower Bound on cost
  2. Worst case - Upper Bound on cost
  3. Average case - "Expected cost"

Now if you want to get number of comparison it makes with particular input then you can form your own mathematical model. But rather for standardization you can think of these three types. And another thing is, number of comparison doesn't varies with input type, but in which order data is. That means if you pass sorted input to the insertion sort, it will give you O(N) with approx N comparisons. But if it is in reverse form, then its worst case.

This is the analysis of sorting: Sorting Comparision

Reference : Princeton course

Improve this answer

3 Comments

I'm aware of this, what I want to know is that if we introduce a variable in the sorting function and count the number of comparisons, would it be the same?
Nope. It varies with input order.
@Bobby: if your comparison function increments a global counter and returns the comparison value correctly, you should get a consistent number of comparisons for a given set and a given sorting algorithm and implementation. But not necessarily: the sorting algorithm may make a non deterministic choices to reach the same result.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.