키를 비교하여 정렬하는 알고리즘

2차시간 정렬 알고리즘: 삽입정렬(Insertion Sort), 교환정렬(Exchange Sort), 선택정렬(Selection Sort)

Θ(n lg n) 정렬 알고리즘: 합병정렬(Merge Sort), 빠른정렬(Quick Sort), 힙정렬(Heap Sort)

키를 비교하지 않고 정렬하는 알고리즘: 기수정렬(Radix Sort)

삽입정렬(insertion sort)

이미 정렬된 배열에 레코드를 삽입하여 정렬하는 알고리즘

즉, 정렬되지 않은 배열에서 키를 순차적으로 선택하여 오름차순으로 정렬중인 앞쪽 부분의 배열에 삽입하는 알고리즘

C++ 스타일 수도코드

void insertionsort (int n, keytype S[])
{
	index i, j;
	keytype x;

	for ( i = 2; i <=; i++ ) {
		x = S[i];
		j = i - 1;
		while ( j > 0 && S[j] > x ) {
			S[j + 1] = S[j];
			j--;
		}
		S[j + 1] = x;
	}
}

Java 구현 코드

public class Insertion {

	public static void insertionsort(int n, int[] S) {
		
		for (int i = 1; i < n; i++) {
			int x = S[i];				// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
			int j = i - 1;
			
			while (j >= 0 && S[j] > x) {	// S[j] > x 가 키 비교횟수의 최악의 경우 시간복잡도의 단위연산
				S[j+1] = S[j];			// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
				j--;
			}
			
			S[j+1] = x;				// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Insertion.java

키 비교횟수의 최악의 경우 시간복잡도

· 단위연산: S[j]와 x의 비교

· 입력크기: 정렬할 키의 개수 n

while 루프를 j가 (-1)이 될 때까지 반복하고 빠져 나가는 경우가 최악.

&& 연산에서 앞의 조건이 false이면 뒤의 조건은 검사하지 않으므로 비교는 j번, 즉 (i-1)번 이루어진다.

i값은 배열의 첫 번째 인덱스를 제외하고 마지막 인덱스 까지 검사하므로 (n-1)개가 된다.

· 총 비교횟수:

레코드 지정횟수의 최악의 경우 시간복잡도

· 단위연산: x에 S[i]를 지정, S[j+1]에 S[j]를 지정, S[j+1]에 x를 지정

· 입력크기: 정렬할 키의 개수 n

while 루프를 j가 (-1)이 될 때까지 반복하고 빠져 나가는 경우가 최악. (i-1)번 이루어진다.

여기에 while 루프 전에 x에 S[i]를 지정하는 값이 고정적으로 1번, 루프를 벗어난 후에 S[j+1]에 x를 지정하는 값이 고정적으로 1번 추가되어 총 while 루프 한번에 (i-1)+2번 키 지정을 하게된다.

· 총 비교횟수:

추가적인 저장장소 사용

배열 내에서 정렬이 일어나므로 제자리 정렬에 해당한다.

따라서 추가적인 저장장소 사용량은  Θ(1)이다.

교환정렬(exchange sort)

정렬되지 않은 배열에서 선택된 인덱스의 키와 나머지 키를 비교하여 자신보다 낮은 경우 계속해서 교환하여 가장 작은 키를 인덱스 순차적으로 위치시키는 알고리즘.

예를 들어 1부터 9까지 아홉개의 숫자가 무작위로 섞여있는 배열이 있는 경우 0번째 인덱스에 있는 키를 선택한 후, 나머지 1부터 8까지 인덱스에 있는 키와 모두 비교하여 최소값인 1이 맨 앞에 오게 한다. 1번째 인덱스에도 마찬가지로 나머지 2부터 8까지 인덱스에 있는 키와 모두 비교하여 최소값 2가 오게 한다.

C++ 스타일 수도코드

void exchangesort (int n, keytype S[])
{
	index i, j;
	for ( i = 1; i <= n - 1; i++ )
		for ( j = i + 1; j <= n; j++ )
			if ( S[j] < S[i] )
				exchange S[i] and S[j];
}

Java 구현 코드

public class Exchange {

	public static void exchangesort(int n, int[] S) {
		
		for(int i = 0; i < n - 1; i++) {
			for(int j = i + 1; j < n; j++) {
				if(S[i] > S[j]) {			// 키 비교횟수의 모든 경우 시간복잡도의 단위연산
					int temp = S[i];		// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
					S[i] = S[j];		// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
					S[j] = temp;		// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
				}
			}
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Exchange.java

키 비교횟수의 모든 경우 시간복잡도

· 정렬되지 않은 배열이 어떻게 존재하여도 항상 모든 배열의 내용을 비교하므로 모든 경우 시간복잡도를 계산한다.

· 단위연산: S[i]와 S[j]의 비교

입력크기: 정렬할 키의 개수 n

변수 i에 대한 for 루프는 (n-1)만큼 반복한다.

i 루프가 첫 번째 수행될 때 j 루프는 (n-1)번, 두 번째에는 (n-2)번, ... , 마지막에는 1번 수행한다.

레코드 지정횟수의 최악의 경우 시간복잡도

· 단위연산: S[i]와 S[j], temp 상호간 지정

· 입력크기: 정렬할 키의 개수 n

비교할 때마다 항상 교환하는게 최악의 경우이므로 모든 경우 시간복잡도에 레코드 지정횟수을 곱한 것(x3)과 같다.

추가적인 저장장소 사용

배열 내에서 정렬이 일어나므로 제자리 정렬이고 추가적인 저장장소 사용량은 Θ(1)이다.

선택정렬(selection sort)

교환정렬을 약간 변형한 알고리즘으로 교환정렬의 단점을 제거하였다.

자신보다 작은 값을 찾으면 키값을 교환했던 교환정렬과는 달리, 키의 인덱스를 저장하는 변수를 이용하여 가장 가장 작은 키의 인덱스를 저장해 두었다가 반복이 끝나면 마지막에 가장 작은 키와 교환한다.

즉, 교환정렬에서 교환으로 인한 오버헤드를 줄인다.

순서대로 레코드를 선택하여 정렬하는 알고리즘을 모두 통칭하여 선택정렬이라 한다.

따라서 교환정렬이나 힙정렬도 선택정렬에 해당한다.

C++ 스타일 수도코드

void selectionsort ( int n, keytype S[] )
{
	index i, j, smallest;
	for ( i = 1; i <= n - 1; i++ ) {
		smallest = i;
		for ( j = i + 1; j <= n; j++ )
			if ( S[j] < S[smallest] )
				smallest = j;
		exchange S[i] and S[smallest];
	}
}

Java 구현 코드

public class Selection {

	public static void selectionsort(int n, int[] S) {
		
		for (int i = 0; i < n - 1; i++) {
			int smallest = i;
			
			for (int j = i + 1; j < n; j++) {
				if (S[j] < S[smallest]) {	// 키 비교횟수의 모든 경우 시간복잡도의 단위연산
					smallest = j;
				}
			}
			
			int temp = S[i];				//
			S[i] = S[smallest];			// 레코드 지정횟수의 모든 경우 시간복잡도의 단위연산
			S[smallest] = temp;			//
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Selection.java

키 비교횟수의 모든 경우 시간복잡도

· 정렬되지 않은 배열이 어떻게 존재하여도 항상 모든 배열의 내용을 비교하므로 모든 경우 시간복잡도를 계산한다.

· 단위연산: S[j]와 S[smallest]의 비교

입력크기: 정렬할 키의 개수 n

변수 i에 대한 for 루프는 (n-1)만큼 반복한다.

i 루프가 첫 번째 수행될 때 j 루프는 (n-1)번, 두 번째에는 (n-2)번, ... , 마지막에는 1번 수행한다.

레코드 지정횟수의 모든 경우 시간복잡도

· 단위연산: S[i]와 S[j], temp 상호간 지정

· 입력크기: 정렬할 키의 개수 n

비교횟수와 상관없이 (i-1)번 반복이 일어난다. 교환을 위한 상호 지정은 3번 일어난다.

추가적인 저장장소 사용

배열 내에서 정렬이 일어나므로 제자리 정렬이고 추가적인 저장장소 사용량은 Θ(1)이다.

삽입정렬, 교환정렬, 선택정렬 비교

삽입정렬과 교환정렬

- 키의 비교를 기준으로 삽입정렬의 수행속도는 최소한 교환정렬만큼은 항상 빠르고, 평균적으로는 더 빠르다.

- 레코드 지정을 기준으로 하면 최악의 경우와 평균의 경우 모두 교환정렬보다 삽입정렬이 빠르다.

- 따라서 삽입정렬이 교환정렬보다 좋은 알고리즘이다.

교환정렬과 선택정렬

- 정렬된 경우를 제외하면 선택정렬이 교환정렬보다 좋은 알고리즘이다. 정렬된 경우에는 교환정렬에선 교환이 일어나지 않는다.

삽입정렬과 선택정렬

- 키의 비교를 기준으로 삽입정렬의 수행속도는 최소한 교환정렬만큼은 항상 빠르고, 평균적으로는 더 빠르다.

- 레코드 지정을 기준으로 하면 n과 레코드가 충분히 크면 선택정렬이 삽입정렬보다 확실히 좋다.

내용 출처

Foundations of Algorithms Using C++ Pseudocode 3rd Edition 알고리즘; Richard Neapolitan, Kumarss Naimipour; 도경구 역; 사이텍미디어