CODEWITHSUNDEEP
algorithmmathsorting
anon
anon

Reputation:

Number of (n-1) comparison needed to sort n elements?

If i have n elements, say

a, b, c

Then i can use 6 comparison with (n-1) comparators to sort the elements:

if (a > b && b > c) {
   a, b, c
}
else if (a < b && b < c) {
   c, b, a
}
else if (b > a && a > c) {
   b, a, c
}
else if (a > c && c > b) {
   a, c, b
}
else if (b > c && c > a) {
   b, c, a
}
else if (c > a && a > b) {
   c, a, b
}

Now I have two questions:

  1. Do this 6 comparisations cover all possibile combinations of the 3 elements?

  2. If yes, is it true that to compare n elements, n! comparisations with (n-1) comparators are needed?

Upvotes: 0

Views: 2144

Answers (3)

Antti Huima
Antti Huima

Reputation: 25532

It is possible to sort an array of N integers using N log_2 N comparisons, which is way less than N!. These comparisons are simple ones (compare two integers only). This is where the standard complexity result O(N log N) comes for QuickSort and MergeSort. It is also proven optimal, i.e. there's no way to sort an array using less comparisons than that.

So, in order to sort N integers, you need N log_2 N comparisons with 1 comparator in each.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372972

For starters, yes, you've covered all the cases. However, what you have isn't an optimal number of comparisons. If you're allowed to have more complicated branching logic, then you can actually get away with many fewer comparisons. One way to think about this is that you could essentially run a sorting algorithm on the input, except that instead of swapping elements around, you just keep track of how the previous comparisons went and use that to influence what comparisons you make later on. Using an approach like this, you can sort with only Θ(n lg n) comparisons total (though your source code would contain Θ(n!) comparisons; you just wouldn't use all of them.)

Upvotes: 2

Dani
Dani

Reputation: 15069

Yes, because there is n! ways to sort n elements (permutations). one of them is the "Right" way, so it's true - at most n! ....

(there are better ways to sort n element array, but using your method, n! covers it)

Upvotes: 2

Related Questions