Your task is to create a program that performs a bubble sort on a given array until it is sorted.
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.)
- You must provide a sufficient explanation for how your answer does a bubble sort.
- You may not use built-in or standard library sorting algorithms. You must make your own code.
- Your program should take an array of numbers as input and output them in the correct order.
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.
- Speed does not matter as much as if the program functions.
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.