[알고리즘]선택 정렬과 삽입 정렬

jaemin·2020년 10월 10일

알고리즘

목록 보기

5/7

선택 정렬

문제 설명

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

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

function selectionSort(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]

풀이 과정 설계

선택 정렬이 어떤 방식으로 검색하는지 이해해보자.
array[0]부터 시작해서 array[n]까지 어떤 일을 반복한다.
array[0]일때의 경우를 자세히 살펴보면, array[0]과 array[1]을 비교하고 array[0]이 더 크다면 값을 서로 교환한다. 그다음 다시 array[0]과 array[2]를 비교한다. 이 같은 행위를 array[0]과 array[n]까지 반복한다.

따라서 두 개의 for문이 필요함을 알 수 있다.
array[0]부터 array[n]까지 돌아줄 for문 1개, array[0]일때 array[1]부터 array[n]까지 비교해줄 for문 1개가 필요하다.

이 생각을 바탕으로 코드를 짜보자!

풀이 과정

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

가장 바깥쪽 for문에서 i의 조건식을 array.length - 1로 해주었는데 array.length로 해줘도 상관은 없다. 그런데 array.length를 끝까지 돌지 않아도 이미 배열의 모든 수가 서로 한 번씩 비교를 마친 상황이므로 마지막 array[n]까지 가지 않아도 된다. 선택 정렬이 성능이 좋지 않다고 하니 조금이나마 일을 줄이려고 빼줬다.

array[0]과 array[0]을 비교할 필요는 없으니 j는 당연히 i + 1임을 알 수 있다. 나머지는 그동안 써왔던 값의 교환식을 사용했다.

그런데, 이 코드는 내가 버블 정렬에서 작성한 코드와 같았다. 버블 정렬과 선택 정렬은 동일하게 작동하는 것일까?

삽입 정렬

문제 설명

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

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

function insertionSort(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]

풀이 과정 설계

삽입 정렬의 시작은 array[0]이 아니라 array[1]부터 시작한다.
array[3]에서의 삽입 정렬을 살펴보자.
먼저, array[3]과 array[2]를 비교한다. 만약 array[2]가 더 큰 수라면 둘의 숫자를 교환한다.
그 후에, array[2]와 array[1]을 비교한다. 만약 array[1]이 더 큰 수라면 둘의 숫자를 교환한다.
이런 방식으로 array[0]과 array[1]의 크기를 비교할 때까지 반복해야 한다.

array[1]부터 배열의 인덱스 끝번호까지 도는 for문이 하나 필요하고 array 각 인덱스마다 이전 요소의 숫자값과 비교해야 하는 for문이 하나 더 필요하다.
첫 번째 for문은 array[1]부터 array[끝 번호]까지 돌아줄 것이고 두 번째 for문은 array[n]부터 array[0]까지 숫자를 비교해 조건에 맞다면 숫자값을 교환해 주는 역할을 해야 한다.

이 생각을 기반으로 코드를 작성해보자.

풀이 과정

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