[Algorithm] 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort)

1. 선택 정렬(Selection Sort)이란?

• 가장 작은 요소를 맨 앞으로 이동하고, 두번째 작은 요소는 맨 앞에서 두번째로 이동하는등의 작업을 반복하는 알고리즘이다.
• 시간 복잡도는 O(n^2)으로 효율이 좋지 않다. (버블 정렬 < 선택 정렬)
• 서로 떨어져있는 요소를 교환하므로 안정적이지 않다. 즉 중복된 요소가 존재할 경우, 정렬한 후 두 요소의 순서가 뒤바뀐다.

이미지 출처:&nbsp;https://he-s3.s3.amazonaws.com/media/uploads/2888f5b.png

 

1.1 선택 정렬 구현

public void selectionSort(int[] arr, int n) {
  for(int i = 0; i < n - 1; i++) {
    int min = i; // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스
    
    for(int j = i + 1; j < n; j++) {
      if(arr[j] < arr[min]) {
        min = j;
      }
      swap(arr, i min);
    }
  }
}

 

2. 삽입 정렬(Insertion Sort)

• 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘이다.
• 시간 복잡도는 O(n^2)으로 효율이 좋지 않다. (선택 정렬 < 삽입 정렬)
• 정렬은 두번째 요소부터 선택하여 진행한다.
• 서로 떨어져있는 요소들을 교환하는게 아니므로 안정적이다.

2.1 삽입 정렬 구현

public void insertionSort(int[] arr, int n) {
  for(int i = 1; i < n; i++) {
    int j;
    int temp = arr[i];
    
    for(j = i; j > 0 && arr[j - 1] > temp; j--) {
      arr[j] = arr[j - 1];
    }
    arr[j] = temp;
  }
}