정렬 알고리즘이 왜 필요할까 ?

정렬 알고리즘이 필요한 이유를 한 마디로 이야기 하자면 데이터를 효율적으로 관리하기 위함이라고 할 수 있다.

만약 데이터를 정렬 되지 않은 형태로 관리한다고 가정하고 , 데이터의 개수가 N 이라고 가정 해보자

정렬 되지 않은 데이터들에서 특정 데이터를 조회하기 위해서 모든 데이터를 선형적으로 순회 해야 하기 때문이 데이터의 개수인 N 만큼 걸린다.

컴퓨터가 1초에 만개의 데이터를 처리 할 수 있다고 가정했을 때 10만개의 데이터를 조회하는데 걸리는 시간은 10초가 걸릴 것이다.

하지만 정렬 된 데이터들에서 특정 데이터를 조회하기 위한 연산 횟수는 고작 20번, 시간으로 치면 약 0.001 초 밖에 걸리지 않는다.

정렬 되어 있는 데이터들에 적용 가능한 강력한 알고리즘 들이 존재하기 때문이다.

에를 들어 정렬 된 형태에서 사용 가능한 이진 탐색 알고리즘 부터, 정렬 된 형태를 유지하며 데이터를 삽입 , 삭제 , 수정이 가능한 힙 자료구조 등이 존재한다.

이로 인해 데이터를 효과적으로 조작하기 위해선 데이터를 올바르게 정렬 시키는 것이 중요하다.

이에 정렬 알고리즘들을 하나하나 순차적으로 알아보자

정렬 안정성

정렬 안정성이란 동일한 키를 가진 요소들의 성질들을 정렬 이후에도 보존하는가를 의미한다.

예를 들어 다음과 같은 자료구조가 있다고 생각해보자

[[1, a], [2, b], [3, b], [4, c] ...]

이 때 [2, b], [3, b]는 두 번째 키 값이 동일하다.

해당 배열을 첫 번째 키 값으로 정렬했을 때 정렬 전의 a, b, c ...에 의한 순서가 변경되지 않는 정렬 알고리즘을 안정 정렬 알고리즘이라고 한다.

그렇지 않은 알고리즘은 불안정 정렬 알고리즘이라고 한다.

정렬 안정성이 중요한 이유

1. 다중 키 정렬:

   • 데이터베이스나 스프레드시트와 같은 응용 프로그램에서는 여러 키를 기준으로 데이터를 정렬해야 하는 경우가 많다. 예를 들어, 먼저 성(last name)으로 정렬한 후, 같은 성을 가진 사람들을 이름(first name)으로 정렬할 수 있다. 이때 안정적인 정렬 알고리즘을 사용하면 첫 번째 키로 정렬된 순서가 두 번째 키로 정렬할 때 유지된다.

2. 데이터의 일관성 유지:

   • 안정적인 정렬 알고리즘은 동일한 키를 가진 요소들의 상대적인 순서를 보존한다. 이는 데이터의 일관성을 유지하는 데 중요하다. 예를 들어, 동일한 우선순위를 가진 작업들이 있을 때, 안정적인 정렬 알고리즘을 사용하면 작업들이 원래의 순서대로 처리된다.

3. 예측 가능성:

   • 안정적인 정렬 알고리즘은 동일한 입력에 대해 항상 동일한 출력을 제공한다. 이는 디버깅과 테스트를 용이하게 하며, 예측 가능한 결과를 얻는 데 도움이 된다.

4. 특정 응용 프로그램 요구 사항:

   • 일부 응용 프로그램에서는 데이터의 특정 속성을 유지하는 것이 중요하다. 예를 들어, 그래프 알고리즘에서 간선을 정렬할 때 안정적인 정렬 알고리즘을 사용하면, 동일한 가중치를 가진 간선들이 원래의 순서를 유지한다.

버블 정렬

버블 정렬의 동작 예시

버블 정렬은 가장 느리지만 , 단순하고 직관적인 알고리즘이다.

슈도 코드로 나타내면 버블 정렬은 다음과 같이 진행 된다.

1. N개의 데이터를 0부터 마지막 인덱스까지 순회한다.
  2. 현재 인덱스의 값과 다음 인덱스의 값을 비교한다.
    3. 만약 현재 인덱스의 값보다 다음 인덱스의 값이 작다면 두 값을 교환한다.
    4. 그렇지 않다면 아무런 행위도 하지 않는다.

버블 정렬이란 이름이 붙은 이유는 매 반복마다 정렬 기준에 따라 가장 큰 값이나, 작은 값이 배열의 마지막 방향으로 뿅 하고 정렬 되기 때문이다.

만약 [5,4,3,2,1] 이란 배열이 있다면 각 순회 순서에 맞게

• [4,3,2,1,5]
• [3,2,1,4,5] ...
• [1,2,3,4,5]

와 같은 순으로 정렬 된다.

코드를 통해 알아보자

const bubbleSort = (arr) => {
  for (let start = 0; start < arr.length - 1; start++) {
    for (let index = 0; index < arr.length - start; index++) {
      if (arr[index + 1] < arr[index]) {
        [arr[index], arr[index + 1]] = [arr[index + 1], arr[index]];
      }
    }
  }
};

버블 정렬의 코드를 살펴보면 첫 번째 외부 반복문에선 배열의 마지막 원소 이전까지 순회하는 모습을 볼 수 있다.

마지막 원소 이전까지 순회하는 이유는 , 버블 정렬을 시행하는 배열의 마지막 원소는 정렬 되어 있다고 가정 하기 때문이다.

정렬 알고리즘에선 위와 같은 가정법들이 자주 사용 된다.

내부 반복문에선 0 부터 arr.length - start 까지 순회하는 것을 볼 수 있는데 그 이유는 배열을 K 번 순회 할 때 마다 배열의 마지막으로부터 K 번째 수까지는 모두 정렬 되기 때문이다.

반복문을 돌 때 마다 로그를 찍어보면 결과가 다음과 같다.

outer : 0 , inner : 0
[4,5,3,2,1]
outer : 0 , inner : 1
[4,3,5,2,1]
outer : 0 , inner : 2
[4,3,2,5,1]
outer : 0 , inner : 3
[4,3,2,1,5]
outer : 0 , inner : 4
[4,3,2,1,5]
------------------------
outer : 1 , inner : 0
[3,4,2,1,5]
outer : 1 , inner : 1
[3,2,4,1,5]
outer : 1 , inner : 2
[3,2,1,4,5]
outer : 1 , inner : 3
[3,2,1,4,5]
------------------------
outer : 2 , inner : 0
[2,3,1,4,5]
outer : 2 , inner : 1
[2,1,3,4,5]
outer : 2 , inner : 2
[2,1,3,4,5]
------------------------
outer : 3 , inner : 0
[1,2,3,4,5]
outer : 3 , inner : 1
[1,2,3,4,5]
------------------------

버블 정렬의 시간 복잡도

버블 정렬의 시간 복잡도는 다음과 같다.

버블 정렬은 외부 루프를 N-1번 도는 동안, N-1, N-2, N-3, ..., 1번 인접한 원소들을 비교한다.

O(n) = (n^2) 이다.

이는 데이터의 개수가 늘어날 때 마다 연산 횟수가 제곱하여 늘어나는 경우로 가장 최악의 시간 복잡도로 버블 정렬이 실제로 사용 되는 경우는 거의 없다.

데이터가 100개에서 200개로 늘어나기만 해도 필요한 연산 횟수는 10000 번에서 40000번으로 4배가 늘어난다.

칵테일 정렬 혹은 쉐이커 정렬

칵테일 정렬의 예시

칵테일 정렬은 버블 정렬의 발전된 버전으로 버블 정렬이 원소 순회를 start -> end 순으로 선형적으로 순회 했다면 칵테일 정렬은 원소를 start -> end -> start .. 와 같이 양방향적으로 순회하며 정렬한다.

start -> end 방향 일 때는 최대값을 찾아 원소 마지막 부분에 정렬하고 end -> start 방향 일 땐 최소값을 찾아 원소 맨 처음 부분에 정렬 한다.

칵테일 정렬은 특정 상항 일 때 버블 정렬보다 효과적이다.

예를 들어 배열이 거의 정렬 되어 있는 상황 일 때 칵테일 정렬은 더욱 빠르게 순회가 가능하다.

예를 들어 1,2,3,4,6,5 의 경우 오름차순 정렬을 하게 되면 버블 정렬은 1~6까지 모두 순회해야지만 정렬이 완료 되지만

칵테일 정렬의 경우엔 1 (start ->end) , 5 (end -> start , 6과 5 스왑) 두 번만 순회 해도 정렬이 완료 된다.

혹은 가장 큰 수나 가장 작은 수가 배열의 끝단에 존재 할 때에도 그렇다.

6,2,3,4,5,1 과 같은 경우도 칵테일 정렬은 2번의 순회만으로 정렬을 마칠 수 있다.

하지만 여전히 칵테일 정렬도 버블정렬이기에 최악의 경우엔 O(N^2) 이라는 최악의 시간 복잡도를 갖는다.

코드를 통해 알아보자

const cocktailSort = (arr) => {
  for (let start = 0, end = arr.length - 1; start < end; ) {
    // 정방향 순회 시작
    for (let index = start; index < end; index++) {
      if (arr[index] > arr[index + 1]) {
        const temp = arr[index];
        arr[index] = arr[index + 1];
        arr[index + 1] = temp;
      }
    }
    // 가장 마지막 배열엔 가장 큰 값이 위치하게 됨
    end--;
 
    // 역방향 순회 시작
    for (let index = end; index > start; index--) {
      if (arr[index] < arr[index - 1]) {
        const temp = arr[index];
        arr[index] = arr[index - 1];
        arr[index - 1] = temp;
      }
    }
    // 가장 첫 번째 배열엔 가장 작은 값이 위치 하게 됨
    start++;
  }
};
 
cocktailSort(arr);

칵테일 정렬은 위와 같이 배열을 한 번 순회 할 때 최대값과 최소값을 찾아 start , end 를 항상 정렬 된 순서로 만든다.

플래그를 넣어 버블정렬을 빠르게 끝내보자

여전히 버블정렬과 칵테일 정렬은 N 크기의 배열 모두를 순회하기 때문에 여전히 느리다는 문제가 존재한다.

이에 정렬이 완료 되었을 때 순회를 멈출 수 있게 하는 플래그를 만들어 정렬이 끝난 경우엔 빠르게 끝내보자

const bubbleSort = (arr) => {
  let isSorted = true;
 
  for (let start = 0, end = arr.length - 1; start < end && isSorted; ) {
    isSorted = false;
 
    for (let index = start; index < end; index++) {
      if (arr[index] > arr[index + 1]) {
        const temp = arr[index];
        arr[index] = arr[index + 1];
        arr[index + 1] = temp;
        isSorted = true;
      }
    }
  }
};
 
bubbleSort(arr);

위와 같이 플래그를 세워 만약 내부를 순회 할 때 arr[index] > arr[index+1] 이 한 번이라도 작동하지 않았다면 모든 배열이 정렬 된 것으로 삼아 반복문을 종료 할 수 있다.