[알고리즘] 정렬 알고리즘이란?(Insertion Sort, Bubble Sort)

정렬 알고리즘의 종류

정렬 알고리즘은 크게 두 가지 방식으로 나눌 수 있음

• 비교 기반 정렬
  • 두 데이터의 크기를 비교하며 정렬하는 방식
  • 종류: 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort), 퀵 정렬(Quick Sort) 등
  • 비교 기반 정렬은 아무리 빨라도 평균적으로 $O(n \log n)$의 시간 복잡도보다 좋을 수 없음
• Linear Time Sort
  • 데이터의 값을 직접 비교하지 않고, 다른 속성을 활용해 정렬합
  • 종류: 계수 정렬(Counting Sort), 기수 정렬(Radix Sort), 버킷 정렬(Bucket Sort) 등

---

삽입 정렬 (Insertion Sort)

• 데이터를 하나씩 확인하며, 각 데이터를 이미 정렬된 부분 배열의 올바른 위치에 '삽입'하는 방식으로 동작
• 손에 쥔 카드를 정렬할 때, 새로운 카드를 이미 정렬된 카드 뭉치의 알맞은 자리에 끼워 넣는 것과 유사

 

def insertion_sort(A): # A: 정렬할 숫자 리스트
  # 주어진 리스트 A를 삽입 정렬 방식으로 정렬
  # 리스트의 두 번째 요소(인덱스 1)부터 마지막 요소까지 반복
  for i in range(1, len(A)):
    key = A[i]  # 현재 삽입될 값을 key 변수에 저장
    
    # A[i]를 정렬된 부분 배열 A[0...i-1]에 삽입
    j = i - 1
    
    # j가 배열의 시작에 도달하지 않았고,
    # key 값보다 큰 요소를 찾을 때까지 왼쪽으로 이동
    while j >= 0 and A[j] > key:
      A[j + 1] = A[j]  # 요소를 오른쪽으로 한 칸 이동
      j = j - 1
      
    # 찾은 올바른 위치에 key 값을 삽입
    A[j + 1] = key

# --- 실행 예제 ---
my_list = [5, 2, 4, 6, 1, 3]
print(f"정렬 전: {my_list}")

insertion_sort(my_list)

print(f"정렬 후: {my_list}")

정확도 증명: 루프 불변식 (Loop Invariant)

• 알고리즘이 왜 정확하게 동작하는지는 루프 불변식(Loop Invariant)이라는 개념을 통해 증명 가능
•  루프의 반복 과정에서 항상 참으로 유지되는 성질을 의미하며, 다음 세 가지 단계를 통해 증명

1. 초기화 (Initialization)
   • 루프가 처음 시작되기 전에 루프 불변식이 참이어야 함
   • 삽입 정렬에서, 첫 번째 원소만 포함하는 부분 배열 A[1...0] (비어 있음) 또는 A[1...1]은 그 자체로 정렬된 상태이므로, 초기 조건은 만족
2. 유지 (Maintenance)
   • 루프의 한 반복이 시작될 때 불변식이 참이었다면, 그 반복이 끝난 후에도 여전히 참으로 유지되어야 함
   • i번째 반복에서 A[1...i-1]이 정렬되어 있다고 가정
     - 알고리즘은 A[i]를 가져와 A[1...i-1] 내의 올바른 위치에 삽입
     - 그 결과, A[1...i]는 전체적으로 정렬된 상태가 됨
     - 따라서 다음 반복(i+1)을 앞두고도 불변식은 유지
3. 종료 (Termination)
   • 루프가 종료될 때, 이 불변식은 알고리즘의 정확성을 보장
   • 삽입 정렬의 루프가 모든 원소(n개)를 다 확인하고 종료되면, 루프 불변식에 따라 부분 배열 A[1...n]은 완벽하게 정렬된 상태가 됨

시간 복잡도 (Running Time)

• 최악: O(n²)

---

버블 정렬 (Bubble Sort)

• 인접한 두 원소를 비교하여, 정해진 기준(예: 오름차순)에 맞지 않으면 서로의 위치를 바꾸는 과정을 반복
• 가장 크거나 작은 원소가 배열의 끝으로 '거품'처럼 올라오는 모습과 같다고 해서 버블 정렬이라 명명

def bubble_sort(a): #  a: 정렬할 숫자 리스트
# 주어진 리스트 a를 버블 정렬 방식으로 정렬
  n = len(a)
  
  # 리스트의 길이 - 1 만큼 외부 루프를 반복
  # 한 번의 반복마다 가장 큰 원소가 맨 뒤로 이동
  for i in range(n - 1):
    
    # 내부 루프는 정렬되지 않은 부분을 순회
    # i가 증가할수록 이미 정렬된 뒷부분은 제외하고 반복
    for j in range(n - 1 - i):
      
      # 현재 원소(a[j])가 다음 원소(a[j+1])보다 크면
      if a[j] > a[j+1]:
        
        # 두 원소의 위치를 바꿈 (swap).
        a[j], a[j+1] = a[j+1], a[j]

# --- 실행 예제 ---
my_list = [5, 2, 4, 6, 1, 3]
print(f"정렬 전: {my_list}")

bubble_sort(my_list)

print(f"정렬 후: {my_list}")

 

정확도 증명

• 알고리즘이 종료된다는 것과, 최종 결과 배열 A'이 A’[1] ≤ A’[2] ≤ … ≤ A’[n] 조건을 만족함을 보여야 함
• 루프 불변식을 통해 증명 가능
• 일반적으로 버블 정렬은 바깥쪽 루프 i가 1부터 n-1까지, 안쪽 루프 j가 n부터 i+1까지 순회하며 A[j]와 A[j-1]을 비교/교환하는 구조를 가짐

안쪽 루프(2-4번째 줄)의 루프 불변식

• 루프 불변식 서술:
  - 안쪽 for 루프(변수 j)가 특정 횟수 반복된 시작 시점에서, A[j]는 부분 배열 A[j...n]에서 가장 작은 값을 가짐
• 증명:
  • 초기화: j=n으로 루프가 처음 시작될 때, 부분 배열 A[n...n]은 A[n] 자신뿐이므로, A[n]이 가장 작은 값이라는 명제는 참
  • 유지:
    - j번째 반복 시작 시 A[j]가 A[j...n]에서 가장 작다고 가정
    - 루프는 A[j-1]과 A[j]를 비교하여, 만약 A[j-1]이 더 크다면 둘을 교환
    - 이 과정을 거치면, 위치 j-1에는 기존의 A[j-1]과 A[j] 중 더 작은 값이 오게 됨
    - 다음 반복(j-1)이 시작될 때 A[j-1]은 부분 배열 A[j-1...n]에서 가장 작은 값이 됨
  • 종료: 안쪽 루프가 종료되면(j가 i가 되면), A[i]는 부분 배열 A[i...n](아직 정렬되지 않은 나머지 부분)에서 가장 작은 값을 갖게 됨

바깥쪽 루프(1-4번째 줄)의 루프 불변식 및 최종 증명

• 루프 불변식 서술:
  - 바깥쪽 for 루프(변수 i)가 특정 횟수 반복된 시작 시점에서, 부분 배열 A[1...i-1]은 원본 배열의 i-1개 가장 작은 원소들로 구성되며, 이들은 정렬된 상태
• 증명:
  • 초기화: i=1로 루프가 처음 시작될 때, 부분 배열 A[1...0]은 비어 있으므로, 이 명제는 참
  • 유지:
    - i번째 반복 시작 시 A[1...i-1]이 정렬되어 있다고 가정
    - 안쪽 루프가 완료되면 A[i]에는 나머지 배열 A[i...n]에서 가장 작은 원소가 위치하게 됨
    - A[1...i-1]은 이미 그보다 작은 값들로 정렬되어 있었으므로, 이제 A[1...i]는 원본 배열의 i개 가장 작은 원소들이 정렬된 상태로 존재하게 됨
  • 종료: 바깥쪽 루프가 종료되면(i가 n이 되면), 루프 불변식에 따라 A[1...n-1]은 n-1개의 가장 작은 원소들로 구성되며 정렬되어 있음
    - 이는 자연스럽게 마지막 원소 A[n]이 가장 큰 값이 됨을 의미
    - 전체 배열 A[1...n]이 A’[1] ≤ A’[2] ≤ … ≤ A’[n]을 만족하게 됨

시간 복잡도 (Running Time)

• 최악: O(n²)