[알고리즘] 기본 정렬 알고리즘(Selection sort, Bubble sort, Insertion sort)

1. Selection sort (선택 정렬)

---

• 선택 정렬의 작동 원리

1. 리스트에서 최소값을 찾는다.
2. 최소값을 찾으면, 배열의 맨 앞 원소와 자리를 교체한다.
3. 루프에서 맨 앞의 원소를 제외한 후 다시 루프를 돈다.

배열에서 어떤 값 하나를 선택해서 교체한다고 하여 선택 정렬이라고 한다. 이는 최소값이 아닌 최대값에도 작동한다. 최대값을 중심으로 정렬하는 경우, 배열의 맨 뒤 원소와 자리를 교체하며 루프를 돈다.

• 위 예시에서 최대값인 37을 찾았으므로 맨 뒷자리와 교체한다. 그렇다면 37은 정렬된 것이므로 제외하고, 나머지에 대해 다시 루프를 돈다. 나머지 중의 최대값인 29를 찾으면, 맨 뒷자리를 제외한 부분 중 가장 뒷자리인 13의 자리와 교체한다. 이후 모두 정렬될 때까지 반복한다.
  
  

void selectionSort(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) {
		int min_idx = i;
		// 최소값 arr[min_idx]를 찾는다.
		for (int j = i + 1; j < n; j++) { 
			if (arr[j] < arr[min_idx]) min_idx = j;
		} 

		// arr[i]와 최소값 arr[min_idx]를 swap한다.
		// 이때 arr[i]의 자리는 정리되지 않은 배열 요소 중 가장 맨 앞의 자리이다.
		int tmp = arr[i];
		arr[i] = arr[min_idx];
		arr[min_idx] = tmp;
	}
}

• 위 소스코드는 최소값을 기준으로 정렬하는 예이다. for문은 n-1번 루프를 반복하고, for문의 안에서 최소값을 찾기 위한 비교 횟수는 n-1, n-2, ... 식으로 줄어든다. 최악의 경우 시간 복잡도는 $O(n^2)$을 가진다.

2. Bubble sort (버블 정렬)

---

버블 정렬에서는 서로 인접한 두 원소를 비교해나가면서 정렬한다. 배열의 첫 원소값부터 시작해서 다음 값과 비교하면서 더 크다면 다음 값과 자리를 바꾼다. 이를 배열이 모두 정렬될 때까지 반복한다.

• pass 1에선 29에서부터 시작하여 마지막 원소값에 도달할 때까지 인접한 두 원소를 계속해서 비교해 나간다. 배열의 마지막 원소값이 정해진 후엔 그 원소를 제외한 나머지에 대해 다시 루프하며 비교한다. 이러한 정렬되는 모습이 거품이 움직이는 것과 같다고 하여 버블 정렬이라고 한다.
  
  

void bubbleSort(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

• 소스 코드가 간단하고 단순하여 사용하기 쉽지만, 인접한 두 원소값을 전부 비교해 나가는 데에 $n(n-1)/2$번의 연산이 일어나므로 시간 복잡도는 역시 $O(n^2)$을 가진다.

3. Insertion sort (삽입 정렬)

---

삽입 정렬은 배열의 모든 요소를 앞에서부터 차례대로 비교하여 적절한 자리에 삽입하는 정렬이다.

• 정렬은 배열의 2번째 값부터 시작한다. 배열의 맨 앞 원소부터 차례대로 비교해 나가는데, 12는 15보다 작기 때문에 15의 앞에 배치되는 것이 적절하므로 swap한다. 이후 13도 앞에서부터 비교해나간다. 13은 12보단 크기 때문에 12의 뒷자리로 가야 하나 15보다는 작으므로 12와 15의 사이에 배치된다. 이렇게 앞에서부터 비교하는 것을 배열이 모두 정렬될 때까지 반복한다.
  
  

구현을 쉽게 하기 위해 아래 코드에선 배열의 뒤에서부터 비교하여 한칸씩 밀어낸다.

void insertionSort(int arr[], int n) {
	for (int i = 1; i < n; i++) {
		int copy = arr[i];

		// 배열은 순서를 밀어내기 복잡하므로 뒤에서부터 비교하여 
		// 한칸씩 밀어내면서 copy한 값을 삽입할 자리를 찾는다.
		int j = i - 1;
		while (j >= 0 && arr[j] > copy) {
			arr[j + 1] = arr[j];
			j--;
		}
		// 찾아낸 빈 자리에 값을 삽입한다.
		arr[j + 1] = copy;
	}
}

• arr[i]값을 복사해 둔 후 while문에서 copy 값이 삽입될 적절한 위치를 찾는다. 만약 arr[j]가 copy 값보다 크다면 copy 값보다 뒤의 위치에 배치되어야 하므로 한칸씩 밀어낸다. 이를 반복하면 삽입할 적절한 위치를 찾을 수 있다.

• 시간 복잡도는 마찬가지로 $O(n^2)$을 가진다. 첫번째 for문은 $n-1$번 반복되는데, 삽입할 자리를 찾기 위해 배열의 원소들을 밀어내는 데에도 최악의 경우 $i-1$번의 비교가 필요하다.

참고자료
기본적인 정렬 알고리즘 / https://youtu.be/0dG7xTt5IfQ