선택/버블 정렬

정렬의 개요

1. 실행 방법에 따른 분류

1) 비교식 정렬과 분산식 정렬

- 비교식 정렬(Comparative Sort)

▪ 비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법

- 분산식 정렬(Distributive Sort)

▪ 키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법

 

2. 정렬 장소에 따른 분류

1) 내부 정렬과 외부 정렬

① 내부 정렬(Internal Sort)
▪ 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식
▪ 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨
▪ 내부 정렬 방식

② 외부 정렬(External Sort)

▪ 정렬할 자료를 보조 기억장치에서 정렬하는 방식

▪ 대용량의 보조 기억장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬 가능

▪ 외부 정렬 방식

3. 안정성에 따른 분류

1) 안정 정렬과 불안정 정렬

▪ 1차 키: 학점

▪ 2차 키: 학년
▪ 안정 정렬에서는
  1차 키로 정렬하더라도
  이전의 2차 키 정렬 순서가 유지됨

 

4. 정렬 대상에 따른 분류

1) 직접 정렬과 간접 정렬
- 직접 정렬(Direct Sorting)
▪ 원래 레코드를 정렬

- 간접 정렬(Indirect Sorting)

▪ 레코드의 인덱스(Index)를 정렬

 

 

선택 정렬

1. 정의 및 방법

1) 정의
▪ 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬

 

2) 수행 방법
① 전체 원소 중 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환함
② 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환함
③ 그 다음 세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환함
④ 이 과정을 반복하면서 정렬을 완성함

 

2. 알고리즘의 분석

1) 선택 정렬 알고리즘

selectionSort(a[ ], n)
	for (i←1; i<n; i←i+1) {
		a[i], …, a[n-1] 중에서 가장 작은 원소 a[k]를 선택하여,
		a[i]와 교환한다.
	}
end selectionSort( )

2) 메모리 사용 공간
▪ n개의 원소에 대하여 n개의 메모리 사용

 

3) 비교 횟수

버블 정렬

1. 정의 및 방법

1) 개요
“인접한 두 개의 원소를 비교하여 자리를 교환하는 방식”
▪ 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
▪ 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블(Bubble) 정렬이라 함

 

2. 알고리즘의 분석

1) 버블 정렬 알고리즘

bubbleSort(a[ ], n)
	for (i←n-1; i≥0; i←i-1) {
        for (j←0; j<i; j←j+1) {
			if (a[j]>a[j+1]) then {
				temp ← a[j];
				a[j] ← a[j+1];
				a[j+1] ← temp
			}
		}
	}
end bubbleSort( )

2) 메모리 사용 공간
▪ n개의 원소에 대하여 n개의 메모리 사용

 

3) 연산 시간