[k-mooc/자료구조] 06-1. 정렬(Sorting) - O(N^2) 정렬 알고리즘

정렬

지금까지 ‘정렬된 리스트’에서의 연산을 이야기해왔음

그렇다면 정렬되지 않은 리스트의 경우에는 → 정렬이 필요하다

💡 정렬(Sorting)
데이터를 정해진 키에 따라서 크기 순으로 배열하는 것
[예] 오름차순 (Ascending Order), 내림차순 (Descending Order)

정렬 알고리즘의 성능

정렬할 데이터의 개수가 n개 있다고 할 때, \(O(f(n))\) 으로 성능을 표시하게 되면:

1. \(O(n^2)\) 정렬 알고리즘
   1. 삽입 정렬: 원소의 이동 기반
   2. 버블 정렬: 원소의 교환 기반
   3. 선택 정렬: 원소의 교환 기반
2. \(O(nlogn)\) 정렬 알고리즘
   1. 합병 절렬
   2. 쾌속 정렬

 

O(n^2) 정렬

1. 삽입 정렬(Insertion Sort)

추가(Insert) 연산에 기반한 정렬 알고리즘으로, 정렬되지 않은 리스트의 원소들을 차례로 정렬된 리스트에 추가하면 정렬이 수행된다. 이 때 정렬은 원소를 이동시켜 수행한다.

✅ 개념
초기: 배열의 가장 앞자리(첫 번째 원소)만 포함하는 정렬된 부분 배열을 만든다.
확장: 배열의 다음 원소를 정렬된 부분 배열의 적절한 위치에 삽입하여 정렬된 상태를 유지한다.
- 이 과정을 배열의 끝까지 반복하면 → 전체 배열이 정렬된 결과를 얻게 된다.

⇒ 정렬된 배열의 상태를 유지하면서 새로운 원소를 삽입하는 연산이 필요하다.

void insert (int x, int y, int b[]) {
	//x보다 큰 첫번째 b[i] 탐색 
	for(int i=0; i<n; i++) {
		if(b[i] > x) break;
	}
	
	//한 칸씩 이동
	for(int j=n-1; j>=i; j--) {
		b[j+1] = b[j];
	}
	
	//새로운 원소 저장(삽입)
	b[i] = x;
}

 

알고리즘 설계와 구현

🔑 핵심: 배열의 원소를 차례로 부분 배열에 삽입하면서 정렬한다.

1. 정렬이 끝난 배열의 앞부분을 부분 배열로 이용한다.
   - `k`번째 원소까지 정렬이 끝났다면: `a[0] - a[k-1]`가 부분 배열이 된다.
2. 부분 배열에 대해 `k+1`번째 원소인 `a[k]`를 적절한 위치에 삽입하여 정렬을 유지한다.

//새로운 원소 x를 배열 b의 적절한 위치에 삽입
void insert(int x, int n, int b[]) {
	//x의 다음 인덱스(n) 전까지(이미 정렬된 부분 배열) x보다 큰 원소를 찾고 인덱스를 저장 - O(n)
	int idx;
	for(int i=0; i<n; i++) {
		if(b[i] > x) {
			idx = i; break;
		}
	}
	
	//b[idx]부터 b[n-1]까지의 값을 한 칸씩 뒤로 밀어 자리 만들기
	for(int j=n-1; j>=idx; j--) {
		b[j+1] = b[j];
	}
	
	//적절한 위치(x보다 큰 원소가 저장돼있던 인덱스의 자리)에 x 저장 - 정렬 상태 유지 + 삽입 완료 
	b[idx] = x;
}

//배열의 원소에 대해 차례대로 삽입 정렬 수행 
void insertion_sort(int n, int a[]) {
	int i;
	
	//O(n)
	for(int i=1; i<n; i++) {
		insert(a[i], i+1, a); //i번째 원소를 부분 배열에 삽입
	}
}

[예]

a[]: 82 61 5 30 74
-> 82 61 5 30 74
-> 61 82 5 30 74
-> 5 61 82 30 74
-> 5 30 61 82 74
-> 5 30 61 74 82 [완료]

성능 분석

`insert()`의 수행 시간 \(O(n)\)과 `insertion_sort()`의 호출 횟수 \(O(n)\)을 합쳐 \(O(n^2)\)가 된다.

 

 

2. 버블 정렬(Bubble Sort)

원소 간 교환을 통해 더 작은 원소를 앞으로 보내는 정렬 알고리즘으로, 서로 인접한 원소들 사이의 교환을 반복하여 정렬을 수행한다.

5
82
61
30
74

Best Case

82
61
74
30
5

Worst Case: (O(n^2)) 내림차순 정렬 → 각 원소마다 앞의 모든 원소들과 비교하여 정렬 필요

⚠️ 실제 버블 정렬은 위와 같은 최악의 경우를 만날 수 있는 정렬이라는 것을 염두에 두고 접근해야 한다.

 

✅ 개념
- 배열의 가장 앞자리부터 차례로 정렬한다.
- 각 단계에서 남은 부분 배열에서 가장 작은 값을 찾아 현재 위치와 교환한다.
   - 첫 번째 반복: 전체 배열에서 가장 작은 값을 찾아 첫 번째 위치에 배치
   - 두 번째 반복: 나머지 원소 중 가장 작은 값을 찾아 두 번째 위치에 배치
   - ...
   - 이러한 과정을 n-1번 반복하면 전체 배열이 오름차순으로 정렬된다.

 

알고리즘 설계와 구현

🔑 핵심: 인접한 두 원소를 비교해 큰 값을 뒤로 보내는 과정을 반복하여 정렬한다.

1. 배열을 앞에서부터 끝까지 탐색하며 인접한 두 원소를 비교한다.
   - 앞의 원소가 더 크면 두 값을 교환한다.
2. 이 과정을 n-1번 반복하면 가장 큰 값부터 차례로 뒤로 정렬된다.
3. 각 회차가 끝날 때마다 가장 큰 값이 맨 뒤로 <버블처럼> 밀려난다.

void swap(int& a, int& b) {
	int x = a;
	a = b;
	b = x;
}

void bubble_sort(int n, int a[]) {
	int i, j;
	
	//처음부터 끝까지
	for(i=0; i<n-1; i++) {
		//뒤에서부터 i번째 원소까지 각각 둘을 비교
		for(j=n-1; j>i; j--) {
			//뒤보다 앞 원소가 크면 자리 교환 (작은 원소가 앞으로 오도록)
			if(a[j-1] > a[j]) swap(a[j-1], a[j]);
		}
	}
}

[예]

a[]: 82 61 5 30 74

i=0
-> 82 61 5 30 74
-> 82 61 5 30 74
-> 82 5 61 30 74
-> 5 81 61 30 74

i=1
-> 5 81 61 30 74
-> 5 81 30 61 74
-> 5 30 81 61 74

i=2
-> 5 30 81 61 74
-> 5 30 61 81 74

i=3
-> 5 30 61 74 81

i=4
-> 5 30 61 74 81 [완료]

성능 분석

`bubble-sort()`의 `for-loop` 수행 횟수 \(O(n^2)\) ⇒ 최악의 경우 \(O(n^2)\) 번 교환을 수행해야 한다.

 

 

3. 선택 정렬(Selection Sort)

⚠️ 버블 정렬의 단점 개선: 최악의 경우에도 \(O(n)\)번만 교환?
     -> i번째 원소는 i번째로 작은 원소이므로, i번째 작은 원소를 찾아 i번째 원소와 교환한다.

✅ 개념
- 배열에서 가장 작은 값을 찾아 맨 앞 자리로 보낸다.
- 그다음으로 작은 값을 찾아 두 번째 자리로 보낸다.
이런 식으로 앞에서부터 차례대로 정렬해 나간다.

 

알고리즘 설계와 구현

🔑 핵심: 각 위치에서 남은 원소 중 가장 작은 값을 찾아 현재 위치와 교환한다.

1. 배열의 첫 번째 원소부터 차례로 방문한다.
2. 각 위치 i에 대해 `a[i]`부터 `a[n-1]`까지 중 최소값을 찾아 `a[i]`와 교환한다.

int select_min(int s, int e, int b[]) {
	int min_idx = s; //현재 위치

	//현재 위치 다음부터 끝까지 탐색하면서 최소값 찾기 - O(n)
	for(int i=s+1; i<=e; i++) {
		if(b[i] < b[min_idx]) min_idx = i;	
	}
	
	return min_idx;
}

void selection_sort(int n, int a[]) {
	int i;
	int min_idx;
	
	//O(n)	
	for(i=0; i<n-1; i++) {
		min_idx = select_min(i, n-1, a); //최소값 인덱스 
		swap(a[i], a[min_idx];           //교환
	}
}

[예]

a[]: 82 61 5 30 74

i=0
-> 5 61 82 30 74

i=1
-> 5 30 82 61 74

i=2
-> 5 30 61 82 74

i=3
-> 5 30 61 74 82

i=4 
-> 5 30 61 74 82 [완료]

성능 분석

`select_min()`은 `n`개에 대해 수행하므로 \(O(n)\)이 걸리고, `select_min()`을 \(O(n)\)번 수행하므로 총 \(O(n^2)\)가 소요된다.