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

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