Golf Me A Bubble Sort

Question

Your task is to create a program that performs a bubble sort on a given array until it is sorted.

---

Algorithm

In order to qualify as a bubble sort, the program must operate as follows:

• Each pass goes through the array, looks at every two adjacent elements in turn, and potentially swaps them.
• Each pass goes through the array in the same direction and without gaps. There are no partial passes - each pass must go through the whole array.
• The program must never compare or swap array elements that aren't adjacent.
• A sufficient (and finite) number of passes must be performed, such that the output array is guaranteed to be sorted. (E.g. you can safely stop if there was a whole pass without any swaps, or after len(array) passes have been made, etc.)

---

Rules

1. You must provide a sufficient explanation for how your answer does a bubble sort.
2. You may not use built-in or standard library sorting algorithms. You must make your own code.
3. Your program should take an array of numbers as input and output them in the correct order.
   • Input: 10 5 9 2 . . . (and so on)
   • The program should always output the sorted array.
   • Output can be an array returned by the program when run, or it can modify the input array in-place.
   • Output can also be the correctly ordered values separated by whitespace.
4. Speed does not matter as much as if the program functions.

---

Test Cases

• 10 5 9 2 1 6 8 3 7 4 (you can format it differently depending on your language)
• 1 2 5 4 3

---

This is code-golf, so the shortest answer in bytes wins.

Answer 1

Haskell, 55 53 bytes

f(a:b:c)=min a b:f(max a b:c)
f x=x
foldr(\_->f)=<<id

Usage example: foldr(\_->f)=<<id $ [3,1,6,4,3,8,3,1,1,2] -> [1,1,1,2,3,3,3,4,6,8]. Try it online!.

How it works: f does one iteration by keeping the minimum of the first two elements and appending a recursive call with the maximum of the first two elements and all the other elements. It stops when there are less than two elements in the list. The main function calls f length <input> times by iterating over the input list via fold but ignoring the elements.

Answer 2

Octave, 77 75 bytes

i=1;while any(diff(x)<0),i=mod(i,rows(x)-1)+1;x(i:i+1)=sort(x(i:i+1));end,x

A crude first attempt. I'm sure I'll be able to golf this a bit. Takes input as a row vector.

Explanation:

i=1;                           % Initialize iterator to 1;
    while                      % Start loop
              diff(x)     % diff(x) creates a vector with the difference between
                          % adjacent elements

              diff(x)<0   % Checks if there are less than 0 (unsorted vector)

          any(diff(x)<0)  % True if there's at least one negative difference

i=mod(i,rows(x)-1)+1      % i++, but loop around if it's equal to the number of rows          
x(i:i+1)=sort(x(i:i+1);   % Take two adjacent elements, sort them and put them back in
end,x                     % End loop and display result

Answer 3

Perl 6, 44 bytes

{.[*]=.[1,0]if [<] $_ for |(.[1..*]Z$_)xx$_}

Takes an array of numbers, and modifies it in-place (so that it is sorted after calling the lambda).

How it works

{                                          }  # A lambda taking one argument.
                                              # e.g [a,b,c]
                            .[1..*]Z$_        # Zip it with itself offset by one.
                                              # e.g. (b,a),(c,b),(d,c)
                          |(          )xx$_   # Repeat this by the input's length.
                                              # e.g. (b,a),(c,b),(d,c),(b,a),(c,b),(d,c),(b,a),(c,b),(d,c)
                      for                     # For each of those pairs:
            if [<] $_                         # If its 1st element is less than the 2nd:
 .[*]=.[1,0]                                  # Swap their values.

This works because the elements of a Perl 6 array are actually mutable item containers (akin to pointers in C except that they hide themselves well). So in the list we iterate over, each pair consists of two item containers from the array.

Answer 4

SmileBASIC, 79 bytes

DEF S A
FOR Z=0TO I
FOR I=1TO LEN(A)-1SWAP A[I-(A[I-1]>A[I])],A[I]NEXT
NEXT
END

This one is pretty simple. It just runs LEN(A) (actually LEN(A)+2 just in case) iterations of bubble sort, which is guaranteed to sort the array.

The only slightly interesting part is how I avoided using IF/THEN: SWAP A[I-(A[I-1]>A[I])],A[I]. If the two adjacent values are in the wrong positions (if (A[I-1]>A[I]) is true), it swaps A[I-1] with A[I], otherwise it swaps A[I-0] with A[I], which does nothing.

Answer 5

Javascript 98, 97, 91 Bytes

edit: removed unneeded semicolon and fixed broken code. Also moved some variable declarations and increments around.

x=>{for(h=1;h--;){for(i=d=0;d<x.length;i=d++){if(x[i]>x[d]){y=x[i];x[i]=x[d];x[d]=y;h=1}}}}

Ungolfed:

x=>{
    for(h=1;h--;){
        for(i=d=0;d<x.length;i=d++){
            if(x[i]>x[d]){
                y=x[i];
                x[i]=x[d];
                x[d]=y;
                h=1
            }
        }
    }
}

Explanation:

x=>{
    for(h=1;h--;){  //set the change tracker, h, to true. On the start of each loop, evaluate it, then decrement it. 
                    //If true, sets to false. If false, exits the loop and sets it to -1.

        for(i=d=0;d<x.length;i=d++){ //i and d are our array indexers. They're both set to null for the first loop, then on subsequent loops i is set to d, then d is incremented.
                                     // Therefore, on each subsequent loop, d will be 1 more than i.



            if(x[i]>x[d]){ //if the previous value, i, is greater than the current value, d, switch their places using the temporary variable y.
                y=x[i];
                x[i]=x[d];
                x[d]=y;
                h=1     //set the change tracker to true.
            }
        }
    }
}

It's rather simple and embarrassingly long, so any suggestions are greatly appreciated!

Answer 6

Python 2, 104 bytes

Straightforward implementation.

L=input()
while L!=sorted(L):
 for i in range(len(L)-1):
    if L[i]>L[i+1]:L[i],L[i+1]=L[i+1],L[i]
print L

Try it online

While not sorted, for each index in the list, swap with next item if greater.