Sorting (bubble, selection, merge)

Directions

Implement bubbleSort, selectionSort, and mergeSort

[0]

Try it first#

Copy the stub, make the 3 tests pass on your machine, then open the solution. The reveal is remembered per page in this browser.

JSexercises/sorting/index.js

const  bubbleSort = (arr) => {let swaps = Infinitywhile(swaps > 0){  swaps = 0  for (let i = 0 ; i < arr.length; i++){    if( arr[i] > arr[i+1] ){      const temp1 = arr[i]      const temp2 = arr[i+1]      arr[i] = temp2      arr[i+1] = temp1      swaps +=1    }  }}return arr;} function insertionSort(arr){  for(let i = 1; i < arr.length; i++){    let currentNum = arr[i]    let j = i - 1    while(currentNum < arr[j]){      const checkValue = arr[j];      arr[j] = currentNum;      arr[j + 1] = checkValue;      j--;    }  }  return arr}   function selectionSort(arr) { } function mergeSort(arr) {  if (arr.length <= 1){    return arr  }   const centerPoint = Math.floor(arr.length / 2) // 7/2 = 3.5  const left = arr.slice(0,centerPoint);  const right = arr.slice(centerPoint);   return merge(mergeSort(left), mergeSort(right)) } function merge(left, right) {    const results = [];     while(left.length && right.length){      if(left[0] < right[0]){        results.push(left.shift())      } else {        results.push(right.shift())      }    }     return [...results, ...left, ...right]}  // [3, 7, 9, 2, 14, 5, 13, 22] [3,7,9,2,5,13],14,[22][3,7,9,2,5,13] 2,3,7,9,5,13 [3,7,9]// 4[]            //4[]// 2[] 2[]        // 2[] 2[]// 1[] 1[] 1 [] 1[]  // 1[] 1[] 1[] 1[]  function quickSort(arr){ if(arr.length < 2){   return arr } const midpointIndex = Math.floor(arr.length/2); const pivot = arr[midpointIndex] const myLeftArr = []; const myRightArr = [];  for(let i = 0; i < arr.length; i++){  if(i !== midpointIndex){    arr[i] < pivot ?      myLeftArr.push(arr[i]):      myRightArr.push(arr[i]);  } } return [...quickSort(myLeftArr), pivot, ...quickSort(myRightArr)]} module.exports = { bubbleSort, selectionSort, mergeSort, merge, insertionSort, quickSort };const  bubbleSort = (arr) => {
let swaps = Infinity
while(swaps > 0){
  swaps = 0
  for (let i = 0 ; i < arr.length; i++){
    if( arr[i] > arr[i+1] ){
      const temp1 = arr[i]
      const temp2 = arr[i+1]
      arr[i] = temp2
      arr[i+1] = temp1
      swaps +=1
    }
  }
}
return arr;
}

function insertionSort(arr){
  for(let i = 1; i < arr.length; i++){
    let currentNum = arr[i]
    let j = i - 1
    while(currentNum < arr[j]){
      const checkValue = arr[j];
      arr[j] = currentNum;
      arr[j + 1] = checkValue;
      j--;
    }
  }
  return arr
}



function selectionSort(arr) {

}

function mergeSort(arr) {
  if (arr.length <= 1){
    return arr
  }

  const centerPoint = Math.floor(arr.length / 2) // 7/2 = 3.5
  const left = arr.slice(0,centerPoint);
  const right = arr.slice(centerPoint);

  return merge(mergeSort(left), mergeSort(right))

}

function merge(left, right) {
    const results = [];

    while(left.length && right.length){
      if(left[0] < right[0]){
        results.push(left.shift())
      } else {
        results.push(right.shift())
      }
    }

    return [...results, ...left, ...right]
}


// [3, 7, 9, 2, 14, 5, 13, 22]

[3,7,9,2,5,13],14,[22]
[3,7,9,2,5,13]
 2,3,7,9,5,13
 [3,7,9]
// 4[]            //4[]
// 2[] 2[]        // 2[] 2[]
// 1[] 1[] 1 [] 1[]  // 1[] 1[] 1[] 1[]


function quickSort(arr){
 if(arr.length < 2){
   return arr
 }
 const midpointIndex = Math.floor(arr.length/2);
 const pivot = arr[midpointIndex]
 const myLeftArr = [];
 const myRightArr = [];

 for(let i = 0; i < arr.length; i++){
  if(i !== midpointIndex){
    arr[i] < pivot ?
      myLeftArr.push(arr[i]):
      myRightArr.push(arr[i]);
  }
 }
 return [...quickSort(myLeftArr), pivot, ...quickSort(myRightArr)]
}

module.exports = { bubbleSort, selectionSort, mergeSort, merge, insertionSort, quickSort };

Solution#

JScompleted_exercises/sorting/index.js

function bubbleSort(arr) {  // Implement bubblesort  for (let i = 0; i < arr.length; i++) {    for (let j = 0; j < (arr.length - i - 1); j++) {      if (arr[j] > arr[j+1]) {        const lesser = arr[j+1];        arr[j+1] = arr[j];        arr[j] = lesser;      }    }  }   // return the sorted array  return arr;} function insertionSort(arr){  for(let i = 1; i < arr.length; i++){    let currentNum = arr[i]    let j = i - 1    while(currentNum < arr[j]){      const checkValue = arr[j];      arr[j] = currentNum;      arr[j + 1] = checkValue;      j--;    }  }  return arr}  function selectionSort(arr) {  for (let i = 0; i < arr.length; i++) {    let indexOfMin = i;     for (let j = i+1; j <arr.length; j++) {      if (arr[j] < arr[indexOfMin]) {        indexOfMin = j;      }    }     if (indexOfMin !== i) {      let lesser = arr[indexOfMin];      arr[indexOfMin] = arr[i];      arr[i] = lesser;    }  }   return arr;} function mergeSort(arr) {  if (arr.length === 1) {    return arr;  }   const center = Math.floor(arr.length / 2);  const left = arr.slice(0, center);  const right = arr.slice(center);   return merge(mergeSort(left), mergeSort(right));} function merge(left, right) {  const results = [];   while (left.length && right.length) {    if (left[0] < right[0]) {      results.push(left.shift());    } else {      results.push(right.shift());    }  }   return [...results, ...left, ...right];} function quickSort (arr){    if(arr.length < 2){        return arr     }    const pivotIndex = Math.floor(arr.length/2);    const pivot = arr[pivotIndex]     const myLeft = []    const myRight =[]     for(let i = 0; i< arr.length; i++){        if(i !== pivotIndex){            arr[i] < pivot ? myLeft.push(arr[i]): myRight.push(arr[i])        }    }    return [...quickSort(myLeft),pivot,...quickSort(myRight)]} module.exports = { bubbleSort, selectionSort, mergeSort, merge, insertionSort, quickSort};function bubbleSort(arr) {
  // Implement bubblesort
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < (arr.length - i - 1); j++) {
      if (arr[j] > arr[j+1]) {
        const lesser = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = lesser;
      }
    }
  }

  // return the sorted array
  return arr;
}

function insertionSort(arr){
  for(let i = 1; i < arr.length; i++){
    let currentNum = arr[i]
    let j = i - 1
    while(currentNum < arr[j]){
      const checkValue = arr[j];
      arr[j] = currentNum;
      arr[j + 1] = checkValue;
      j--;
    }
  }
  return arr
}


function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let indexOfMin = i;

    for (let j = i+1; j <arr.length; j++) {
      if (arr[j] < arr[indexOfMin]) {
        indexOfMin = j;
      }
    }

    if (indexOfMin !== i) {
      let lesser = arr[indexOfMin];
      arr[indexOfMin] = arr[i];
      arr[i] = lesser;
    }
  }

  return arr;
}

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }

  const center = Math.floor(arr.length / 2);
  const left = arr.slice(0, center);
  const right = arr.slice(center);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const results = [];

  while (left.length && right.length) {
    if (left[0] < right[0]) {
      results.push(left.shift());
    } else {
      results.push(right.shift());
    }
  }

  return [...results, ...left, ...right];
}

function quickSort (arr){
    if(arr.length < 2){
        return arr 
    }
    const pivotIndex = Math.floor(arr.length/2);
    const pivot = arr[pivotIndex]

    const myLeft = []
    const myRight =[]

    for(let i = 0; i< arr.length; i++){
        if(i !== pivotIndex){
            arr[i] < pivot ? myLeft.push(arr[i]): myRight.push(arr[i])
        }
    }
    return [...quickSort(myLeft),pivot,...quickSort(myRight)]
}

module.exports = { bubbleSort, selectionSort, mergeSort, merge, insertionSort, quickSort};
const S = require('./index');const bubbleSort = S.bubbleSort;const selectionSort = S.selectionSort;const mergeSort = S.mergeSort;const insertionSort = S.insertionSort;const quickSort = S.quickSort;const merge = S.merge; function getArray() {  return [100, -40, 500, -124, 0, 21, 7];} function getSortedArray() {  return [-124, -40, 0, 7, 21, 100, 500];} // describe('Bubble sort', () => {//   test('sorts an array', () => {//     expect(bubbleSort(getArray())).toEqual(getSortedArray());//   });// }); // describe('insertion Sort', ()=> {//   test('sorts an array', ()=> {//     expect(insertionSort(getArray())).toEqual(getSortedArray());//   });// }); // describe('Selection sort', () => {//   test('sorts an array', () => {//     expect(selectionSort(getArray())).toEqual(getSortedArray());//   });// }); describe('Merge sort', () => {  test('merge function can join together two sorted arrays', () => {    const left = [1, 10];    const right = [2, 8, 12];     expect(merge(left, right)).toEqual([1,2,8,10,12]);  });   test('sorts an array', () => {    expect(mergeSort(getArray())).toEqual(getSortedArray());  });   describe('Quick sort', () => {    test('sorts an array', () => {      expect(quickSort(getArray())).toEqual(getSortedArray());    });  });}); const S = require('./index');
const bubbleSort = S.bubbleSort;
const selectionSort = S.selectionSort;
const mergeSort = S.mergeSort;
const insertionSort = S.insertionSort;
const quickSort = S.quickSort;
const merge = S.merge;

function getArray() {
  return [100, -40, 500, -124, 0, 21, 7];
}

function getSortedArray() {
  return [-124, -40, 0, 7, 21, 100, 500];
}

// describe('Bubble sort', () => {
//   test('sorts an array', () => {
//     expect(bubbleSort(getArray())).toEqual(getSortedArray());
//   });
// });

// describe('insertion Sort', ()=> {
//   test('sorts an array', ()=> {
//     expect(insertionSort(getArray())).toEqual(getSortedArray());
//   });
// });

// describe('Selection sort', () => {
//   test('sorts an array', () => {
//     expect(selectionSort(getArray())).toEqual(getSortedArray());
//   });
// });

describe('Merge sort', () => {
  test('merge function can join together two sorted arrays', () => {
    const left = [1, 10];
    const right = [2, 8, 12];

    expect(merge(left, right)).toEqual([1,2,8,10,12]);
  });

  test('sorts an array', () => {
    expect(mergeSort(getArray())).toEqual(getSortedArray());
  });

  describe('Quick sort', () => {
    test('sorts an array', () => {
      expect(quickSort(getArray())).toEqual(getSortedArray());
    });
  });
});

Verbatim from the repo at 30cf7634. Alternate tabs are the commented-out solutions with the leading // removed and nothing else changed. Run the tests locally with npx jest sorting inside the fork.

Directions

Try it first#

Solution#hide again

Solution#