0
$\begingroup$

I need a reference for sorting algorithm where all possible orders are considered.

example: if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ascend

The two solutions are:

n1(3) n2(5) n4(5) n3(10) and

n1(3) n4(5) n2(5) n3(10)

  1. what is the name of this technique?
  2. what is its time complexity?
  3. If I do not know the values by beginning as they may be dependent on each other sequentially, how to predict the number of all possible solutions?
$\endgroup$

2 Answers 2

1
$\begingroup$

The only way to have multiple solutions is if there are repeated values. So say your numbers are 3 10 5 5 5 3 10 3 10 5 3 10, then you can simply find the set of distinct values (3 10 5) and then sort this (3 5 10) and then since there are four copies of 3, four copies of 5, and three copies of 10, you just write out all 4!*4!*3! permutations of your objects.

  1. I do not know if there is a name of this sort of thing, aside from 'sorting objects with repeated keys'
  2. The time complexity to write them all out will depend heavily on the number of repeats of a number. In the worst case, all values are equal, and so every permutation of your $n$ objects needs to be written out, and this takes $O(n!)$ time
  3. If you can scan your list and count how many copies of each type there are, then the formula I gave above (the product of all the factorials of the frequencies) will be the number of sorted orderings
$\endgroup$
1
$\begingroup$

Just ise any regular sorting algorithm.

All other permutations are guaranteed to be formed by taking all inner permutations of elements with the same value (e.g, if there are 3 elements with the same value, we consider all arrays with all $3!=6$ permutations of those elements).

The time complexity will vary by the number of "same value elements".

In general, here are the time complexities (in terms of the number of "same value elements):

  • If all elements have the same value, we have to consider all permutations and hence the complexity is $\Theta(n!)$
  • If all elements are distinct in their values, then the time complexity is $O(n\log(n))$ since we won't consider any more permutations.
  • If there are $k_1, \dots,k_l$ elements of values $v_1,\dots,v_l$ respectively, then the complexity is $O\left(n\log(n)+\Pi_{i=1}^l k_i!\right)$
$\endgroup$

Your Answer

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

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