Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is partly a programming and partly a combinatorics question.

I'm working in a language that unfortunately doesn't support array structures. I've run into a problem where I need to sort my variables in increasing order.

Since the language has functions for the minimum and maximum of two inputs (but the language does not allow me to nest them, e.g. min(a, min(b, c)) is disallowed), I thought this might be one way towards my problem.

If, for instance, I have two variables $a$ and $b$, I only need one temporary variable so that $a$ ends up being less than or equal to $b$:

t = min(a, b);
b = max(a, b);
a = t;

for three variables $a,b,c$, the situation is a little more complicated, but only one temporary variable still suffices so that $a \leq b \leq c$:

a = min(a, b);
t = max(a, b);
c = max(t, c);
t = min(t, c);
b = max(a, t);
a = min(a, t);

Not having a strong combinatorics background, however, I don't know how to generalize the above constructions if I have $n$ variables in general. In particular, is there a way to figure out how many temporary variables I would need to sort out $n$ variables, and to figure out what is the minimum number of assignment statements needed for sorting?

Thanks in advance!

share|improve this question
2  
Out of curiosity, what programming language are you using? –  lewellen Jul 21 '11 at 17:22

2 Answers 2

up vote 2 down vote accepted

Many sorting algorithms work by performing a sequence of swaps, so you need only one extra variable to implement them for any fixed $n$. What you're doing is effectively unrolling the entire algorithm loop into a sequence of conditional assignments.

The number of assignments will be three times the number of swaps, and I think the exact number may depend on the sorting algorithm. It'll be on the order of $n \log n$, though.

share|improve this answer

I'd like to expand on Rahul's answer and note that, given that the number of items you're going to sort is presumably fixed and fairly small, you might want to take the extra effort to look up an optimal (or near-optimal) sorting network for that number of items.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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