[자료구조] 선택 정렬과 삽입 정렬

1. 정렬 알고리즘

• 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용

2. 선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
• 동작 예시
  • [Step 0] 처리되지 않은 데이터 중 가장 작은 ‘0’을 선택해 가장 앞의 7과 위치 변경
    

    

  • [Step 1] 처리되지 않은 데이터 중 가장 작은 ‘1’을 선택해 가장 앞의 5와 위치 변경
    

    

  • [Step 2] 처리되지 않은 데이터 중 가장 작은 ‘2’을 선택해 가장 앞의 9와 위치 변경
    
    

    

  • [Step 3] 처리되지 않은 데이터 중 가장 작은 ‘3’을 선택해 가장 앞의 7와 위치 변경
    
    

    

  • 이러한 과정 반복
    

    

  • 매번 가장 작은 데이터를 찾기 위해서 선형 탐색을 하는 것과 동일
• 소스 코드 (Python)
  

  array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
  
  for i in range(len(array)):
      min_index = i # 가장 작은 원소의 인덱스
      for j in range(i + 1, len(array)):
          if array[min_index] > array[j]:
              min_index = j
          array[i], array[min_index] = array[min_index], array[i]
  
  print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]​

• 소스 코드 (Java)
  

  import java.util.*;
  
  public class Main {
      public static void main(String[] args) {
          int n = 10;
          int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
          
          for (int i = 0; i < n; i++) {
              int min_index = i; // 가장 작은 원소의 인덱스
              
              for (int j = i + 1; j < n; j++) {
                  if (arr[min_index] > arr[j]) {
                      min_index = j;
                  }
              }
              
              int temp = arr[i];
              arr[i] = arr[min_index];
              arr[min_index] = temp;
          }
          
          for (int i = 0; i < n; i++) {
              System.out.print(arr[i] + " "); // 0 1 2 3 4 5 6 7 8 9
          }
      }
  }​

• 시간 복잡도
  • 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 함
  • 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같음
    • N + (N - 1) + (N - 2) + ... + 2
  • 이는 (N^2 + N - 2) / 2로 표현 가능
  • 따라서 O(N^2)

3. 삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작
• 동작 예시
  • [Step 0] 첫 번째 데이터 ‘7’은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 ‘5’가 어떤 위치로 들어갈지 판단
    • ‘7’의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재
      

      

  • [Step 1] 이어서 ‘9’가 어떤 위치로 들어갈지 판단
    

    

  • [Step 2] 이어서 ‘0’이 어떤 위치로 들어갈지 판단
    

    

  • [Step 3] 이어서 ‘3’이 어떤 위치로 들어갈지 판단
    

    

  • 이러한 과정 반복
    

    

• 소스 코드(Python)
  

  array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
  
  for i in range(1, len(array)):
      for j in range(i, 0, -1):
          if array[j] < array[j - 1]:
              array[j], array[j - 1] = array[j - 1], array[j]
          else:
              break
              
   print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]​

• 소스 코드(Java)
  

  import java.util.*;
  
  public class Main {
      public static void main(String[] args) {
          int n = 10;
          int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
          
          for (int i = 0; i < n; i++) {            
              for (int j = i; j > 0; j--) {
                  if (arr[j] < arr[j - 1]) {
                      int temp = arr[i];
                      arr[i] = arr[min_index];
                      arr[min_index] = temp;
                  }
                  else break;
              }
          }
          
          for (int i = 0; i < n; i++) {
              System.out.print(arr[i] + " "); // 0 1 2 3 4 5 6 7 8 9
          }
      }
  }

• 시간 복잡도
  • 삽입 정렬의 시간 복잡도는 O(N^2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용
  • 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작
    • 최선의 경우, O(N)의 시간 복잡도를 가짐
    • 이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행한다면?
      • 두 번째 원소부터 다 비교했을 때 이미 오름차순으로 되어 있어 탐색 과정이 바로 멈춰서 O(N)