[알고리즘]정렬 알고리즘

bareum park·2021년 10월 26일

내가 Javascript 공부하면서 가장 먼저 스스로 구현하고자 했던 것은 정렬 함수를 구현하는 것이었다. 대부분의 언어가 그렇듯 Javascript에도 정렬을 위한 메서드가 있지만, 실제로 정렬을 어떤식으로 구현하는지 스스로 이해하고 구현 할 수 있다면 개발 언어 공부에 큰 도움이 될 것이라고 생각했기 때문이다. 실제로 며칠을 고민하고 시행착오를 겪은 끝에 스스로 만들어 냈던 정렬 함수로 이중 for문에 대한 이해도를 많이 높일 수 있었다. 그때 당시에는 내가 만든 정렬 함수가 어떤 알고리즘인지 몰랐는데, 이제와 보니 버블 정렬 알고리즘으로 정렬을 구현해냈던 것이었다.

정렬 알고리즘은 알고리즘을 공부함에 있어 가장 기본적인 알고리즘 중 하나다. 그래서 알고리즘을 공부 할 때 필수적으로 공부하게 된다. 위에서 언급했듯이 내장 메서드를 사용하면 간단하게 정렬 할 수 있지만, 가장 기본이 되는 알고리즘인만큼 메서드 없이도 스스로 구현 할 수 있어야 된다고 생각한다. 그래서 이번에는 가장 기본적인 정렬 알고리즘 3개에 대해 포스팅해보려고 한다.

정렬 알고리즘이란?

먼저, 정렬 알고리즘은 위키 백과에 의하면 다음과 같이 정의되어 있다.

정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는 데 흔히 유용하게 쓰인다. 이 알고리즘의 결과는 반드시 다음 두 조건을 만족해야 한다.

1. 출력은 비 내림차순(각각의 원소가 전 순서 원소에 비해 이전의 원소보다 작지 않은 순서)이다.

2. 출력은 입력을 재배열하여 만든 순열이다.

정렬은 프로그래밍 할 때 자주 사용되는 알고리즘이다. 때문에 다양한 알고리즘이 고안되었다. 그중에서도 버블, 선택, 삽입 정렬 알고리즘에 대해 알아보도록 하자.

버블 정렬 알고리즘

버블 정렬 알고리즘은 서로 인접한 데이터를 비교하여 정렬하는 알고리즘이다. 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 방식으로 진행한다. 언제나 인접한 두개의 데이터를 비교하여 큰 데이터를 뒤로 보내기 때문에, 반복이 돌 때 마다 가장 가장 큰 데이터가 마지막 데이터가 되게 된다.

버블 정렬 알고리즘은 시간 복잡도가 O(n^2)이기 때문에 성능은 좋지 않지만, 구현이 쉬워 많이 사용되는 정렬 알고리즘이다.

버블 정렬 알고리즘을 javascript로 구현하면 다음과 같다.

const bubbleSort = array => {
  let temp = 0;
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
};

console.log(bubbleSort([5,4,3,2,1]));

선택 정렬 알고리즘

선택 정렬은 제자리 정렬 알고리즘의 하나다. 선택 정렬 알고리즘의 진행방식은 다음과 같다.

배열을 훑어 가장 작은 데이터를 찾는다.
그 데이터를 가장 앞에 위치한 데이터와 교체한다.
맨 처음 위치를 뺀 나머지 데이터를 같은 방법으로 교체한다.

버블 정렬과 마찬가지로 시간 복잡도는 O(n^2)다. 성능이 좋지 않지만 작은 수를 정렬하는데는 효과적이다. 또한 선택 정렬은 버블 정렬보다 항상 우수하다.

선택 정렬 알고리즘을 javascript 코드로 구현하면 다음과 같다.

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

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

삽입 정렬 알고리즘

삽입 정렬 알고리즘은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는 식으로 진행되는데, 이는 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입하는데, 이 작업을 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬되는 이치와 같다.

삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

삽입 정렬은 k번째 반복 이후, 첫번째 k 요소가 정렬된 순서로 온다는 점에서 선택 정렬과 유사하다. 하지만 선택 정렬은 k+1 번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 삽입 정렬은 k+1 번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있다.

삽입 정렬 알고리즘을 javascript로 구현하면 다음과 같다.

const insertionSort = array => {
    let temp = 0;
    let j = 0;
    for (let i = 1; i < array.length; i++) {
        temp = array[i];
        for (j = i - 1; j >= 0 && temp < array[j]; j--) {
            array[j + 1] = array[j];
        }
        array[j + 1] = temp;
    }
    return array;
};
console.log(insertionSort([5,4,3,2,1]));