3
\$\begingroup\$

This question already has an answer here:

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 , so the shortest answer in bytes wins.

\$\endgroup\$

marked as duplicate by mbomb007, jacksonecac, 0 ', Mike Bufardeci, insert_name_here Jan 30 '17 at 19:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 7
    \$\begingroup\$ Saying "use this algorithm" is usually seen as a non-observable requirement. Perhaps "perform one iteration" of bubble sort is a better challenge? \$\endgroup\$ – FlipTack Jan 28 '17 at 18:43
  • 7
    \$\begingroup\$ Also, 10 minutes in the sandbox isn't very long. You should leave it there for longer (at least a day, if not more) to get more feedback first. \$\endgroup\$ – FlipTack Jan 28 '17 at 18:45
  • 5
    \$\begingroup\$ It seems very similar to this challenge, except that one has a parameter for max comparisons. \$\endgroup\$ – FlipTack Jan 28 '17 at 18:47
  • 1
    \$\begingroup\$ It's well known that many people mix up the various simple quadratic sorts. I agree with FlipTack that asking specifically for bubble sort makes a bad question, but I would add that if you do want to require a specific algorithm then you must clearly specific exactly what qualifies as that algorithm. This question as it stands is inviting arguments over the difference between insertion sort, selection sort, and bubble sort. \$\endgroup\$ – Peter Taylor Jan 28 '17 at 19:51
  • 1
    \$\begingroup\$ @PeterTaylor: It could be distinguished from those two, by requiring that comparisons are only ever allowed between two adjacent elements. \$\endgroup\$ – smls Jan 28 '17 at 20:03
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It is fine to use this. \$\endgroup\$ – ckjbgames Jan 28 '17 at 20:14
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Explanation please? That is in the requirements. \$\endgroup\$ – ckjbgames Jan 30 '17 at 16:17
  • \$\begingroup\$ Sorry about that! I've edited it into the bottom of my original post. \$\endgroup\$ – Jhal Jan 30 '17 at 17:06
0
\$\begingroup\$

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.

\$\endgroup\$

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