Rearranging a set of numbers into order

Question

The Question

Given a set of 9 numbers, m[], which contains only numbers 1 through 9 in a random order, with no two numbers being the same, create a program in any language which rearranges the number to be in numerical order (1, 2, 3, etc. etc.) by only switching two numbers which are next to each other (ie. 1, 3, 2 → 1, 2, 3).

Rules

• You may only modify the set by switching two numbers which are next to each other
• The ending numbers (1 through 9 in order) should be contained in m[]
• You can use any language you would like
• The answer with the smallest amount of bytes wins

Edit:

Your code does not have to print the output, but the rearranged array must be in m[].

Answer 1

CJam, 15 bytes

q~A{{a+$~}*]}*p

How it works:

q~                     e# Read the CJam styled input array (For ex. [1 3 4 2 5 6 8 7 9])
  A{        }*         e# Run the loop 10 times. This is enough times for a 10 length
                       e# input array in a bubble sort
    {    }*            e# reduce
     a+$~              e# Rearrange the pair so that they are sorted
           ]           e# After each loop, wrap the numbers back into the array
              p        e# Print the array after the loops are done

Try it online here

Answer 2

Mathematica, 38 bytes

#//.{a___,b_,c_,d___}/;b>c:>{a,c,b,d}&

This is an unnamed function taking an array, which applies a replacement rule until the pattern cannot be found any more. The pattern is a list which has two consecutive elements b and c where b > c, and the rule says to swap the b and c but otherwise leave the array untouched.

There's a lot of syntactic sugar here, but the code is actually very readable if you know a bit of Mathematica:

# //. {a___,b_,c_,d___} /; b>c :> {a,c,b,d} &
^  ^     ^   ^          ^      ^            ^
|  |     |   |          |      |            |
|  |     |   | Declares an unnamed function |
|  |     |   |          |      |
| The function's argument      |
   |     |   |          |      |
   | Replace while possible... |
         |   |          |      |
         | Zero or more list elements.
             |          |      |
             | A single list element
                        |      |
                        | A condition for the pattern
                               |
                               | What to replace the pattern with

Answer 3

Python 3, 72 bytes

from random import*
while m!=sorted(m):p=randrange(8);m[p:p]=m.pop(p+1),

The bogosort (aka stupid sort) approach: swap neighbor elements randomly until the array will be sorted. Usually runs under a second.

2 bytes thanks to @xnor.

Answer 4

Python 2, 45

for i in range(8)*8:m[i:i+2]=sorted(m[i:i+2])

Cycles around the list, sorting consecutive pairs of elements. The index i cycles through 0,1,2,3,4,5,6,7 eight times, which guarantees all elements bubble through and the list is sorted.

Answer 5

Pyth, 13 - 15 bytes

Solution which performs the requested swapping, and produces no output:

#X=Qhf>FT.:Q2

Solution which performs the requested swapping, and prints out the intermediate state of the list at every step:

#QX=Qhf>FT.:Q2

Solution which performs the requested swapping, and prints out the final state of the list:

#X=Qhf>FT.:Q2;Q

Demonstration of the middle solution above.

The method of swapping adjacent values is taken from @Jakube's answer.

The program uses #, the loop until error statement, to swap an adjacent pair of misordered elements until no such pair exists, at which point h, the head function, throws an error, ending the program.

Answer 6

Retina, 95 93 bytes

Not particularly competitive (and probably still golfable), but here we go...

(.)1
1$1
([^1])2
2$1
([4-9])3
3$1
([5-9])4
4$1
([6-9])5
5$1
([7-9])6
6$1
(8|9)7
7$1
)`98
89
<empty>
<empty>

Where <empty> should be an empty line.

Since all numbers are single digits, this just expects a string with all 9 digits as the input and will print 123456789 after successfully sorting it. Each stage performs a single swap and the )1` indicates that all but the last stage should be repeated until the result stops changing.

The empty stage at the end is necessary, because otherwise we would get intermediate results every time the 98 stage is processed.

Here are all the intermediate results (whenever it changes) for an example run:

451629387
451269387
451263987
451263978
415263978
412563978
412536978
412536798
412536789
142536789
124536789
124356789
123456789

(I obtained this by adding the : option to each stage, and got rid of consecutive duplicates manually.)

Answer 7

Pyth, 17 bytes

uXGhaf>FT.:G2]Z)Q

Switching items in a list is really expensive in Pyth. So here's a fun solution, that stretches the rules a little bit. It's probably not valid.

Try it online: Pyth Compiler/Executor

Explanation

First of all, the time complexity of my code is O(n^3). But this is not the interesting part. The question doesn't say anything about the complexity.

The critical part is, how I switch two elements in the list. Let's say I want to switch the elements m[3] and m[4]. I don't care about the indices 3 and 4 at all. I simply create a second list, that replaces every element equal to m[3] with the number m[4] and every number equal to m[4] with the value m[3]. Since the list doesn't contain duplicates, this simulates switching these two values. If there were duplicates, like in the input [1, 3, 2, 2], the output would be [1, 2, 3, 3]. And if you give the input [1, 2, 1], it would end in an infinite loop. I don't explicitly create the second list, it's just part of Pyth's implementation of the translate-method. If you print out the current lists (see here), it give the correct values, which you would expect.

                   implicit: Q = input list
u               Q  set G = Q, update G as long with the following statements, 
                   until it stops changing: 
         .:G2         all pairs (G[i],G[i+1])
     f>FT             filter for pairs T, where T[0] > T[1]
    a        ]Z       add to this list of pairs [0] 
                      (ensures that the filtered list is always non-empty)
   h                  take the first element
 XG            )      translate G by this pair (switches the values T[0] with T[1])
                   print implicitly at the end 

Answer 8

JavaScript (ES6) 56

A recursive function that rearranges the given list in place.

F=l=>l.some((v,i)=>v>l[++i]&&[l[i-1]=l[i],l[i]=v])&&F(l)

Notes

• In JS, for any numeric value v : v > undefined == false, v < undefined == false. So going outside the array bounds is not a problem if we use the right comparison

• When the array at last is sorted, the function inside 'some' return false and recursion ends

• The value returned in case of a swap is a 2 element array, and its value is always 'truthy'. That works even when one or more array elements are 0

• In fact the function works with any numeric input, not only single and not repeated digits. Did not found a way to take advantage from this OP constraint.

Test using snippet (in Firefox) - the snippet version output the current list values at each step.

F=l=>(log('L='+l), l.some((v,i)=>v>l[++i]&&[l[i-1]=l[i],l[i]=v])&&F(l))

function log(x) {
   L.innerHTML = L.innerHTML +x+'\n' 
}

function go() {
  l = I.value.split(/\D+/g).map(x=>x|0)
  F(l)
  O.innerHTML = '' + l
}  

go()

Unsorted: <input id=I value="2 8 4 7 5 3 9 1 6"><button onclick="go()">-></button>
<br>Sorted: <span id=O></span>
<br>Operations log:<br>
<pre id=L></pre>

Answer 9

Javascript (ES6), 66 61 53 bytes

Thanks to the new rule, I can reduce even further :)

f=x=>x.map((a,i)=>a<(b=x[--i])&&f(x,x[i]=a,x[i+1]=b))


// Snippet demo: (Firefox only)
f(z=prompt().split(/\D+/).map(x=>+x))
alert(z.join(', '));

Commented

f=x=> // recursive function f
    x.map( // map function to array
        (a, i)=> // a = current value, i = current index
            a < (b = x[--i]) && // poll value of previous index, compare less than
                                // comparison always false at first index as undefined will always be less
                f(x, x[i] = a, x[i + 1] = b) // if true, swap values and call f
    )

Answer 10

C, 183

main(c,d,s){int a[10];for(c=0;c<10;c++)scanf("%d", &a[c]);for (c=0;c<10;c++){for(d=0;d<10-c-1;d++){if(a[d]>a[d+1]){s=a[d];a[d]=a[d+1];a[d+1]=s;}}}for(c=0;c<10;c++)printf("%d", a[c]);}

It's not golfed yet, other than variable names.

Answer 11

Haskell, 59 bytes

s e(h:t)=min e h:max e h:t
f l=iterate(init.foldr s[9])l!!9

The function s puts an element e in front or at the second place of a list depending on if it's less or greater than the first element of the list. Folding s into the input list lets the smallest element bubble to the front. I'm folding into a list containing a single 9 which I immediately remove afterwards with init, so that I don't have to check for empty lists in s. iterate repeats the folding process forever creating a list of intermediate results. The final result is the 9th element of this list.

Answer 12

Perl, 68 bytes

{for(0..7){if($m[$_]>$m[$_+1]){splice@m,$_,2,$m[$_+1],$m[$_];redo}}}

Ungolfed code

 {                                             # Block runs once unless redo is called

     for (0..7) {                                 # Loop index is in $_

         if ($m[$_] > $m[$_+1]) {                 # Check if swap needed

             splice @m, $_, 2, $m[$_+1], $m[$_];  # Replace a two element slice of
                                                  # the array with those 
                                                  # two elements reversed

             redo                                 # Restart the block over
         }
     }
}