Interview Questions

  • View all tutorials
  • blank
  • 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.

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

    Animation example from Wikipedia

    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])
    
    Run Code
    Run Code

    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 | javascript, bootcamp, array, sorting, App Academy
    Comments
  • +
  • 3
  • -
  • 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]) 
  • +
  • 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);
            }
    
    
    Login to submit a comment