YoungGyu Blog

sort 알고리즘

July 24, 2020

Bubble Sort(버블정렬)

서로 인접한 두 원소를 비교하고 자리를 교환하며 정렬하는 알고리즘

image

JavaScript

function bubbleSort(arr) {
  let temp = 0
  for (let i = 0; i < arr.length; i++) {
    for (let j = 1; j < arr.length; j++) {
      if (arr[j - 1] > arr[j]) {
        temp = arr[j - 1]
        arr[j - 1] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}
console.log(bubbleSort([3, 4, 1, 5, 6, 2]))

시간 복잡도 : O(n^2)

구현방법이 간단하지만 효율이 좋지 않습니다.

Selection Sort(선택정렬)

자리를 선택하고 정렬되지 않은 배열들중에 최소값을 찾아서 교환하는 방식

image

function SelectionSort(arr) {
  let indexMin = 0
  let temp = 0
  for (let i = 0; i < arr.length; i++) {
    indexMin = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[indexMin]) {
        indexMin = j
      }
    }
    temp = arr[indexMin]
    arr[indexMin] = arr[i]
    arr[i] = temp
  }

  return arr
}
console.log(SelectionSort([3, 4, 1, 5, 6, 2]))

시간 복잡도 : O(n^2)

Bubble Sorting 만큼 구현방법이 간단하지만 마찬가지로 효율이 좋지않습니다.

삽입 정렬 (Insertion Sort)

image

const insertionSort = arr => {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i]
    let prev = i - 1
    while (prev >= 0 && arr[prev] > temp) {
      arr[prev + 1] = arr[prev]
      prev--
    }
    arr[prev + 1] = temp
  }
  return arr
}
console.log(insertionSort([3, 1, 4, 5, 2, 1, 6]))
Lee YoungGyu