알고리즘 03 정렬 기본 | 선택 정렬, 거품 정렬, 삽입 정렬 | JS

protect-me·2021년 8월 29일

📝 CS Study

목록 보기

20/37

정렬 알고리즘 종류

simple, slow	fast	O(N)
Selection sort, Bubble sort, Insertion sort	Quicksort, Merge sort, Heap sort	radix sort

선택 정렬 | Selection Sort

최대 값을 찾아서 마지막 자리와 바꾸거나
혹은 최소 값을 찾아 맨 앞자리와 바꾸는 방식
시간복잡도: O(n^2)

// 오름차순, 최소값을 맨 앞자리와 바꾸는 방식
function selectionSort(arr) {
  const len = arr.length
  let minIndex = 0
  let temp = 0
  let i = 0
  let j = 0
  for (i = 0; i < len; i++) {
    minIndex = i
    for (j = i + 1; j < len; j++) {
      if (arr[i] > arr[j]) {
        minIndex = j
      }
    }
    temp = arr[minIndex]
    arr[minIndex] = arr[i]
    arr[i] = temp
  }
  return arr
}

const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
console.log(selectionSort(arr))

거품 정렬 | Bubble Sort

이미지 출처

두 인접한 원소를 검사하여 정렬하는 방법
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름
시간복잡도: O(n^2)

// 오름차순
function bubbleSort(arr) {
  const len = arr.length
  let temp = 0
  let i = 0
  let j = 0
  for (i = 0; i < len; i++) {
    for (j = i + 1; j < len; j++) {
      if (arr[i] > arr[j]) {
        temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}


const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
console.log(bubbleSort(arr))

삽입 정렬 | Insertion Sort

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬
시간복잡도: O(n^2)

삽입 정렬(이중 for문)

function insertionSort(arr) {
  const len = arr.length
  let temp = 0
  for (i = 1; i < len; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (arr[i] < arr[j]) {
        temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
        i--
      }
    }
  }
  return arr
}

const arr = [1, 2, 5, 6, 4, 7, 9, 8, 3]
console.log(insertionSort(arr))

삽입 정렬(for문 + while문)

참고

function insertionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    index = i;
    while (arr[index] !== undefined && arr[index - 1] > arr[index]) {
      let temp = arr[index - 1];
      arr[index - 1] = arr[index];
      arr[index] = temp;
      index--;
    }
  }
}