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

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

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

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

기수정렬(radix sort)

순서를 매길 수 있다는 것 이외에 키에 대한 정보가 없는 경우, 앞서 알아본 키를 비교하는 방법 이외에 할수 있는 정렬방법은 없다.

기수 정렬은 키가 음이 아닌 10진수 정수라는 것을 알 때 사용할 수 있다. 자리수(digit)를 따라 분배하여 정렬하는 알고리즘이다.

정렬하려 하는 숫자가 3자리 숫자라 가정하면, 100의 자리에서 0..9까지 더미로 숫자를 분배할 수 있다. 이 안에서 다시 10의 자리에서 0..9까지 분배 하고 마지막으로 1의 자리에서 0..9까지 분배하면 자동적으로 정렬이 되게 된다.

따라서 이 알고리즘은 분배에 의한 정렬(sorting by distribution)이다.

숫자가 아니라 알파벳 또한 분배할 수 있다. 이 경우에는 0..9까지의 10개 더미가 아니라 a..z까지의 26개의 더미로 나눠서 분배해야 한다.

http://rightwayman2013.blogspot.kr/2010/09/algo-83-radix-sort.html

C++ 스타일 수도코드

// 아래는 연결된리스트의 구현에 필요한 노드의 선언이다.
struct nodetype
{
	keytype key;
	nodetype* link;
};

typedef nodetype* node_pointer;

// 아래는 알고리즘이다.
void radixsort ( node_pointer& marsterlist, int numdigits )
{
	index i;
	node_pointer list[0..9];

	for ( i = 1; i <= numdigits; i++ ) {
		distribute ( masterlist, list, i );
		coalesce( masterlist, list );
	}
}

void distribute ( node_pointer& masterlist, node list[], index i )
{
	index j;
	node_pointer p;

	for ( j = 0; j <= 9; j++ )
		list[j] = NULL;
	p = masterlist;
	whild ( p != NULL ) {
		j = p->key에서 i자리 값;
		p를 list[j]의 끝에 링크;
		p = p -> link;
	}
}

void coalesce ( node_pointer& masterlist, node list[] )
{
	index j;

	masterlist = NULL;
	for ( j = 0; j <= 9; j++ )
		list[j]에 있는 마디들을 masterlist의 끝에 링크;
}

Java 구현 코드

import main.Print;

public class Radix {

	public static node radixsort(node masterlist, int numdigits) {
		
		node[] list = new node[10];
		
		for (int i = 1; i <= numdigits; i++) {
			distribute(masterlist, list, i);
			
//			for(int j = 0; j < list.length; j++) {
//				node temp = list[j];
//				System.out.print(j + ":");
//				while (temp != null) {
//					System.out.print(" [" + temp.key + "]");
//					temp = temp.link;
//				}
//				System.out.println();
//			}
			
			masterlist = coalesce(masterlist, list);
//			int[] arr = masterlist.getResult();
//			Print.printArray(arr);
		}
		
		return masterlist;
	}
	
	private static void distribute(node masterlist, node[] list, int i) {
		
		int j;
		node p;
		
		for(j = 0; j <= 9; j++) {
			list[j] = null;
		}
		p = masterlist;
		while (p != null) {
			j = (int) ((p.key % Math.pow(10, i)) / Math.pow(10, (i-1)));
			node temp;
			
			if (list[j] == null) {
				temp = p;
				list[j] = temp;
			} else {
				temp = list[j];
				while(temp.link != null) {
					temp = temp.link;
				}
				temp.link = p;
				temp = temp.link;
				
			}
			
			p = p.link;
			temp.link = null;
		}
	}
	
	private static node coalesce(node masterlist, node[] list) {
		
		masterlist = null;
		node temp = null;
		for (int j = 0; j <= 9; j++) {
			if (list[j] != null) {
				if (masterlist == null) {
					masterlist = list[j];
					temp = masterlist;
				} else {
					temp.link = list[j];	
				}
				while (temp.link != null) {
					temp = temp.link;
				}
			}
		}
		
		return masterlist;
	}
	
	public static class node {
		public int key;
		public node link;
		
		public int[] getResult() {
			
			int[] result;
			int size = 1;
			
			node temp = link;
			while (temp != null) {
				temp = temp.link;
				size++;
			}
			
			result = new int[size];
			
			temp = link;
			for (int i = 0; i < size; i++) {
				if (temp != null) {
					if (i == 0) {
						result[i] = key;
					} else {
						result[i] = temp.key;
						temp = temp.link;
					}
				}
			}
			
			return result;
		}
	}
}

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

중간에 주석은 테스트를 위한 출력 코드이다. 출력에 필요한 관련 클래스는 github에서 나머지 코드를 찾아보시라.

모든 경우 시간복잡도

단위연산: 비교연산이 없기 때문에 다른 연산을 찾아야 한다. coalesce에서 masterlist의 끝에 노드를 추가하는 연산, distribute에선s while루프의 일부 또는 전체를 단위연산으로 취급할 수 있다. 

입력크기: masterlist에서 정수의 개수 n, 각 정수에서 십진숫자의 최대 개수 numdigits

masterlist 전체를 처음부터 차례로 따라가려면 항상 distribute의 while루프를 n번 수행해야 한다. masterlist에 리스트를 모두 추가하려면 항상 coalesce의 for 루프를 10번 수행해야 한다. (여기서는 마지막 포인터도 두어, 위의 java 코드와는 달리 while루프 없이 한번에 저장할 수 있는 더 효율적인 알고리즘이라 하자)

이 프로시저는 radixsort에서 numdigits번 for문에 의해 호출된다.

따라서,

numdigits와 n을 기준으로 한계값을 표현하기 때문에, 이 알고리즘은 Θ(n)이 아니다. numdigits값을 임의로 크게 하여 n을 기준으로, 임의로 큰 시간복잡도를 만들 수 있다. 10억 자리(numdigits)의 숫자 10개(n)을 정렬한다고 고려 하면 Θ(n^2) 시간이 걸린다. 보통은 numdigits이 훨씬 작다. 최선의 경우 시간 복잡도는 Θ(n lg n)이고, 보통은 최선의 경우에 수렴한다.

추가적인 저장장소 사용

masterlist와 더미를 나타내는 리스트에서 새로운 노드를 만들지 않는다. masterlist의 노드가 더미 리스트로 이동하고, 다시 masterlist로 정렬되는 방식이다. 다만 노드에서 key와 쌍이되는 link가 사용되기 때문에 Θ(n) 링크 만큼 추가 공간을 필요로 한다.

내용 출처

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

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

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

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

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

합병정렬(merge sort)

정렬되지 않은 배열을 2개의 배열로 분할하고, 그 두 부분배열을 각각 정렬하고, 다시 합병하여 정렬된 배열로 만든다.

분할정복(divide-and-conquer) 절차

1. 분할: 배열을 n/2개 아이템을 가진 2개의 부분배열로 분할한다.

2. 정복: 정렬함으로써 각 부분배열을 정복한다(푼다). 배열이 충분히 작지 않으면 재귀 호출을 한다.

3. 통합: 부분배열에 대한 답들을 합병하여 하나의 정렬된 배열로 만든다.

C++ 스타일 수도코드

void mergesort ( int n, keytype S[] )
{
	if ( n > 1 ) {
		const int h = └h / 2┘, m = n - h;
		keytype U[1..h], V[1..m];
		copy S[1] through S[h] to U[1] through U[h];
		copy S[h+1] through S[n] to V[1] through V[m];
		mergesort(h ,U);
		mergesort(m, V);
		merge(h, m, U, V, S);
	}
}

void merge ( int h, int m , const keytype U[], const keytype V[], keytype S[] )
{
	index i, j, k;

	i = 1; j = 1; k = 1;
	while ( i <= h && j <= m ) {
		if ( U[i] < V[j] ) {
			S[k] = U[i];
			i++;
		}
		else {
			S[k] = V[j];
			j++;
		}
		k++;
	}
	if ( i > h )
		copy V[j] through V[m] to S[k] through S[h+m];
	else
		copy U[i] through U[h] to S[k] through S[h+m];
}

Java 구현 코드

public class Merge {
	
	public static void mergesort (int n, int[] S) {
		
		if(n > 1) {
			final int h = n / 2;
			final int m = n - h;
			int[] U = new int[h];
			int[] V = new int[m];
			
			for(int i = 0; i < h; i++) {
				U[i] = S[i];
			}
			
			for(int i = 0; i < m; i++) {
				V[i] = S[h+i];
			}
			
			mergesort(h, U);
			mergesort(m, V);
			merge(h, m, U, V, S);
		}
	}
	
	public static void merge(int h, int m, final int[] U, final int[] V, int[] S) {
		int i, j, k;	// index
		
		i = 0;
		j = 0;
		k = 0;
		
		while(i < h && j < m) {
			if(U[i] < V[j]) {	// 단위연산
				S[k] = U[i];
				i++;
			} else {
				S[k] = V[j];
				j++;
			}
			k++;
		}
		
		if(i >= h) {
			while(j < m) {
				S[k] = V[j];
				j++;
				k++;
			}
		} else {
			while(i < h) {
				S[k] = U[i];
				i++;
				k++;
			}
		}
	}
}

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

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

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

· 입력크기: 두 입력 배열 아이템의 개수, h와 m

최악의 경우는 i와 j가 while 루프 안에서 최대에 도달한 상태에서 빠져나올 때이다. 즉 i가 h에 도달하고, j가 (m-1)에 도달하거나, 반대로 j가 m에 도달하고 i가 (h-1)에 도달한 상태에서 while 루프를 빠져나오는 경우이다.

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

· 단위연산: merge에서 일어나는 비교연산

· 입력크기: 배열 S의 아이템의 수, n

총 비교횟수는 mergesort(h, U)와 mergesort(m, V)를 재귀호출 하는데 수행되는 비교연산의 횟수와 merge를 호출하는데 수행되는 비교연산의 횟수의 합이다.

n이 2의 거듭제곱인 경우 다음과 같다.

입력크기 n이 1인 경우에는 if 문을 통과하지 못하고 merge는 행해지지 않으므로 W(1)은 0이다.

위 재현식의 해를 구하면 아래와 같다. 해법은 출처의 도서를 참고하자.

추가적인 저장장소 사용

mergesort에서 분할된 배열 U, V를 새롭게 선언하여 사용한다. 첫 mergesort에서 입력 크기 n의 절반인 n/2 크기의 배열 두개가 생성된다. 따라서 n 크기의 저장장소가 새로이 필요하다. 다음 mergesort가 호출된다(코드상에서는 U배열에 대한 mergesort가 수행된다). 이 경우에는 n/4크기의 배열 두개가 생성되므로 n/2 크기의 저장장소가 필요하며, 다음 재귀호출에서는 n/4 크기의 배열이 필요하다. 따라서 추가적인 저장장소의 크기는 다음과 같다.

따라서 2n이다.

위의 알고리즘보다 추가적인 저장장소를 덜 사용하는 개선된 합병정렬을 알아보자.

C++ 스타일 수도코드

void mergesort2 ( index low, index high )
{
	index mid;

	if ( low < high ) {
		mid = └(low + high) / 2┘;
		mergesort2(low, mid);
		mergesort2(mid + 1, high);
		merge2(low, high);
	}
}

void merge2 ( index low, index mid, index high )
{
	index i, j, k;
	keytype U[low..high];

	i = low; j = mid + 1; k = 0;
	while ( i <= mid && j <= high ) {
		if ( S[i] < S[j] ) {
			U[k] = S[i];
			i++;
		}
		else {
			U[k] = S[j];
			j++;
		}
		k++;
	}
	if ( i > mid )
		move S[j] through S[high] to U[k] through U[high];
	else
		move S[i] through s[mid] to U[k] through U[high];

	move U[low] through U[high] to S[low] through S[high];
}

Java 구현 코드

public class Merge2 {

	private int[] S;
	
	public Merge2(int[] S) {
		this.S = new int[S.length];
		
		for(int i = 0; i < S.length; i++) {
			this.S[i] = S[i];
		}
	}
	
	public void mergesort2(int low, int high) {
		int mid;
		
		if(low < high) {
			mid = (low + high) / 2;
			mergesort2(low, mid);
			mergesort2(mid+1, high);
			merge2(low, mid, high);
		}
	}
	
	private void merge2(int low, int mid, int high) {
		int i, j, k;
		int[] U = new int[high - low + 1];	// 추가적인 메모리를 사용하는 지역배열
		
		i = low;
		j = mid + 1;
		k = 0;
		
		while(i <= mid && j <= high) {
			if(S[i] < S[j]) {
				U[k] = S[i];
				i++;
			} else {
				U[k] = S[j];
				j++;
			}
			
			k++;
		}
		
		if(i > mid) {
			while(j <= high) {
				U[k] = S[j];
				j++;
				k++;
			}
		} else {
			while(i <= mid) {
				U[k] = S[i];
				i++;
				k++;
			}
		}
		
		for(int x = 0; x < U.length; x++) {
			S[low + x] = U[x];
		}
	}
}

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

위 코드는 S 배열이 전역변수로 선언되어 있다. 재귀호출을 하여도 동일한 배열을 사용하기 때문에 파라미터로 같은 값이 계속 넘어가기에 굳이 넘겨줄 필요가 없기 때문이다. 자바코드를 구현할 때에는 배열을 멤버변수로 설정하여 생성자 설정시 배열을 설정하고 메서드를 호출할 수 있도록 하였다. 아니면 이 전 mergesort 처럼 배열을 직접 넘겨줘도 무방하다.

위와 같이 구현하므로써 merge2가 호출될 때마다 배열이 생성되고 다시 삭제된다. 가장 아래에 1개씩으로 분할되었을 때는 크기가 2인 배열이 생성되고 다시 해제된다. 합병하는 과정이서 최상단에 도달했을때 입력크기인 n만큼의 배열이 생성된다. 따라서 추가적인 저장장소 사용은 n이다.

동적계획법을 사용한 합병정렬

재귀 구현시 필요한 스택연산의 비용부담을 피할 수 있는 방법이다. 앞서 알고리즘이 분할정복법에 기반한 하향식(top-down) 방식이라면 이 방식은 상향식(bottom-up) 합병정렬 알고리즘 구현이다.

C++ 스타일 수도코드

void mergesort3( int n, keytype S[] )
{
	int m;
	index low, mid, high, size;
	m = 2^┌lg n┐;
	size = 1;
	repeat ( lg m times ) {
		for ( low = 1; low <= m - 2*size + 1; low = low + 2*size ) {
			mid = low + size - 1;
			high = minimum(low + 2*size - 1, n);
			merge3(low, mid, high, S);
		}
		size = 2 * size;
	}
}

void merge3( int low, int mid, int high, int[] S )
{
	// merge2와 구현 동일
}

Java 구현 코드

public class Merge3 {
	
	public static void mergesort3(int n, int[] S) {
		int size = 1;
		int m = (int) Math.pow(2, Math.ceil(Math.log(n)/Math.log(2)));
		
		for(int i = 0; i < (Math.log(m)/Math.log(2)); i++) {
			for (int low = 0; low < m - (2*size) + 1; low = low + (2*size)) {
				int mid = low + size - 1;
				int high = ((low + (2*size) - 1) > n - 1 ? n - 1 : (low + (2*size) - 1));
				merge3(low, mid, high, S);
			}
			
			size = 2 * size;
		}
	}
	
	public static void merge3(int low, int mid, int high, int[] S) {
		
		if(low < high && mid < high) {
			
			int i, j, k;
			int[] U = new int[high - low + 1];	// 추가적인 메모리를 사용하는 지역배열
			
			i = low;
			j = mid + 1;
			k = 0;
			
			while(i <= mid && j <= high) {
				if(S[i] < S[j]) {
					U[k] = S[i];
					i++;
				} else {
					U[k] = S[j];
					j++;
				}
				
				k++;
			}
			
			if(i > mid) {
				while(j <= high) {
					U[k] = S[j];
					j++;
					k++;
				}
			} else {
				while(i <= mid) {
					U[k] = S[i];
					i++;
					k++;
				}
			}
			
			for(int x = 0; x < U.length; x++) {
				S[low + x] = U[x];
			}
		}
	}
}

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

연결된 리스트를 사용한 합병정렬

합병정렬에서 합병시 키를 교환하는 오버헤드를 줄이기 위해 연결된 리스트를 사용할 수도 있다. 특히 정렬하고자 하는 데이터가 많아질 수록 추가적인 저장장소 사용량을 줄일 수 있다. 실제 데이터를 교환하지 않고 연결된 리스트 노드의 링크만 바꿔서 표기하면 되기 때문이다.

아래 알고리즘은 배열에 기반한 연결된 리스트 구현이다. 노드의 링크는 배열의 인덱스를 저장하여 다른 노드를 가리키게 된다.

C++ 스타일 수도코드

void mergesort4( index low, index high, index& mergedlist)
{
	index mid, list1, list2;

	if (low == high) {
		mergedlist = low;
		S[mergedlist].link = 0;
	}
	else {
		mid = └(low + high) / 2┘;
		mergesort4(low, mid, list1);
		mergesort4(mid + 1, high, list2);
		merge4(list1, list2, mergedlist)'
	}
}

void merge4( index list1, index list2, index& mergedlist )
{
	index lastsorted;

	if ( S[list1].key < S[list2].key ) {
		mergedlist = list1;
		list1 = S[list1].link;
	}
	else {
		mergedlist = list1;
		list1 = S[list2].link;
	}
	lastsorted = mergedlist;
	while ( list1 != 0 && list2 != 0 )
		if ( S[list1].key < S[list2].key ) {
			S[lastsorted].link = list1;
			lastsorted = list1;
			list1 = S[list1].link;
		}
		else {
			S[lastsorted].link = list2;
			lastsorted = list2;
			list2 = S[list2].link
		}
	if ( list1 == 0 )
		S[lastsorted].link = list2;
	else
		S[lastsorted].link = list1;
}

Java 구현 코드

public class Merge4 {
	
	private node[] S;
	
	public Merge4(node[] S) {
		this.S = S;
	}

	public int mergesort4(int low, int high, int mergedlist) {
		
		if(low == high) {
			mergedlist = low;
			S[mergedlist].link = -1;
		} else {
			int mid = (low + high) / 2;
			int list1 = mergesort4(low, mid, low);
			int list2 = mergesort4(mid + 1, high, mid + 1);
			mergedlist = merge4(list1, list2, mergedlist);
		}
		
		return mergedlist;
	}
	
	private int merge4(int list1, int list2, int mergedlist) {
		
		int lastsorted;
		
		if (S[list1].key < S[list2].key) {
			mergedlist = list1;
			list1 = S[list1].link;
		} else {
			mergedlist = list2;
			list2 = S[list2].link;
		}
		lastsorted = mergedlist;
		
		while (list1 != -1 && list2 != -1) {
			if (S[list1].key < S[list2].key) {
				S[lastsorted].link = list1;
				lastsorted = list1;
				list1 = S[list1].link;
			} else {
				S[lastsorted].link = list2;
				lastsorted = list2;
				list2 = S[list2].link;
			}
		}
		if (list1 == -1) {
			S[lastsorted].link = list2;
		} else {
			S[lastsorted].link = list1;
		}
		
		return mergedlist;
	}
	
	public static class node {
		public int key;
		public int link;
	}
}

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

자바는 call by value이기 때문에 &와 같은 alias 타입으로 파라미터 전달하는 것을 지원하지 않으므로 C++스타일 수도코드와는 달리 리턴 타입의 메소드를 선언하여 작성하였다. 위의 알고리즘을 통과한 배열을 인덱스 순서대로 찍으면 당연히 그대로 출력되지만, mergesort4 메서드를 호출하여 반환된 인덱스를 시작노드로 하여 노드 안의 link를 따라 출력하면 정렬된 형태로 출력하게 된다.

위 알고리즘의 경우 추가적인 저장장소는 key가 아닌 link를 저장하기 위한 변수가 사용되므로 Θ(n)만큼 필요하다. 그 외에 node를 옮기기 위한 새로운 노드나 배열을 만들지 않는다.

또한 레코드 지정을 하지 않고 link의 값만 바꾸기 때문에 레코드 지정횟수의 시간복잡도는 0이다. 레코드를 서로 이웃한 배열 슬롯에 순서대로 놓을 필요가 있는 경우에도 Θ(n)으로 줄인다.

빠른정렬(quick sort)

임의의 아이템을 pivot으로 설정하고(보통 가장 앞에 있는 아이템), 이 pivot을 기준으로 작은 아이템은 앞으로, 큰 아이템은 뒤로 보내고 다시 분할된 아이템들을 기준으로 정렬하는 방법이다.

C++ 스타일 수도코드

void quicksort ( index low, index high )
{
	index pivotpoint;

	if ( high > low ) {
		partition( low, high, pivotpoint );
		quicksort( low, pivotpoint - 1 );
		quicksort( pivotpoint + 1, high );
	}
}

void partition ( index low, index high, index& pivotpoint )
{
	index i, j;
	keytype pivotitem;

	pivotitem = S[low];
	j = low;
	for ( i = low + 1; i <= high; i++ )
		if ( s[i] < pivotitem ) {
			j++;
			exchange S[i] and S[j];
		}
	pivotpoint = j;
	exchange S[low] and S[pivotpoint];
}

Java 구현 코드

public class Quick {

	private int[] S;
	
	public Quick(int[] S) {
		this.S = S;
	}
	
	public void quicksort(int low, int high) {
		int pivotpoint;
		if(high > low) {
			pivotpoint = partition(low, high);
			quicksort(low, pivotpoint - 1);
			quicksort(pivotpoint + 1, high);
		}
	}
	
	private int partition(int low, int high) {
		int i, j;
		int pivotitem;
		int pivotpoint;
		int temp;
		
		pivotitem = S[low];
		j = low;
		
		for(i = low + 1; i <= high; i++) {
			if(S[i] < pivotitem) {	// 단위연산
				j++;
				
				temp = S[i];
				S[i] = S[j];
				S[j] = temp;
			}
		}
		
		pivotpoint = j;
		temp = S[low];
		S[low] = S[pivotpoint];
		S[pivotpoint] = temp;
		
		return pivotpoint;
	}
}

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

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

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

· 입력크기: n = high - low + 1

첫 번째 아이템을 제외한 모든 아이템이 항상 비교된다.

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

· 단위연산: partition에서 일어나느 비교연산

· 입력크기: 배열 S의 아이템의 수, n

최악의 경우는 내림차순 또는 오름차순 형태로 이미 정렬되어 있는 경우에 해당한다. 정렬된 경우 분할시 한쪽은 크기가 0이고 나머지 한쪽은 크기가 (n-1)인 배열로 쪼개지기 때문에 재귀호출횟수가 그만큼 늘어나게 된다.

따라서,

W(0) = 0 이므로 재현식은 아래와 같다.

위 재현식의 해를 구하면 아래와 같다. 해법은 출처의 도서를 참고하자.

키 비교횟수의 평균의 경우 시간복잡도(quicksort)

· 단위연산: partition에서 일어나느 비교연산

· 입력크기: 배열 S의 아이템의 수, n

배열에 있는 숫자들이 위치할 확률이 다르지 않으므로 모두 동등한 확률을 갖는다고 가정한다. 그러므로 partition이 넘겨주는 pivotpoint 값은 1부터 n까지의 어떤 수가 될 확률이 모두 같다. 분포가 다른 경우(예를 들어 사람의 이름을 정렬하는 경우, 희귀한 이름과 흔한 이름간의 분포가 다르기에 확률도 달라진다) 적용할 수 없다.

(1) - (2)를 하면 아래와 같다.

다음과 같이 놓으면

아래와 같은 재현식이 된다.

위 재현식의 해를 구하면 아래와 같다. 해법은 출처의 도서를 참고하자.

추가적인 저장장소 사용

합병정렬과는 달리 추가적인 배열이 필요가 없다. 하지만 첫 부분배열을 정렬하는 동안, 다른 부분배열의 처음과 마지막 인덱스는 활성 레코드 스택에 저장되어야 하기 때문에 제자리정렬이 아니다.

또한 합병정렬과 달리 정확히 반으로 분할된다는 보장이 없기 때문에 한쪽은 0의 크기로, 한쪽은 (n-1)크기로 분할된다면 최악의 경우 추가적인 저장장소 사용량은 Θ(n)이다.

힙정렬(heap sort)

힙(heap)이라는 자료구조를 이용하여 정렬하는 방법이다. 힙정렬에 앞어서 관련된 자료구조를 잠깐 짚고 넘어가자.

마디의 깊이: 뿌리마디(root)에서 그 마디(node)로 가는 유일한 경로상에 있는 이음선(edge)의 개수

트리의 깊이(depth): 트리에 속하는 모든 마디의 깊이 중 최대값

잎마디(leaf): 자식마디가 없는 마디

내부마디: 최소한 하나의 자식마디를 가진 마디. 즉, 잎마디가 아닌 모든 마디

완전한 이진 트리(complete binary tree)

· 내부마디는 모두 자식마디가 2개 있다.

· 잎마디는 모두 깊이가 d이다.

http://doctrina.org/maximum-height-of-red-black-tree.html

실질적으로 완전한 이진 트리(essentially complete binary tree)

· (d - 1)의 깊이까지는 완전한 이진 트리이다.

· 깊이가 d인 마디는 모두 왼쪽 끝으로 모여 있다.

http://apprize.info/science/algorithms/7.html

참고 도서에서의 표현과 달리 완전한 이진 트리를 포화 이진 트리(fully binary tree)로, 실질적으로 완전한 이진 트리를 완전한 이진 트리로 설명하는 경우가 더 많은듯 보인다. 책에서는 이렇게 설명하였으니 표현대로 써 놓았으나 이 표현을 알아두는 것도 좋을 듯 하다.

http://cs.stackexchange.com/questions/54171/is-a-balanced-binary-tree-a-complete-binary-tree

힙(heap)

· 마디에 저장된 값은 순서가능집합(ordered set: 순서를 매길 수 있는 원소로 구성된 집합)에서 온다.

· 각 마디에 저장된 값은 그의 자식마디에 저장된 값보다 크거나 같다. 이를 힙 성질(heap property)이라고 한다.

http://oniondev.egloos.com/288205

힙정렬은 뿌리노드에 있는 키를 제거하고, 바닥마디에 있는 키로 바꾼 뒤, 힙 성질을 유지하도록 트리의 변화를 주는 방식을 반복하므로써 수행할 수 있다.

즉, 힙정렬을 위해서는 힙이 힙 성질을 유지할 수 있도록 하는 메소드(siftdown), 뿌리마디에서 키를 제거하고 바닥마디의 값을 가져오는 메소드(root), 뿌리마디에서 제거한 키를 배열 S에 정렬하는 메소드(removekeys), 그리고 맨 처음 정렬되지 않은 값들을 heap으로 만드는 메소드(makeheap)이 필요하다.

아래에서는 힙 자료구조를 만들기 위해 배열을 사용할 것이다.

C++ 스타일 의사코드

// 아래는 heap 자료 구조이다.
struct heap{
	keytype S[1..n];
	int heapsize;
};

void siftdown( heap& H, index i )
{
	index parent, largerchild;
	keytype siftkey;
	bool spotfound;

	siftkey = H.S[i];
	parent = i;
	spotfound = false;
	while (2*parent <= H.heapsize && !spotfound ) {
		if (2*parent < H.heapsize && H.S[2*parent] < H.S[2*parent + 1])
			largerchild = 2*parent + 1;
		else
			largerchild = 2*parent;
		if ( siftkey < H.S[largerchild] ) {
			H.S[parent] = H.S[largerchild];
			parent = largerchild;
		}
		else
			spotfound = true;
	}
	H.S[parent] = siftkey;
}

keytype root ( heap& H )
{
	keytype keyout;

	keyout = H.S[1];
	H.S[1] = H.S[heapsize];
	H.heapsize = H.heapsize - 1;
	siftdown(H, 1);
	return keyout;
}

void remotekeys ( int n, heap& H, keytype S[] )
{
	index i;

	for ( i = n; i >= 1; i-- )
		S[i] = root(H);
}

void makeheap ( int n, heap& H )
{
	index i;

	H.heapsize = n;
	for ( i = └n/2┘; i >= 1; i-- )
		siftdown(H, i);
}

// 아래는 힙정렬 메소드
void heapsort ( int n, heap& H )
{
	makeheap (n, H);
	removekeys (n, H, H.S);
}

Java 구현 코드

public class Heap {

	private int[] S;
	private int heapsize;
	
	public Heap(int[] S) {
		
		heapsize = S.length;
		this.S = new int[heapsize + 1];
		for(int i = 0; i < heapsize + 1; i++) {
			if(i == 0) {
				this.S[0] = 0;
			} else {
				this.S[i] = S[i-1];
			}
		}
	}
	
	private void siftdown(int i) {
		
		int parent, largerchild;
		int siftkey;
		boolean spotfound;
		
		siftkey = S[i];
		parent = i;
		spotfound = false;
		while (2*parent <= heapsize && !spotfound) {
			if (2*parent < heapsize && S[2*parent] < S[2*parent+1]) {
				largerchild = 2*parent+1;
			} else {
				largerchild = 2*parent;
			}
			
			if (siftkey < S[largerchild]) {
				S[parent] = S[largerchild];
				parent = largerchild;
			} else {
				spotfound = true;
			}
			
		}
		
		S[parent] = siftkey;
	}
	
	private int root() {
		
		int keyout;
		
		keyout = S[1];
		S[1] = S[heapsize];
		heapsize = heapsize - 1;
		siftdown(1);
		
		return keyout;
	}
	
	private void removekeys() {
		
		for (int i = S.length-1; i >= 1; i--) {
			S[i] = root();
		}
	}
	
	private void makeheap() {
		
		for (int i = (S.length-1)/2; i >= 1; i--) {
			siftdown(i);
		}
	}
	
	public void heapsort() {
		
		makeheap();
		removekeys();
	}
	
	public int[] getResult() {
		
		int[] result = new int[S.length - 1];
		for (int i = 1; i < S.length; i++) {
			result[i-1] = S[i];
		}
		
		return result;
	}
}

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

힙정렬 알고리즘 수도코드를 실 구현코드로 작성시 문제가 되는건, 알고리즘에서는 배열을 인덱스 1부터 시작하는 배열로 보는 반면에 구현 코드는 0부터 시작하기에 이를 맞춰주는데 어려움이 생긴다. 이전에 구현했던 다른 알고리즘은 그저 (-1) 해주므로써 문제가 해결되지만 힙정렬의 경우는 배열을 힙구조로 사용하기 위해 해당 인덱스의 *2를 왼쪽 자식노드, *2+1을 오른쪽 자식구조로 판단하는 계산을 하기 때문에 조금 더 머리를 써야 한다. 그렇게 복잡하게 구현할 경우 추후에 구현 코드를 이해하는데 어렵기 때문에, 차라리 아래와 같이 0번째 인덱스를 비운 배열을 사용하여 알고리즘을 구현하였다.

수도코드와는 달리 메소드들을 객체에 종속된 메소드로 구현하여 생성자에서 정렬하고자 하는 자료를 입력받은 후, 전역변수처럼 값을 사용하였다.

http://blog.naver.com/PostView.nhn?blogId=redwave102&logNo=80074139499

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

· 단위연산: siftdown 프로시저에서 키의 비교

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

프로시저 makeheap과 removekeys는 둘 다 siftdown을 호출한다. 따라서 이 두 프로시저를 따로 분석하여야 한다. 분석은 출처 도서를 참고해주시기 바란다.

n이 2의 거듭제곱일 때,

makeheap에 의해 행해지는 최대 비교횟수: 2(n - 1)

removekeys에 의해 행해지는 최대 비교횟수: 2nlgn - 4n + 4

힙정렬에서 키의 최대 비교횟수: 2(n - 1) + 2nlgn - 4n + 4 = (2nlgn - n + 1)  2nlgn

키 비교횟수의 평균의 경우 시간복잡도(heapsort)

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

추가적인 저장장소 사용

힙정렬은 제자리정렬이다. 따라서 Θ(1)이다.

합병정렬, 빠른정렬, 힙정렬 비교

빠른정렬과 힙정렬

- 키의 비교와 레코드 배정에서 평균적으로 빠른정렬보다 나쁘다.

- 빠른정렬의 추가적인 공간 사용량은 최소이므로 빠른정렬이 선호된다.

합병정렬와 빠른정렬

- 전체 입력 레코드 배열 크기 만큼의 배열을 추가적으로 사용하고, 또한 합병정렬은 빠른정렬이 평균적으로 하는 것보다 레코드 지정횟수가 항상 3배 가량 많기 때문에, 빠른정렬이 평균적으로 피의 비교횟수가 약간 많음에도 합병정렬보다 선호된다.

- 연결된리스트를 사용한 합병정렬(합병정렬4)은 이와 관련된 단점이 거의 모두 제거한다. 유일한 단점은 각 키에 대응되는 추가적인 링크를 사용하기 때문에 Θ(n)만큼의 공간을 사용한다는 것이다.

내용 출처

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

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

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; 도경구 역; 사이텍미디어

단위연산(basic operation): 알고리즘 내의 어떤 명령문이나 명령문 군을 선정하여, 알고리즘이 수행한 총 작업의 양을 이 명령문이나 명령문 군을 수행한 횟수에 대략적으로 비례하도록한다. 이 명령문 또는 명령문 군을 단위연산이라 한다.

시간복잡도 분석(time complexity analysis): 입력크기의 값에 대해서 단위연산을 몇 번 수행하는지를 구하는 것

입력 값에 상관 없이 입력크기에 따라 시간복잡도가 달라지는 경우

모든 경우 시간복잡도(every-case time complexity, T(n))

입력 값과 입력크기에 따라 시간복잡도가 달라지는 경우

최악의 경우 시간복잡도(worst-case time complexity, W(n)): 단위연산이 수행되는 최대 횟수 고려

평균의 경우 시간복잡도(average-case time complexity, A(n)): 알고리즘이 수행할 단위연산의 평균 횟수 고려, 입력 값에 대한 각각의 확률을 부여해야 함

최선의 경우 시간복잡도(best-case time complexity, B(n): 알고리즘이 수행할 단위연산의 최소 횟수 고려

* 모든 경우 시간복잡도를 구할 수 없는 알고리즘에 대하여, 최선의 경우 분석보다는 최악의 경우나 평균의 경우 분석을 훨씬 더 자주 실시함

큰 O(big O)

주어진 복잡도 함수 f(n)에 대해서, O(f(n))은 n ≥ N을 만족하는 모든 n에 대해 다음 부등식이 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

만약 g(n) ∈ O(f(n))이면, "g(n)은 f(n)의 큰 O이다"라고 한다.

예) 

위의 경우 n ≥ 10에 대해서는 다음과 같이 된다.

따라서 큰 O의 정의에서 c = 2와 N = 10을 취할 수 있으므로 다음과 같이 결론 지을 수 있다.

큰 O는 함수의 점근적인 상한(asymptotic upper bound)을 준다.

오메가(omega)

주어진 복잡도 함수 f(n)에 대해서, Ω(f(n))은 n ≥ N을 만족하는 모든 n에 대해 다음 부등식이 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

만약 g(n) ∈ Ω(f(n))이면, "g(n)은 f(n)의 오메가이다"라고 한다.

예) 

위의 경우 n ≥ 0에 대해서는 다음과 같이 된다.

따라서 오메가의 정의에서 c = 1과 N = 0을 취할 수 있으므로 다음과 같이 결론 지을 수 있다.

오메가는 함수의 점근적인 하한(asymptotic lower bound)를 나타낸다.

차수(order)

주어진 복잡도 함수 f(n)에 대해서, 다음과 같이 정의한다.

Θ(f(n))는 n ≥ N을 만족하는 모든 n에 대해서 다음 부등식이 만족하는 양의 실수 c, d와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

만약 g(n) ∈ Θ(f(n))이면, "g(n)은 f(n)의 차수이다"라고 한다.

작은 o(small o)

주어진 복잡도 함수 f(n)에 대해서, o(f(n))은 모든 양의 실수 c에 대해 n ≥ N을 만족하는 모든 n에 대하여 다음 부등식을 만족하는 음이 아닌 정수 N이 존재하는 모든 복잡도 함수 g(n)의 집합이다.

만약 g(n) ∈ o(f(n))이면, "g(n)은 f(n)의 작은 o이다"라고 한다.

위의 정의는 모든 양의 실수 c에 대해서 그 범위가 성립해야 하므로 g(n)은 f(n)같은 함수보다는 궁극적으로 훨씬 좋다.

내용 출처

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

그림 출처

GeeksforGeeks, http://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/