합병 정렬, 퀵 정렬, 기수 정렬

합병 정렬 (Merge sort)

합병 정렬은 요소가 하나만 남을 때까지 리스트를 반으로 나눠준 후, 나눴던 리스트를 대소 관계에 맞게 다시 합치는 방법이다.

위 사진에서는 모든 리스트의 요소가 하나가 될 때까지 나누고 2와 7을 붙이기 위해 대소 비교를한다.
2가 더 작기 때문에 2다음에 7이 오게된다.

6과 9를 붙이기 위해 대소관계를 비교하면 6 다음 9가 오게된다.

이제 정렬된 2와 7 그리고 6과 9를 합쳐야한다.
2와 6을 비교한다 --> 2
6과 7을 비교한다 --> 6
7과 9를 비교한다 --> 9
이렇게 하면 리스트의 반이 2, 6, 7, 9로 정렬이 되었다.

동일하게 나머지 반을 수행하면 된다.

합병 정렬은 중복된 숫자의 순서가 유지되는 안정 정렬이다.
그리고 리스트를 나눠 다른 공간에 저장해야 하기 때문에 out-of-place 정렬이다.

리스트를 나눌 때마다 필요한 대소 비교의 횟수가 줄어들어 평균적인 시간 복잡도는 $O( nlogn)$이다.

// 정렬대상이 될 배열과, 배열의 복사본 생성
int[] array, temp; 

// 생성자
public mergeSort(int[] array) {
	this.array = array;
    
	// 빈 배열을 만들어 데이터가 정렬되면 이를 저장
	temp = new int[array.length];
    
    // 요소 나누기
	split(0, array.length - 1);
}

// 리스트가 1개 남을 때까지 나누기
priavte void split(int low, int high) {

	//low, high가 같으면 나누기 종료
	if (low == high) {
    	return;
	}
    
    // 둘로 나누기
    int mid = (high + low) / 2;
	split (low, mid)
	split (mid + 1, high)
    
    // 합치기
	merge (low, mid, high)
}

// 대소 비교 후 순서에 맞게 열거.
priavte void merge(int low, int mid, int high) {
	
	int i=low, j=mid+1, tempposn = low;
    
	// 나눈 리스트의 대소 비교와 정렬
	while (i <= mid && j <= high) {
		if (array [i] <= array [j]){
			temp[tempposn++] = array[i++];
		} else {
			temp[tempposn++] = array[j++];
        }    
	}
    
	// // i가 mid로 가고 j가 high로 갈 때까지 반복
	while (i <= mid) temp[tempposn++] = array[i++];
	while (j <= high) temp[tempposn++] = array[j++];
    
	// 원래 배열에 다시 복사
	for (tempposn = low; tempposn <= high; tempposn++) {
		array[tempposn] = temp[tempposn];
		}
}

---

퀵 정렬(Quicksort)

퀵 정렬은 중심점(Pivot Point)을 임의로 고른 후 이 중심점보다 작은 수를 한 쪽으로 분류하고 큰 수들은 다른 쪽으로 분류하여 정렬하는 방법이다.

Java의 sort 메소드에서 사용하는 정렬 알고리즘이며 모든 종류의 변수에 대해 사용 할 수 있다.

중심점의 왼쪽에 있는 숫자들은 오른쪽에 있는 숫자들과 비교할 필요가 없다.
즉 위 그림에서 중심점 6의 왼쪽에 있는 3,2 는 12, 8, 10, 7과 절대 비교하지 않는다.
3과 2끼리만 비교하면되고, 12, 8, 10, 7끼리만 비교하면 된다.
이들을 비교하기 위해선 중심점을 다시 정하고 정렬을 반복한다.

퀵 정렬의 순서를 정리하면 다음과 같다.

1. 중심점을 선택. 주로 리스트의 중간에 있는 숫자 혹은 마지막에 있는 숫자를 선택.
2. 마지막 요소와 중심점의 위치를 바꿔 중심점을 리스트의 가장 끝으로 보낸다.
3. 2개의 카운터를 사용하여 리스트의 처음부터 탐색. 첫 번째 카운터에는 중심점보다 큰 숫자의 위치를 저장하고 두 번째 카운터에는 현재 탐색하고 있는 위치를 저장.
4. 탐색하며 중심점보다 작은 숫자를 발견하면 첫 번째 카운터의 숫자 위치와 바꾼다.
5. 3, 4 과정을 반복하면 중심점보다 큰 수와 중심점보다 작은 수가 나눠진다.
6. 다시 중심점을 선택하여 2~5 과정을 반복하면 리스트가 정렬된다.

리스트를 분리하여 따로 비교하므로, 평균적인 경우에 시간 복잡도는 $O( nlogn)$이다.

퀵 정렬을 하는데 중심점의 숫자가 2인 경우를 생각해보자.

작은 숫자가 중심점이 되는 경우 모든 숫자와 대소 비교를 하고, 분류가 되지 않는 상황이 생갈 수 있다.
이런 최악의 케이스인 경우 시간 복잡도는 $O(n^2)$까지도 늘어날 수 있다.

public class QuickSort <E> {
	E[] array;
    
	// 제너릭 생성자
	public E[] sort(E[] array) {
    	
        // 제네릭 배열 생성
		this.array = array;
        
        // 제네릭 배열 정렬
		quicksort(0, array.length - 1);
		return array;
	}
    
	// 위치를 바꿔주는 함수
	public void swap(int from, int to) {
    	
        //임시 변수
		E tmp = array[from];
		array[from] = array[to];
		array[to] = tmp;
	}
    
	// 퀵 정렬
	public void quicksort(int from, int to) {
    
		// 정렬 종료 (요소가 한개인 경우)
		if (from >= to) {
        	return;
		}
        
        // 중심점(Pivot Point)으로 배열의 마지막에 있는 숫자를 선택.
		E value = array[to];
        
		// 중심점보다 큰 값을 가리키는 카운터, 가장 앞으로 지정
        // 중심점보다 큰 값중 가장 앞에 있는 값
		int counter = from;
        
		// 중심점의 바로 앞까지 탐색
		for (int i=from; i < to; i++) {
        
			// 중심점보다 작은 값을 발견하면 카운터와 위치 바꾸기.
			if (((Comparable<E>) array[i].compareTo(value) <= 0) {
				swap(i, counter);
                
                // 카운터위치를 옆으로 하나 이동
				counter++;
			}
		}
        
		// 중심점이 중간에 오게 한다. 
        // to가 중심점임. 
		swap(counter, to);
        
		// 배열의 왼쪽과 오른쪽을 정렬.
        // 카운터의 위치는 맞는 자리이므로 더 이상 옮길 필요가 없다.
		quicksort(from, counter - 1);
		quicksort(counter + 1, to);

}

---

기수 정렬(Radix)

기수 정렬(Radix)은 우편번호, 자릿수 등의 기준을 만들어 기준에 따라 숫자를 분류하여 정렬하는 방법이다.

예를 들어, 4자리 숫자를 일의 자리의 숫자, 십의 자리의 숫자, 백의 자리의 숫자, 천의 자리의 숫자에 따라 분류하여 정렬할 수 있습니다.
이럴 경우 시간 복잡도는 $4$n이 된다.

이론적으로 이 방법은 $n$ 의 복잡도를 갖는 빠른 정렬 방법이다.
하지만 실제로는 숫자를 복사하는 과정이 너무 많아 수행 속도가 느리다.
그래서 컴퓨터에서는 사용하기 어렵고 일상 생활에서 우편물을 정렬할 때와 같이 기계적으로 정렬할 때 많이 쓰인다.

---

각 정렬을 요약하자면 다음 그림과 같다.