4
$\begingroup$

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!

  • 2
    Out of curiosity, what programming language are you using?2011-07-21

2 Answers 2

2

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.

2

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.