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:
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.

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] 1st 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] 2nd 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]

Code

```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])
```

Running time

This algorithm runs in worst case O(n2) 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 = n2.
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]) ```
• +
• 1
• -
• ```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); }```
• +
• 1
• -
• Too many long lines ``` lists = [14,6,91,155,0,2,4,1,2,1,4873,5] def bu_sort(lists): length = len(lists) - 1 for number in range(length,0,-1): for a in range(number): if (lists[a] > lists[a+1]): temp = lists[a] lists[a] = lists[a+1] lists[a+1] = temp bu_sort(lists) ```
• +
• 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); } ```