개념 정리 - 선택, 버블, 삽입 정렬

정렬 알고리즘의 장점과 선택, 버블, 삽입 정렬의 시간 복잡도에 대한 설명은 아래 참고자료에 자세히 나와있다.

물론 구현 코드도 나와있지만 내가 이해한 생각의 흐름대로 코드 구현 과정을 정리하고 싶었다.

https://im-developer.tistory.com/133

[JS/Sorting] 버블 정렬, 삽입 정렬, 선택 정렬 자바스크립트로 구현하기 (Bubble Sort, Insertion Sort, Select

 

 

가장 베이직한 정렬 문제로 오름차순 정렬을 sort 메서드없이 구현하는 문제가 있다.

해당 문제를 선택, 버블, 삽입 정렬 알고리즘으로 풀이해보았다.

나는 [ 13, 5, 11, 7, 23, 15 ] 를 오름차순으로 정렬할 것이다.

 

선택 정렬

 

선택 정렬은 위 그림과 같이 해당 위치에 올 수 있는 요소를 전체 요소(또는 부분 요소)에서 선택하는 것이다.

이를 코드로 표현하면 다음과 같다.

function solution(arr) {
  for (let i = 0; i < arr.length; i++) {
    let idx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[idx]) idx = j;
    }
    [arr[i], arr[idx]] = [arr[idx], arr[i]];
  }
  return arr.join(' ');
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));

 

처음 알았는데 두 요소를 바꿀 때 파이썬처럼 표현할 수 있단다. 임시 변수를 저장해서 바꾸는 것보다 깔끔한 것 같다.

 

버블 정렬

 

버블 정렬은 데이터를 두개씩 묶어서 비교하면서 n번째 정렬 회차가 끝나면 뒤에서 n번째 자리의 데이터가 확정된다.

function solution(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let swap;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = swap;
      }
    }
    if (!swap) break;
  }
  return arr.join(' ');
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));

 

swap 변수를 이용하면 정렬이 되어있을 때 시간복잡도가 O(N)이다.

보통 버블 정렬은 최악의 경우 O(N^2)인데, 정렬이 되어있다면 선택 정렬보다 효율성이 좋다.

 

삽입 정렬

조건에 맞게 요소를 어떤 위치에 삽입할 지를 결정하는 것이다.

 

13 5 11 7 23 15

첫번째 요소 13을 제외하고 두번째 요소인 5부터 시작할 때, 5가 삽입될 수 있는 위치는 13 앞이거나 13 뒤인 본래 자기 자리이다.

13보다 5가 작기 때문에 5의 자리는 13 앞 자리이다. 따라서 원래 5가 있던 자리에 13을 넣어준다. 그리고 5는 13의 앞자리로 간다.

 

5 13 11 7 23 15

그 다음 11을 정렬할 것이다. 13보다 11이 작기 때문에 11은 13의 앞으로 삽입된다. 그리고 5보다는 크기 때문에 5의 뒷자리에 삽입되어야한다.

 

이것을 코드로 일반화 시키면 다음과 같다.

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

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));

 

비교하는 대상의 앞자리에 삽입할지, 뒷자리에 삽입할지를 결정하는 것이라고 생각하면 된다.

5를 13의 앞에 삽입할지, 뒤에 삽입할지를 결정하는것이다.

그렇다면 비교대상은 i보다 한칸 아래 인덱스부터 시작하는 것이 옳다. 

그리고 비교대상보다 내가 정렬하고 싶은 요소가 큰 경우에는 비교대상의 뒷자리에 와야하기 때문에 j+1번째 인덱스에 내가 정렬하고 싶은 요소를 넣어주는 것이다.

 

예제

배열이 주어졌을 때 양수는 왼쪽으로, 음수는 오른쪽으로 정렬하는 문제이다. 단, 순서가 변경되어서는 안된다.

예시가 다음과 같을 때

1 2 3 -3 -2 5 6 -6

정렬하게 되면 다음과 같다.

-3 -2 -6 1 2 3 5 6

 

버블 정렬로 풀면 데이터를 두개씩 묶어 비교하면서 오른쪽에 있는 값이 음수이고 왼쪽에 있는 값이 양수이면 두 값의 순서를 바꿔주면 된다.

그렇다면 차례로 버블 정렬이 되었을 때 원하는 값을 얻을 수 있다.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > 0 && arr[j + 1] < 0) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr.join(' ');
}

 

삽입 정렬을 사용하면 내가 삽입하고자 하는 요소가 음수이고 비교 대상이 양수이면 비교 대상 앞에 삽입시키고, 그렇지 않은 경우에는 비교 대상의 뒤에다가 삽입시킨다.

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i];
    let j;
    for (j = i - 1; j >= 0; j--) {
      if (arr[j] > 0 && temp < 0) {
        arr[j + 1] = arr[j];
      } else break;
    }
    arr[j + 1] = temp;
  }
  return arr.join(' ');
}

 

반드시 오름차순 문제만 나오는 것이 아니다.

조건에 맞게 요소를 묶어서 비교하며 정렬할 것인지, 아니면 적절한 위치에 삽입하는 방법이 좋을지를 스스로 판단하는 능력이 중요하다고 느꼈다.

 

참고로 버블, 삽입, sort메서드는 stable하다. 즉, 같은 값이 존재하면 순서를 바꾸지 않고 정렬한다.