자료구조 23강 - O(n²) 정렬

O(n²) 정렬

 

- 정렬 알고리즘의 성능은 정렬하고자 하는 원소의 수(n)의 제곱(n²)에 비례함

- 이동 기반 정렬 : 삽입 정렬

- 교환 기반 정렬 : 버블 정렬, 선택 정렬 

 

 

삽입 정렬(Insertion Sort)

 

- 삽입 정렬 기본 원리

 

• 추가(insert) 연산에 기반한 정렬 알고리즘
• 정렬되지 않은 리스트의 원소들을 차례로 정렬된 리스트에 추가하면 정렬이 수행됨
• 원소를 이동시켜서 정렬을 수행함

 

- 삽입 정렬 기본 개념

 

• 배열의 가장 앞자리로부터 정렬된 부분 배열을 생성하고 그 크기를 증가시킴

부분 배열을 처음에는 배열의 첫 원소로부터 시작
마지막으로 부분 배열이 배열과 일치하게 되면 정렬 완료

• 새로운 원소를 정렬된 부분 배열의 적당한 위치에 삽입하여 부분 배열의 정렬을 유지
• 정렬된 배열에 새로운 원소를 삽입하는 연산이 필요함
• 삽입 후에도 배열의 정렬이 유지되어야 함

void insert (int x, int n, int b[]){
	int num=0;
	for(int i=0;i<n;i++){
		if(b[i]>x) {//x보다 큰 첫번째 b[i] 찾기
			num=i;
			break;
		}
	}
	for(int j=n-1;j>=i;j--){
		b[j+1]=b[j];//한칸씩 이동
	}
	b[i]=x;//b[i]에 삽입
}

 

- 삽입 정렬 알고리즘 설계 

 

① 배열의 원소를 하나씩 부분 배열에 삽입하면서 정렬을 수행

② 정렬이 끝난 배열의 앞부분을 부분 배열로 이용

 

K번째 원소까지 정렬이 끝난 상황 → a[0]~a[k-1]을 부분 배열로 이용

③ 부분 배열 a[0···k-1]에 대해서 (k+1)번째 원소인 a[k]를 a[0···k-1]에 삽입

→ 부분 배열은 a[0···k-1]에서 a[0···k]로증가

 

 

- 삽입 정렬 알고리즘 구현

 

void insert_sort (int n, int a[]){
	int i;
	for(int i=0;i<n;i++){
		insert(a[i],i+1,a);//i번째 원소를 부분 배열 a[0···i-1]에 삽입
	}
}

 

- 삽입 정렬 수행 예시

 

for-loop 이전, a[ ] = 82 61 5 30 74 → 82 61 5 30 74 
i=1 일 때, a[ ] = 82 61 5 30 74 → 61 82 5 30 74

i=2 일 때, a[ ] = 61 82 5 30 74 → 5 61 82 30 74

i=3 일 때, a[ ] = 5 61 82 30 74 → 5 30 61 82 74

i=4 일 때, a[ ] = 5 30 61 82 74 → 5 30 61 74 82

 

- 삽입 정렬 성능분석

 

• insert()의 수행시간 → O(n)
• insert()를 호출하는 횟수 → O(n)
• 결과 : O(n²)

 

 

버블 정렬(Bubble Sort)

 

- 버블 정렬 기본 원리

 

• 교환을 통해서 더 작은 원소를 앞으로 보냄
• 서로 인접한 원소들 사이의 교환을 반복해서 정렬을 수행함

 

- 버블 정렬 기본 개념

 

배열의 가장 앞자리에 최소값을 옮김
→ 배열의 가장 뒷자리로부터 원소들을 차례로 비교하면서 작은 값을 가장 앞 자리로 옮김

배열의 두 번째 자리에 두 번째 작은 값을 옮김
→ 배열의 가장 뒷자리로부터 원소들을 차례로 비교하면서 작은 값을 두번째 자리로 옮김

이 과정을 n-1번 반복
마치 거품(bubble)이 물밑에서 올라오는 듯 하여 bubble sort라고 한다
sinking sort라고도 불린다

 

- 버블 정렬 알고리즘 설계

 

배열의 임의의 위치(i번째 위치)에서 다음의 연산을 수행

i번째 위치에 i ~ (n-1)의 원소들 중에서 가장 작은 값이 옴 i번째에는 i번째 작은 값이 옴
→ i번째에는 i번째 작은 값이 옴
(n-1)번째 위치부터 (i+1)번째 위치까지 차근차근 비교하면서 진행함

 

- 버블 정렬 알고리즘 구현

 

• 배열의 임의의 위치 i번째 위치에서 다음의 연산을 수행함
• (n-1)번째 위치부터 (i+1)번째 위치까지 차근차근 비교하면서 진행함

void bubble_sort(int n, int a[]){
	int i, j;
	for(i=0;i<n-1;i++){//0번째부터 n-1번째까지 차례대로 가장 작은 값을 저장
		//i번째에는 i번째로 작은 값 저장
		for(j=n-1;j>i;j--){//n-1번째부터 i+1번째까지 진행 → 밑에서부터 올라옴
			if(a[j-1]>a[j]) swap(a[j-1],a[j]);
			//바로 위에 있는 원소와 비교해서 아래의 원소가 더 작으면 swap
		}
	}
}

 

• swap() 함수

① 두 매개변수의 값을 바꾸는 함수

② call-by-reference 이용

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

 

- 버블 정렬 수행 예시

 

i=0, j=4 일 때, a[ ] = 82 61 5 30 74 → 82 61 5 30 74
i=0, j=3 일 때, a[ ] = 82 61 5 30 74 → 82 61 5 30 74
i=0, j=2 일 때, a[ ] = 82 61 5 30 74 → 82 5 61 30 74
i=0, j=1 일 때, a[ ] = 82 5 61 30 74 → 5 82 61 30 74
i=1, j=4 일 때, a[ ] = 5 82 61 30 74 → 5 82 61 30 74
i=1, j=3 일 때, a[ ] = 5 82 61 30 74 → 5 82 30 61 74
i=1, j=2 일 때, a[ ] = 5 82 30 61 74 → 5 30 82 61 74
i=2, j=4 일 때, a[ ] = 5 30 82 61 74 → 5 30 82 61 74
i=2, j=3 일 때, a[ ] = 5 30 82 61 74 → 5 30 61 82 74
i=3, j=4 일 때, a[ ] = 5 30 61 82 74 → 5 30 61 74 82

 

- 버블 정렬 성능 분석

 

안쪽 for-loop의 수행 횟수 = n(n-1)/2 = O(n²)

 

 

선택 정렬(Selection Sort)

 

• 버블 정렬의 단점 : 최악의 경우 O(n²)번의 교환을 수행해야 한다
• 버블 정렬의 단점을 개선

① 최악의 경우에도 O(n)번만 교환하는 정렬의 필요

② i번째 자리에 올 원소는 i번째로 작은 원소

③ i번째로 작은 원소를 찾아서 i번째 원소와 교환

 

- 선택 정렬 기본 개념

• 배열의 첫 번째 자리에 최소 값을 옮김 → 배열에서 가장 작은 값과 첫 번째 원소와 교환
• 배열의 두 번째 자리에 두 번째 작은 값을 옮김 → 배열에서 두 번째 작은 값과 두 번째 원소와 교환
• 이 과정을 반복함
• 버블 정렬과 다른 점 : select_min() 함수

 

- 선택 정렬 기본 연산

 

배열에서 s번째 원소와 e번째 원소 사이에서 가장 작은 원소(최소값)의 인덱스를 찾는 연산

int select_min(int s, int e, int b[]){
	int min_idx = s;
	for(int i=s+1;i<=e;i++){
		if(b[i]<b[min_idx]) min_idx=i;
	}
	return min_idx;
}

 

- 선택 정렬 알고리즘 설계

 

• 정렬하고자 하는 배열의 첫 번째 원소부터 차례로 방문
• i번째 원소의 처리

a[i] ~ a[n-1] 중에서 최소값을 찾을 것 → min_idx는 최소값의 인덱스를 가리킴
최소값과 a[i]의 값을 교환할 것 → a[i]에 a[i] ~ a[n-1]까지의 최소값이 오도록 함

 

- 선택 정렬 알고리즘 구현

 

void selection_sort(int n, int a[]){
	int i, min_idx;
	for(i=0;i<n-1;i++){
		min_idx = select_min(i,n-1,a);
		swap(a[i],a[min_idx]);
	}
}

 

- 선택 정렬 실행 예시

 

i=0 일 때, a[ ] = 82 61 5 30 74 → 5 61 82 30 74
i=1 일 때, a[ ] = 5 61 82 30 74 → 5 30 82 61 74
i=2 일 때, a[ ] = 5 30 82 61 74 → 5 30 61 82 74
i=3 일 때, a[ ] = 5 30 61 82 74 → 5 30 61 74 82
i=4 일 때, a[ ] = 5 30 61 74 82 → 5 30 61 74 82

 

- 선택 정렬 성능 분석

 

• select_min() → n개에 대해서 수행 → O(n)
• select_min() 함수를 O(n)번 수행
• 결과 : O(n²)