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

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

만약 데이터를 정렬 되지 않은 형태로 관리한다고 가정하고 , 데이터의 개수가 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배가 늘어난다.