Sorting Algorithms

bubbleSort.js

function bubbleSort(nums){
  var swapped = false;
  do {
    swapped = false;
    for(var i = 0; i < nums.length; i++) {
      if(nums[i] > nums[i+1]) {
        var temp = nums[i];
        nums[i] = nums[i+1];
        nums[i+1] = temp;
        swapped = true;    
      }
    }
  } while (swapped);
}


// unit tests
// do not modify the below code


describe('bubble sort', function() {
  it('should sort correctly', () => {
    var nums = [10,5,3,8,2,6,4,7,9,1];
    bubbleSort(nums);
    expect(nums).toEqual([1,2,3,4,5,6,7,8,9,10]);
    // done();
  });
});




// O(n^2) time

insertionSort.js

function insertionSort(nums) {
  // let i = 2nd element in array
  for (var i = 1; i < nums.length; i++){
    // let j = 1st element in array
    for (var j = 0; j < i ; j++){
      // if second element is less than first element, enter conditional
      if (nums[i] < nums[j]) {
        // splice out element[i], 1 as delete count (one entry)
        var s = nums.splice(i, 1);
        // add spliced out element[i] before j element, use 0 count to delete nothing from nums array
        nums.splice(j, 0, s[0]);
      }
    }
  }
}

// unit tests
// do not modify the below code
describe('insertion sort', function() {
  it('should sort correctly', () => {
    var nums = [10,5,3,8,2,6,4,7,9,1];
    insertionSort(nums);
    expect(nums).toEqual([1,2,3,4,5,6,7,8,9,10]);
    // done();
  });
});


//  O(n^2) time  - two loops

mergeSort.js

function mergeSort(nums){
  if (nums.length < 2) return nums;
  
  var length = nums.length;
  var mid = Math.floor(length / 2);
  var left = nums.slice(0, mid);
  var right = nums.slice(mid, length);
  
  return merge(mergeSort(left), mergeSort(right));
};


function merge(left, right){
  var results = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]){
      results.push(left.shift());
    } else {
      results.push(right.shift());
    }
  }
  return results.concat(left, right);
};




// unit tests
// do not modify the below code
describe('insertion sort', function() {
  it('should sort correctly', () => {
    var nums = [10,5,3,8,2,6,4,7,9,1];
    var ans = mergeSort(nums);
    expect(ans).toEqual([1,2,3,4,5,6,7,8,9,10]);
  });
});

//O(n log n) time

quickSort.js

function quickSort(nums) {
  if (nums.length <= 1) {
    return nums;
  }
  var pivot = nums[nums.length-1];
  var left = [];
  var right = [];
  
  for (var i = 0; i < nums.length-1 ; i++) {
    if (nums[i] > pivot){
      right.push(nums[i]);
    } else {
      left.push(nums[i]);
    }
  }
  return quickSort(left).concat(pivot, quickSort(right));
  // return [...quickSort(left), pivot, ...quickSort(right)];
}


// unit tests
// do not modify the below code
describe('quickSort', function() {
  it('quicksort an array', () => {
    const input = [10, 8, 2, 1, 6, 3, 9, 4, 7, 5];
    const answer = quickSort(input);
    
    expect(answer).toEqual([1,2,3,4,5,6,7,8,9,10]);

  });
});


// O(n log n)