Interview Questions

Implement bubble sort

Implementing bubble sort is used as an example of a slightly *harder* problem that one should solve to be prepared for the App Academy bootcamp. The source link is listed below, but the statement was:
## Sources

http://www.patheos.com/blogs/hallq/2014/06/so-youre-thinking-of-applying-to-app-academy
## Algorithm

The steps in the bubble sort algorithm are:
(1) Loop through the whole array starting from index 1
(2) If the number in the array at index i-1 is greater than i, swap the numbers and continue
(3) Once the end of the array is reached, start looping again from the beginning
(3) Once no more elements can be swapped, the sorting is complete
## Example

Let arr = [4, 2, 5, 3]
**1**^{st} loop through array
i = 1
Swap (4, 2)
arr = [**2**, **4**, 5, 3]
i = 2
Keep (4, 5)
arr = [2, **4**, **5**, 3]
i = 3
Swap (5, 3)
arr = [2, 4, **3**, **5**]
**2**^{nd} loop through array
i = 1
Keep (2, 4)
arr = [**2**, **4**, 3, 5]
i = 2
Swap (4, 3)
arr = [2, **3**, **4**, 5]
i = 3
Keep (4, 5)
arr = [2, 3, **4**, **5**]
## Animation example from Wikipedia

## Code

## Running time

This algorithm runs in worst case O(*n*^{2}) time where *n* is the number of items that need to be sorted because we potentially need to loop through the entire array every time we reach a new element, making the running time *n* * *n* = *n*^{2}.

I often use "implement bubble sort" (in a beginner-friendly language like Ruby or Python) as an example of one of the harder problems I had to do in order to get in to App Academy.

We'll go ahead and implement bubble sort in JavaScript and Python below. Bubble sort is actually a very slow algorithm that one should never attempt to seriously use, but the algorithm is simple enough to implement which is why this question might be asked.
function swap(arr, i1, i2) { var temp = arr[i1]; arr[i1] = arr[i2]; arr[i2] = temp; } function bubblesort(arr) { var swapped = true; // keep going unless no elements can be swapped anymore while (swapped) { // set swapped to false so that the loop stops // unless two element are actually swapped swapped = false; // loop through the whole array swapping adjacent elements for (var i = 1; i < arr.length; i++) { if (arr[i-1] > arr[i]) { swap(arr, i-1, i); swapped = true; } } } return arr; } bubblesort([103, 45, 2, 1, 97, -4, 67]);

def swap(arr, i1, i2): temp = arr[i1] arr[i1] = arr[i2] arr[i2] = temp def bubblesort(arr): swapped = True # keep going unless no elements can be swapped anymore while swapped: # set swapped to false so that the loop stops # unless two element are actually swapped swapped = False # loop through the whole array swapping adjacent elements for i in range(1, len(arr)): if arr[i-1] > arr[i]: swap(arr, i-1, i) swapped = True return arr print bubblesort([103, 45, 2, 1, 97, -4, 67])

mrdaniel
published this on 11/24/15 **|**

2

swap(array,i,j) { let temp = array[i] array[i] = array[j] array[j]=temp } function bubbleSort(array) { let swaps = 0; for (let i=0; i<array.length - 1; i++) { if (array[i] > array[i + 1]) { swap(array, i, i + 1); swaps++; } } if (swaps > 0) { return bubbleSort(array); } return array; }; bubbleSort([5,2,3,4,8,7,10])

brianmsj

commented on 05/19/17

0

Solution via C#:

static void BubbleSort(ref int[] array) { for (int i = array.Length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (array[j] > array[j + 1]) { Swap(array, j, j + 1); } } } } public static void Main(string[] args) { int[] array = { 8, 7, 6, 5, 3, 5, 1, 0 }; BubbleSort(ref array); string str = string.Join(",", array); Console.WriteLine(str); }

sunyikang

commented on 10/27/16

Login to submit a comment