[ Algo Theory ] 버블 / 삽입 / 선택 정렬

머릿말

 

알고리즘 공부를 하면서, 어딘가 부족하다는 느낌을 받는 지점이 많은데, 이 때 주로 느끼는 감정은 " 뭘 모르는지 모르겠다" 이다.

실제로 알고리즘을 수업과 여러 자료를 통해 배웠지만, 당시에는 문제를 많이 접하면서 체득을 하는 단계가 아니라 오로지 "이해"하는 것에만 초점을 두고 암기를 하였기에 각 알고리즘이 가진 장/단점을 온전히 느꼈다는 감정은 들지 않았다.

 

고로, 알고리즘 기본에 해당되는 [ 재귀, 정렬, 탐색, Hash, Graph, 분할정복, DP, 탐욕, 백트래킹 ] 순서로 관련된 이론 및 코드를 정리하며 내가 부족한 부분을 찾고 채워 나가는 시간을 가져 보려고 한다.

 

 

버블 정렬

 

버블 정렬은 명명된 이름과 같이 "버블"  즉, 비눗방울이 가지는 특징을 바탕으로 알고리즘을 설계하였다.

 

알고리즘의 로직에 따라 [ 오름차순 || 내림차순 ] 으로 정렬을 하되,

 

1) 오름차순의 경우, 자신의 뒤의 값들과 비교하여 자신보다 크다면 자리를 바꿔준다.

2) 내림차순의 경우, 자신의 뒤의 값들과 비교하여 자신보다 작다면 자리를 바꿔준다.

 

이를 통해 원하는 값을 배열의 끝, 즉 떠올려 보낸다는 개념을 바탕으로 만들어진 알고리즘이다.

 

시간복잡도

 

최선 : O(n)

자신보다 크거나 작은 값이 없다면, 길이만큼만 순회를 하기 때문에 O(n) 이다.

 

최악 : O(n^2)

 

자신보다 크거나 작은 값이 있다면, 자신의 뒤에 있는 배열의 다시 순회 하기 때문에 O(n^2) 이다.

 

코드

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let swap;
    for (let j = 0; j < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = swap;
      }
    }
    console.log(`${i + 1} 번째 : ${arr}`);
  }
  return arr;
}

let arr = [5, 4, 3, 2, 1];

console.log(bubbleSort(arr));

 

삽입 정렬

 

삽입 정렬은 말 그대로 "삽입"을 하는 과정에서 비교를 하는 정렬 알고리즘을 의미한다.

 

시간복잡도

 

최선 : O(n)

자신보다 크거나 작은 값이 없다면, 길이만큼만 순회를 하기 때문에 O(n) 이다.

 

최악 : O(n^2)

자신보다 크거나 작은 값이 있다면, 자신의 앞에 있는 배열의 다시 순회 하기 때문에 O(n^2) 이다.

 

코드

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let current = array[i];
    let prev = i - 1;
    let tmp = 0;
    while (prev >= 0 && array[prev] > current) {
      array[prev + 1] = array[prev];
      array[prev] = current;
      current = array[prev];
      prev--;
    }
    console.log(`${i} : ${arr}`);
  }
  return array;
}

let arr = [5, 4, 3, 2, 1];
console.log(insertionSort(arr));

 

선택정렬

선택정렬은 배열의 최소 값을 찾아 맨 앞으로 보내주는 알고리즘이다.

 

순서는 다음과 같이 진행된다.

 

1) 배열의 가장 작은 값을 찾는다.

2) 그 값을 맨 앞의 배열과 순서를 바꾼다.

3) 맨 앞을 제외한 가장 작은 값을 찾는다.

4) 2번째 값과 자리를 바꾼다 .. ( 반복 )

 

시간복잡도

 

최선 : O(n^2)

 

최악 : O(n^2)

 

어떤 형태든 모든 배열을 돌면서 최소 값을 찾기 때문에 O(n^2) 으로 고정이다.

 

코드

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      let swap = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = swap;
    }
    console.log(`${i} : ${arr}`);
  }
  return arr;
}

let arr = [5, 4, 3, 2, 1];
console.log(selectionSort(arr));