Sorting Algorithms

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Sorting Algorithms Animations

https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations

 

 

 

 

 

 

 

 

Insertion Sort

const numbers = [33, 12, 4, 65, 52, 41, 7, 12, 27];

function insertionSort(array) {
  const length = array.length;
  for (let i = 0; i < length; i++) {
    if (array[i] < array[0]) {
      // move number to the first position
    } else {
      // find where number should go
      for (let j = 1; j < i; j++) {
        if (array[i] > array[j - 1] && array[i] < array[j]) {
          //move number to the right spot
          array.splice(j, 0, array.splice(i, 1)[0]);
        }
      }
    }
  }
}

 

 

 

 

 

 

Merge Sort

const numbers = [33, 12, 4, 65, 52, 41, 7, 12, 27];

function mergeSort (array) {
  if (array.length === 1) {
    return array
  }
  // Split Array in into right and left
  const length = array.length;
  const middle = Math.floor(length / 2)
  const left = array.slice(0, middle)
  const right = array.slice(middle)
  // console.log('left:', left);
  // console.log('right:', right);

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

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while(leftIndex < left.length && rightIndex < right.length){
    if(left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      rightIndexx++
    }
  }
  // console.log(left, right)
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

 

 

 

 

 

 

Quick Sort

 

Quick Sort uses a pivoting technique (picking a random number) to break the main list into smaller lists, and the smaller lists use the pivoting technique until they are sorted. 

반응형

 

 

 

 

 

 

 

Quick Sort  vs Heap Sort

https://stackoverflow.com/questions/2467751/quicksort-vs-heapsort

Quicksort vs heapsort

 

 

 

 

 

 

 

 

 

 

 

 

 

 

*출처: Master the Coding Interview: Data Structures + Algorithms by Andrei Neagoie