정렬 알고리즘은 개발자 면접을 보기 위해서 꼭 필요한 내용이다.
하나씩 정리해보고 숙지해보자.
정렬 알고리즘은 다음과 같이 간단하게 나눠볼 수 있다.

  • 단순하지만 비효율적인 방법
    • 선택 정렬, 삽입 정렬, 버블 정렬
  • 복잡하지만 조금 더 효율적인 방법
    • 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

Q. 정렬은 왜 사용할까?
탐색을 빠르게 하기 위해서 정렬을 한다.
하지만 정렬 방법은 많고 이 중에서 제일 빠른 걸 사용해야 한다.
같은 시간 복잡도를 갖더라도 요소에 따라 달라질 수 있으니 알아보자.

# 선택 정렬

기본이 되는 정렬 중 하나이다. 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장될 값의 크기가 작냐, 크냐에 따라서 최소 선택 정렬(오름차순으로 정렬)과 최대 선택 정렬(내림차순으로 정렬)이 있다.

기본로직은 아래와 같다.

  1. 정렬되지 않은 인덱스의 맨 앞에서부터 이를 포함한 그 이후 배열의 값 중 가장 작은 값을 찾는다.
  2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
  3. 다음 인덱스에서 위의 과정을 반복한다.

쉽게 설명하면 기준이 되는 수와 나머지 수를 비교해서 가장 작은 수를 앞으로 계속 보내는 정렬이다. 간단하지만 매우 비효율적이다.

최악의 경우, 최선의 경우, 평균적인 경우 모두 시간 복잡도 : O(N^2)을 갖는다.

장점

  • 데이터의 양이 적을 때 좋은 성능을 나타냄
  • 적은 값을 선택하기 위해서는 비교는 여러번 수행되지만 교환횟수가 적다.

단점

  • 100개 이상의 자료에 대해서는 속도가 급격히 떨어져 적절히 사용되기 힘들다.

# 버블 정렬

  • 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘을 갖는다.
    • 인접한 2개의 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
  • 선택 정렬과 기본 개념이 유사함.

기본 로직은 아래와 같다.

  1. 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를 … n-1번째 자료와 n번째 자료를 비교하여 교환하면서 자료를 정렬한다.
  2. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동한다.
  3. 이렇기 때문에 2회전에서는 맨 끝에 있는 자료가 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

쉽게 설명하면 현재 원소와 다음 원소를 비교해서 큰 원소를 뒤로 보내는 정렬이다.

최악의 경우, 최선의 경우, 평균적인 경우 모두 시간 복잡도 : O(N^2)을 갖는다.
이미 정렬된 데이터에 대해서 검사하는데는 O(N)으로 간단하게 할 수 있다.

장점

  • 구현이 쉽다.
  • 이미 정렬된 데이터를 정렬할 때 가장 빠르다.

단점

  • 다른 정렬에 비해 정렬 속도가 느리다.
  • 역순배열을 정렬할 때 가장 느리다.
  • 정말 비효율적이라 거의 쓰이지 않는다.

# 삽입 정렬

삽입 정렬의 기본 개념은 손안의 카드를 정렬하는 방법과 유사하다.

  • 새로운 카드를 기존의 정렬된 카드 사이에 올바른 자리를 찾아 삽입한다.
  • 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.
  • 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘.
  • 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

기본 로직은 아래와 같다.

  • 오름차순을 기준으로 정렬한다.
  1. 기준이 되는 인덱스는 두 번째 자료부터 시작한다. 이 기준이 되는 인덱스를 Key라고 하겠다. Key가 들어갈 자리를 찾는게 핵심이다.
  2. Key는 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료들을 뒤로 옮기고 지정한 자리에 Key 자료를 삽입하여 정렬한다.
  3. 즉, 두 번째 자료는 첫 번째 자료와 비교하고 세 번째 자료는 두 번째와 첫 번째 자료 … 이런 방식으로 비교해서 기준이 되는 자료가 들어갈 위치를 찾는다.
  4. 최종적으로 Key가 들어갈 위치를 찾았다면 자료들을 한칸씩 뒤로 이동시키고 그 자리에 삽입한다.

쉽게 말하면 기준이 되는 인덱스의 앞쪽(왼쪽)을 검사하여 기준이 되는 인덱스가 들어갈 자리를 찾아서 삽입하는 정렬이다.

최악의 경우 : O(N^2) - 자료가 역순으로 정렬되어 있을 경우/작은 값이 뒤에 몰려있을 경우
최선의 경우 : O(N) - 이동없이 1번의 비교만 이루어질 경우
평균적인 경우 : O(N^2)

장점

  • stable한 정렬 방법
  • 적은 수를 정렬할 경우 알고리즘 자체가 간단해서 다른 복잡한 정렬 방법보다 유리할 수 있다.
  • 대부분의 수가 이미 정렬되어 있는 경우에 매우 효율적이다.

단점

  • 비교적 많은 수들의 이동을 포함한다.
  • 비교할 수가 많고 크기가 클 경우에 적합하지 않다.

결론

위에서 살펴본 정렬 알고리즘들은 비교적 구현이 간단하다. 그리고 이해하기도 어렵지 않다. 하지만 속도가 느리다는 단점이 존재한다. 다음에는 이보다 속도가 좋은 정렬 알고리즘을 살펴보도록 하겠다.

stable과 unstable

  • stable : 정렬할 때 같은 값을 가진 수들이 정렬 전과 정렬 후에 순서가 바뀌지 않는 경우
  • unstable : 정렬할 때 같은 값을 가진 수들이 정렬 전과 정렬 후에 순서가 바뀌는 경우

다음의 예를 한 번 생각해보자.
ex) 5, 4, 8, 8, 5, 3, 1, 10, 6
숫자가 있고 순서를 부여해보자.
ex 5(1), 4(2), 8(3), 8(4), 5(5), 3(6), 1(7), 10(8), 6(9)

()안의 숫자는 해당 노드(수)가 들어온 순서를 뜻한다. 만약 정렬할 시에 key 값을 기준으로 정렬을 하되, 같은 key 값을 가진 노드는 들어온 순서에 따라 다시 정렬되어야 한다면 어떻게 할 것인가? 다음 결과와 같이 최종적으로 정렬된 정보가 바로 stable한 것이다. 정렬된 결과는 다음과 같다.

ex) 1(7), 3(6), 4(2), 5(1), 5(5), 6(9), 8(3), 8(4), 10(8)

  • 선택 정렬 : unstable

ex) 5(1), 4(2), 5(3), 2(4), 3(5)
위에서 5(1)과 2(4)를 교환한다.
ex) 2(4), 4(2), 5(3), 5(1), 3(5)
위의 결과가 나온다. 처음의 순서를 유지하지 않게 된다. 이러한 이유로 선택 정렬은 stable한 결과를 보장할 수 없기 때문에 unstable하다고 한다.

  • 버블 정렬 : stable
  • 삽입 정렬 : stable

참고