1. 계산복잡도와 정렬의 하한

• 계산복잡도(computational complexity):
  • 알고리즘의 효율을 시간복잡도, 공간복잡도 기준으로 분석
  • 어떤 문제에 대해, “모든 알고리즘이 달성할 수 있는 최선의 하한(lower bound)”을 결정하는 것이 중요
• 정렬(sorting) 문제의 하한:
  • 비교 기반 정렬의 계산복잡도 하한은 Ω(n log n)
  • n개의 키를 정렬하는데 이보다 더 빠른 비교 기반 알고리즘은 존재하지 않음이 증명됨
  • 실제로 mergesort, heapsort 등은 Θ(n log n)로 동작

2. 시간복잡도, 공간복잡도, 제자리 정렬

• 시간복잡도(time complexity): 연산의 총 횟수(예: 비교, 할당)로 측정
• 공간복잡도(space complexity): 추가적으로 필요한 메모리(배열 등)의 크기
• 제자리 정렬(in-place sort): 추가 공간 사용 없이(상수 크기 메모리만) 입력 배열 내에서 정렬 수행

3. 주요 정렬 알고리즘 및 분석

3.1 교환정렬 (Exchange Sort)

• 아이디어: 모든 쌍을 비교하여 앞에 큰 값이 있으면 자리 교환

• 알고리즘:

  for (i = 1; i <= n-1; i++)
      for (j = i+1; j <= n; j++)
          if (S[j] < S[i])
              exchange S[i] and S[j];
  
  

• 최악 시간복잡도:

  • 비교: n(n-1)/2 = Θ(n²)
  • 할당(교환): 3 * n(n-1)/2 = Θ(n²)

• 평균:

  • 비교의 1/2에서 교환 발생 → 평균 교환 횟수는 최악의 1/2

• 특징: 제자리 정렬

3.2 삽입정렬 (Insertion Sort)

• 아이디어: 이미 정렬된 배열에 새로운 값을 “삽입”하듯 차례로 키를 끼워넣음

• 알고리즘:

  for (i = 2; i <= n; i++) {
      x = S[i];
      j = i - 1;
      while (j > 0 && S[j] > x) {
          S[j+1] = S[j];
          j--;
      }
      S[j+1] = x;
  }