Sorting Algorithms

Bubble Sort

실제로는 많이 쓰이지 않지만 기본적으로 알고 있어야 하는 방법이다.

근접한 요소끼리 비교해서 내가 원하는 순서대로 정렬하는 것을 반복하고

만약 요소들이 순서가 변경되지 않았다면 제대로 정렬이 된거니까 완료한다.

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

        }
    } while(swapped)
}

 

Big O : O(n^2)

 

Insertion Sort

정렬이 된 배열과 정렬이 되지 않은 배열이 있다는 전제 하에 요소를 넣어 정렬해준다.

하나의 기준에서 그 이전에 있는 요소들과 값의 크기를 비교하여 위치를 변경해준다.

function func(arr) {
  for (let i = 1; i < arr.length; i++) {
    let numberToInsert = arr[i]
    let j = i - 1;
    while(j >= 0 && arr[j] > numberToInsert) {
      arr[j+1] = arr[j]
      j = j - 1
    }
    arr[j+1] = numberToInsert
  }
}

 

Big O : O(n^2)

 

Quick Sort

pivot이라는 대표 숫자를 정해서 그보다 작은 수를 left, 큰 수를 right으로 나누고

left or right이 하나가 빌 때까지 계속 진행해준다.

그리고 나서 마지막 단계에서 left나 right와 pivot을 합치고 위로 올라오면서 pivot만 추가해준다.

function func(arr) {
  if (arr.length < 2) return arr
  
  let pivot = arr[arr.length - 1]
  
  let left = [];
  let right = [];

  for (let i = 0; i < arr.length -1 ; i++) {
    if (arr[i] < pivot) left.push(arr[i])
    else right.push(arr[i])
  }

  return [...func(left), pivot ,...func(right)]
}

Big O : O(n^2) - worst case, O(nlogn) - avg case

 

 

Merge Sort

길이가 1인 배열로 계속 나눈 후에 합치면서 비교해서 정렬을 진행한다.

function func(arr) {
  if (arr.length < 2) return arr
  const mid = Math.floor(arr.length / 2)
  const leftArr = arr.slice(0, mid)
  const rightArr = arr.slice(mid)
  return merge(func(leftArr), func(rightArr))
}

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

 

Big O : O(nlogn) --> 반으로 나누면서 배열을 나누고 합칠 때는 linear로 가기 때문에 둘을 합치면 nlogn이 된다.