2

if we have n elements with keys:{0,1,-1} and we want to sort them,how many comparison at least we have in the worst case?

Improve this question
3
  • Sounds like homework. Also, you need to elaborate a bit on the problem. Commented Dec 17, 2010 at 19:59
  • What do you mean when you say "with keys {0, 1, -1}"? Commented Dec 17, 2010 at 20:06
  • when we want to sort cards with some keys,instead of sorting with their values we can sort them by keys Commented Dec 17, 2010 at 20:11

3 Answers 3

Reset to default
2

Here is a solution that runs in O(n):

  1. Create an array of three lists.

  2. For each key/value entry, do

    lists[entry.key + 1].append(entry)

  3. Concatenate the three lists into one long list.

This way you have no comparisons between keys.

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

2 Comments

You need to compare if an element = -1, 0, or else is 1. So 2n?
Ok, sure. ϑ(n) comparisons then. (But no comparisons between different keys.)
1

With a small fixed number of possible values, you can sort in linear time with something like counting sort.

Improve this answer

1 Comment

how can i do that with a linear time?
0

It depends on the algorithm used and distribution of the of elements.

Improve this answer

2 Comments

its about the lower bound of sorting and the decision tree model,
When he says "worst case" he probably means "worst case for best possible algorithm".

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.