sorting int array with only 3 elements

Question

I have this array:

int [] myarray =  {17, 6, 8};

What is the optimal way to sort this array, in pseudocode?

Thanks!

`sorted(a)` with my pseudo `sorted` function that sorts in place :) — Felix Kling, Jan 25 '11 at 12:06
Many duplicates, e.g. http://stackoverflow.com/questions/3319993/sorting-the-three-integers-program — Paul R, Jan 25 '11 at 12:26

score 26 · Accepted Answer · answered Jan 25 '11 at 12:07

26

I think this should be quite fast (ascending order):

if (el1 > el2) Swap(el1,el2)
if (el2 > el3) Swap(el2,el3)
if (el1 > el2) Swap(el1,el2)

answered Jan 25 '11 at 12:07

nan

19,595
7
48
80

6

Your classic unrolled bubble sort :-) +1. – paxdiablo Jan 25 '11 at 12:18

score 13 · Answer 2 · edited Jun 04 '16 at 23:53

13

This code makes 2 or 3 comparisons and 4 memory records in the worst case, as opposed to another answer (always 3 comparisons and 9 memory records in the worst case).

if a[0] < a[1]:
    if a[1] > a[2]:
        if a[0] < a[2]:
            temp = a[1]
            a[1] = a[2]
            a[2] = temp
        else:
            temp = a[0]
            a[0] = a[2]
            a[2] = a[1]
            a[1] = temp
    else:
        # do nothing
else:
    if a[1] < a[2]:
        if a[0] < a[2]:
            temp = a[0]
            a[0] = a[1]
            a[1] = temp
        else:
            temp = a[0]
            a[0] = a[1]
            a[1] = a[2]
            a[2] = temp
    else:
        temp = a[0]
        a[0] = a[2]
        a[2] = temp

edited Jun 04 '16 at 23:53

nitrocaster

306
2
15

answered Jan 25 '11 at 15:52

adamax

3,835
2
19
21

1

I'll give you +1 for that, adamax. Though it's butt-ugly to read, the question _did_ ask for optimal and yours seems to satisfy that :-) – paxdiablo Jan 26 '11 at 03:09
Your algorithm yields an incorrect result with {2, 3, 1} array. – nitrocaster Jun 04 '16 at 17:15
@ionree Sure, I fixed the code. If you take a look at [the original code](https://stackoverflow.com/posts/4795638/revisions), you'll see that execution path ends up swapping two elements while every element has to be moved. – nitrocaster Aug 19 '17 at 19:49
Slight optimization: replacing the first `<` comparison with `=<` would avoid an unnecessary swap if `a[0]`==a[1]`. – James Bucanek Dec 17 '19 at 18:20

score 12 · Answer 3 · answered May 17 '13 at 15:05

12

Slightly more efficient version than the unrolled bubble sort, not optimal, but still quite simple

if (el1 > el2) Swap(el1, el2)
if (el2 > el3) {
   Swap(el2, el3)
   if (el1 > el2) Swap(el1, el2)
}

answered May 17 '13 at 15:05

Eric Grange

5,931
1
39
61

I can't believe someone voted this down. It was at –1. I just upvoted it and now it's at 0. – Todd Lehman May 05 '15 at 20:45

score 6 · Answer 4 · answered Mar 01 '14 at 09:26

6

May this graphic showing a decision tree for sorting three elements helps: enter image description here

answered Mar 01 '14 at 09:26

Michael Dorner

17,587
13
87
117

Which book is this from? – johncip Apr 29 '14 at 23:28
This is from "Grundlegende Algorithmen" (http://www14.in.tum.de/~ga/) by Volker Heun -- unfortunately in German only. A very similar figure can be found in "Introduction to Algorithms" by Cormen et al.(http://mitpress.mit.edu/books/introduction-algorithms). – Michael Dorner Apr 30 '14 at 10:19
1

I knew I'd seen it somewhere... perhaps it's in the Sedgewick book, too? But for anyone else wondering it is indeed in CLRS, under "Sorting in Linear Time." Thanks! – johncip Apr 30 '14 at 17:35

sorting int array with only 3 elements

4 Answers4

Linked