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

jaemin·2020년 10월 10일
0

알고리즘

목록 보기
5/7
post-thumbnail

선택 정렬

문제 설명

  • 선택 정렬(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;
}

시작점은 array[1]이므로 제일 바깥쪽 for문 i의 시작점도 1로 설정했다.
안쪽 for문 j의 시작점은 i와 같다. i를 기준으로 1씩 줄어들면서 비교할 예정이고 array[0]까지 비교해야 하기 때문에 조건을 j >= 0이라고 했다.

그 다음 값의 교환은 다른 정렬과 마찬가지 방법으로 교환해주었다.
수업 시간에 변수파트에서 배웠던 a라는 변수를 만들어서 값을 담고 할당해주는 방법도 있지만 나는 이 방법이 한 눈에 들어와 가독성이 좋다고 생각한다.

profile
프론트엔드 개발자가 되기 위해 공부 중입니다.

0개의 댓글