자료구조와 알고리즘 (정렬) (2)

1.3 선택 정렬

• 선택 정렬(selection sort)은 배열의 최소값을 검색하여 배열의 왼쪽부터 순차적으로 정렬을 반복하는 정렬 알고리즘입니다.
• 배열이 미정렬 상태이므로 최솟값 검색에는 이진 검색이 아닌 선형 검색 알고리즘을 사용합니다.
• 선택 정렬은 버블 정렬보다 빠릅니다.
• 시간 복잡도: O(n^2)

선택 정렬

문제

선택 정렬을 통해 주어진 배열(array)을 정렬하는 함수를 구현하라. 단, 어떠한 빌트인 함수도 사용하지 않고 for 문을 사용하여 구현하여야 한다.

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [array[i], array[minIdx]] = [array[minIdx], array[i]];
  }
  return array;
}

console.log(selectionSort([3, 1, 0, -1, 4, 2])); // [-1, 0, 1, 2, 3, 4]
console.log(selectionSort([2, 4, 5, 1, 3])); // [1, 2, 3, 4, 5]
console.log(selectionSort([5, 2, 1, 3, 4, 6])); // [1, 2, 3, 4, 5, 6]

1.4 삽입 정렬

• 삽입 정렬(insertion sort)은 인덱스 1부터 왼쪽과 비교하면서 순차적으로 정렬을 반복하는 정렬 알고리즘입니다.
• 정렬이 진행됨에 따라 왼쪽에는 정렬이 종료된 값이 모이게 되고, 오른쪽에는 아직 정렬되지 않은 값이 남게 됩니다.
• 선택 정렬은 최솟값 검색이 필요하지만 삽입 정렬은 필요없습니다.
• 삽입 정렬은 평균 시나리오에서 선택 정렬과 유사하고(데이터 정렬 유형에 따라 차이가 있음) 버블 정렬보다 빠릅니다.
• 시간 복잡도: O(n^2)

삽입 정렬

문제

삽입 정렬을 통해 주어진 배열(array)을 정렬하는 함수를 구현하라. 단, 어떠한 빌트인 함수도 사용하지 않고 for 문을 사용하여 구현하여야 한다.

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let curIdx = i;
    for (let j = curIdx - 1; j >= 0; j--) {
      if (array[curIdx - 1] <= array[curIdx]) break;
      [array[curIdx - 1], array[curIdx]] = [array[curIdx], array[curIdx - 1]];
      --curIdx;
    }
  }
  return array;
}

console.log(insertionSort([3, 1, 0, -1, 4, 2])); // [-1, 0, 1, 2, 3, 4]
console.log(insertionSort([2, 4, 5, 1, 3])); // [1, 2, 3, 4, 5]
console.log(insertionSort([5, 2, 1, 3, 4, 6])); // [1, 2, 3, 4, 5, 6]