정렬 알고리즘에 대해 공부하려 한다. 이번 포스팅에서는 정렬 알고리즘의 개념과 안정성(Stability), 기초적인 비교 알고리즘에 대해 작성하고자 한다.

1. 정렬 알고리즘이란?

여러 개의 데이터를 일정한 순서(오름차순 또는 내림차순)로 배열하는 알고리즘이다.

1.1 정렬 알고리즘을 사용하는 이유

• 데이터 검색 속도 향상
  • 정렬된 데이터는 이진 탐색(Binary Search) 같은 빠른 탐색이 가능하다.
• 데이터 분석 및 처리 효율 증가
  • 순위, 통계, 데이터 비교가 쉬워진다.
• 다른 알고리즘의 기반
  • 많은 알고리즘이 정렬을 전제로 동작한다.

1.2 내부 정렬, 외부 정렬, 제자리 정렬의 개념

• 내부 정렬 : 입력의 크기가 주 기억 장치보다 크지 않음 -> 컴퓨터 메모리 내부에서 정렬

• 외부 정렬 : 입력의 크기가 매우 커서 보조 기억 장치에 저장해야 하는 경우에 사용하는 정렬, 보조기억장치에서 부분적으로 주 기억 장치로 옮기면서 처리되는 정렬

• 제자리 정렬 : 입력 크기에 비례하는 추가 공간을 필요로 하지 않는 알고리즘. 보통 공간 복잡도가 $O(1)\ 또는\ O(logn)$ 를 넘지 않으면 제자리 정렬 알고리즘이라고 한다.

1.3 정렬 알고리즘에서 안정성이란?

• 값이 같은 데이터들의 상대적인 순서가 정렬 후에도 유지되는 성질을 의미한다.

예를 들어 점수와 학생 데이터가 있다고 하자.

점수	학생
90	A
80	B
90	C
70	D

점수를 기준으로 정렬하면

안정 정렬

점수	학생
70	D
80	B
90	A
90	C

같은 점수 90인 데이터에서 A → C 순서가 유지된다.

불안정 정렬

점수	학생
70	D
80	B
90	C
90	A

같은 값 90의 순서가
A → C 에서 C → A 처럼 바뀌었다.

안정 정렬 종류 : 버블 정렬, 삽입 정렬, 병합 정렬, 팀 소트, 계수 정렬 등이 있다.
불안정 정렬 종류 : 선택 정렬, 퀵 정렬, 힙 정렬, 셸 정렬 등이 있다.

2. 기초적인 비교 정렬 알고리즘

• 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬 등이 있다.
• 모두 구현이 비교적 쉽고 메모리를 적게 사용하므로 제자리 정렬 알고리즘이며 공간 복잡도는 O(1)이다.
• 대부분의 경우 향상된 정렬 알고리즘에 비해서 비효율적이다.

2.1 선택 정렬

• 선택 정렬은 이름 그대로 현재 위치에 들어갈 데이터를 '선택'해서 바꾸는 직관적이고 단순한 정렬 알고리즘이다.
• 배열에서 가장 작은 원소를 찾아 맨 앞의 원소와 자리를 교환하는 과정을 반복하여 정렬을 완성한다.
• 구현이 매우 간단하고 추가 메모리를 사용하지 않는다는 장점이 있지만, 시간 복잡도가 $O(N^2)$ 이기 때문에 데이터의 개수가 많아질수록 성능이 급격히 떨어져 실제 서비스에서는 잘 사용되지 않는다.
  

구현 코드

arr = [9, 6, 7, 3, 5]
min_idx = 0
for i in range(len(arr)-1):
  min_idx = i  # 최솟값의 인덱스

  for j in range(i+1, len(arr)): # 실제 최솟값의 위치를 찾는 부분
    if arr[min_idx] > arr[j]:
      min_idx = j
  
  temp = arr[min_idx]  # 현재 위치의 값과 최소값을 Swap
  arr[min_idx] = arr[i]
  arr[i] = temp

2.2 버블 정렬

• 버블 정렬은 서로 인접한 두 원소를 비교하여, 앞의 원소가 뒤의 원소보다 크면 자리를 교환하며 정렬하는 알고리즘이다.
• 이 과정을 배열 끝까지 반복하면 가장 큰 값이 맨 뒤로 이동한다. 그다음엔 맨 끝을 제외한 나머지 배열에 대해 같은 과정을 반복한다.
• 구현이 매우 단순하지만, 자리를 바꾸는 연산(Swap)이 빈번하게 일어나기 때문에 실제로는 선택 정렬보다도 느린 경우가 많아 거의 쓰이지 않는다.
  

구현 코드

  arr = [7, 4, 5, 1, 3]   

  for i in range(len(arr)-1):

    for j in range(0, len(arr)-1-i):
      if arr[j+1] < arr[j]:

        temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp

2.3 삽입 정렬

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

• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입한다.

• key값은 2번째 인덱스부터 시작되며, key값이 자료의 길이만큼 이동되었을 때 정렬이 완성된다.

• 데이터가 이미 어느 정도 정렬된 상태라면 매우 효율적이다.
  

  arr = [9, 4, 3, 5, 1]

  for i in range(1, len(arr)):

      key = arr[i]

      j = i - 1   # arr[j] 는 key와 크기를 비교할 데이터의 인덱스

      while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]
        j -= 1

      arr[j+1] = key 

  print(arr)

2.4 셸 정렬

• 리스트를 일정한 간격에 따라 나누고, 각 부분 리스트를 삽입 정렬을 통해 정렬하는 방법이다.
• 조금이라도 정렬이 된 상태에 가까운 배열로 만든 후에 삽입정렬을 수행하는 방법이 쉘 정렬이라고 할 수 있겠다.
  → 쉘 정렬은 삽입 정렬을 보완한 방법!
• 데이터를 멀리씩 이동시킬 수 있어 삽입 정렬보다 초기 이동 횟수를 크게 줄여준다.

쉘 정렬 과정

1. 초기 시작 간격(gap)을 정한다. 간격을 k라고 하자.
   1.1 간격의 초깃값: (정렬할 값의 수)/2
   1

• 구현 코드

  def shell_sort(arr):
      n = len(arr)
      gap = n // 2

      while gap > 0:
          for i in range(gap, n):
              temp = arr[i]
              j = i

              while j >= gap and arr[j - gap] > temp:
                  arr[j] = arr[j - gap]
                  j -= gap

              arr[j] = temp

          gap //= 2

      return arr

3. 효율적인 비교 정렬 알고리즘

3.1 퀵 정렬

3.2 병합 정렬

3.3 팀 소트

3.4 힙 정렬

3.5 트리 정렬

4. 비교하지 않는 정렬 알고리즘

4.1 기수 정렬

4.2 버킷 정렬