자바로 작성하는 정렬

1. 들어가기 앞서

코테를 준비하다보면 정렬 문제도 심심치 않게 나오는 것을 볼 수 있다. 단순히 Arrays.sort()을 사용하거나 Collections.sort()을 사용할 수 있지만, 직접 구현도 할 줄 알아야 된다는 생각에 흔히 사용하는 모든 정렬을 구현해 보고자 한다. 물론 C++로 작성하는게 좀 더 이상적일 수 있지만(낭만의 언어) 지금은 java를 주력으로 하기 때문에 java로 작성하고자 한다.
정렬을 구현하기 앞서서 swap하는 코드 하나만 작성하고 가자.

void swap(int[] arr,int idx1,int idx2) {
	int tmp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = tmp;
}

참고로 Arrays.sort() 와 Collection.sort()는 보통 TimSort를 사용한다고 하는데 MergeSort와 SelectionSort을 결합한 정렬이라고 한다. 본 포스팅에서 정리하지는 않는다.

2. 정렬 구현

2.1 버블 정렬

아주 기초적인 정렬이다. 보통 처음 정렬을 배울 때 배우는 정렬이고, 구현하기 쉽지만 성능이 안 좋다. 무조건 시간 복잡도는 O(n^2)이다.

void bubblesort(int[] arr) {
		for(int i=0;i<arr.length-1;i++) {
			for(int j=0;j<arr.length-1-i;j++) {
				if(arr[j] > arr[j+1])
					swap(arr,j,j+1);
			}
		}
	}

2.2 선택 정렬

리스트안에 여러 개의 원소가 있다고 할 때 가장 작은 것을 구해서 맨 앞에 배치한다. 그 다음은 맨 앞을 제외한 나머지 원소들 중에서 최소 값을 찾아 2번째에 배치한다.. 이 과정을 반복한다. 역시 시간 복잡도는 O(n^2) 이다.

void selectionSort(int[] arr) {
		for(int i=0;i<arr.length-1;i++) {
			int minIdx = i;
			for(int j=i+1;j<arr.length;j++) {
				if(arr[j] < arr[minIdx]) {
					minIdx = j;
				}
			}
			swap(arr,i,minIdx);
		}
	}

2.3 삽입 정렬

삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞에 데이터는 이미 정렬되었다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.

static void insertionSort(int[] arr) {
		for(int i=1;i<arr.length;i++) {
			for(int j=i;j>=1;j--) {
				if(arr[j-1] > arr[j]) {
					swap(arr,j-1,j);
				}
			}
		}
	}

시간 복잡도는 O(n^2) 이지만 정렬이 많이 되어 있다고 가정하면 O(n) 까지도 가능하다. 이상적인 경우 퀵 정렬 보다 빠를 수 있음.

2.4 퀵 정렬

피벗을 설정하는 정렬 방법이다. 피벗을 설정하는 방식 중 호어 분할 방식을 기준으로 퀵 정렬을 살펴 본다.

호어 분할 방식은 '리스트에서 첫 번째 데이터를 피벗으로 정하는 방식'이다.

이렇게 피벗을 설정하고 왼쪽부터 피벗보다 큰 데이터를 찾고, 오른쪽으로 부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 바꾼다. 이를 반복한다.

조금 복잡하니 그림과 설명을 함께 살펴보자.

step 0: 리스트의 첫 번째 데이터 ‘5’를 피벗으로 설정한다. 이후 왼쪽에서부터 ‘5’보다 큰 데이터 ‘7’을 선택하고 오른쪽에서부터 ‘5’보다 작은 데이터를 ‘4’를 선택하여, 두 데이터의 위치를 서로 변경한다.

step 1: 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. ‘9’와 ‘2’가 선택되고, 두 값의 위치를 서로 변경한다.

step 2: 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. 이때 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린다. 이렇게 두 값이 엇갈린 경우 ‘작은 데이터’와 ‘피벗’의 위치를 서로 변경한다. 즉, ‘1’과 피벗인 ‘5’의 위치를 서로 변경하여 분할을 수행한다.

step 3(분할 완료): ‘5’의 왼쪽에 있는 데이터는 모두 ‘5’보다 작고, 오른쪽에 있는 데이터는 모두 ‘5’보다 크다. 이렇게 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 ‘분할’ 혹시 ‘파티션’이라고 한다.

다음에는 피벗의 오른쪽과 왼쪽에 대해서 다시 퀵정렬을 진행한다.

static void quickSort(int[] arr,int start,int end) {
		if(start >= end)
			return;
		int pivot = start;
		int left = start+1;
		int right = end;
		
		while(left<=right) {
			// 피벗 왼쪽부터
			while(left <= end && arr[left] < arr[pivot]) 
				left++;
			// 피벗 오른쪽
			while(right > start && arr[right] > arr[pivot])
				right--;
			// 엇갈리지 않은 경우
			if(left <= right) {
				swap(arr,left,right);
			} else {
				swap(arr,pivot,right);
			}
			
			// 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
			quickSort(arr,start,right-1);
			quickSort(arr,right+1,end);
		}
	}

pivot을 정하는 방법에 따라서 성능이 달라진다.

• 시간 복잡도 : 평균 O(nlogn), 최악 O(n^2)

2.5 계수 정렬

특수한 상황에서 사용 가능하다.

static void countSort(int[] arr) {
		int[] count = new int[20000];
		for(int i=0;i<arr.length;i++) {
			count[arr[i] + 10000]++;
		}
		for(int i=0;i<count.length;i++) {
			for(int j=0;j<count[i];j++) {
				System.out.print(i-10000 + " ");
			}
		}
	}

다음 코드도 내가 new int[20000]으로 설정했는데 이는 -10000~10000 사이에 해당하는 값을 정렬할 때만 사용 가능하다. (엄밀히 하면 20001로 설정해야함) 속도는 아주 빠르다는 장점이 있지만 메모리를 아주 많이 잡아먹는다는 단점이 존재하는데, 극단적으로 [-100000000,100000000] 을 정렬하려면 int[200000001] 배열을 선언해야한다.

• 시간 복잡도 : O(n)

2.6 합병 정렬 (mergeSort)

개인적으로 코드를 작성하는데 애를 좀 먹은 합병 정렬이다.

static void mergeSort(int[] arr,int start,int end) {
		if(start < end) {
			int mid = start + (end-start) /2;
			mergeSort(arr,start,mid);
			mergeSort(arr,mid+1,end);
			merge(arr,start,mid,end);
		}
	}
	
	// 분할된 두 리스트를 합쳐서 하나의 리스트를 반환한다.
static void merge(int[] arr,int start,int mid,int end) {
		int[] sorted = new int[arr.length];
		
		int l = start;
		int r = mid+1;
		int idx = start; //sorted에 넣어줄 인덱스
		
		while(l<=mid && r<=end) {
			if(arr[l] < arr[r]) sorted[idx++] = arr[l++];
			else sorted[idx++] = arr[r++];
		}
		
		while(l<=mid) sorted[idx++] = arr[l++];
		while(r<=end) sorted[idx++] = arr[r++];
		
		while(--idx >= start) {
			arr[idx] = sorted[idx];
		}
	}

코드를 2부분으로 나누어 작성했다. 분할(mergeSort)과 합병(merge)으로 나누었다.
여기서 한 가지 포인트는
int mid = start + (end-start) /2; 이다.

정수 오버플로우를 방지하기 위함이다. 단순히 (start+end)/2 하는 것에 비해 오버플로우가 발생하지 않게 방지할 수 있다.

mergeSort 코드를 먼저 보자.

if(start < end) {
	int mid = start + (end-start) /2;
	mergeSort(arr,start,mid);
	mergeSort(arr,mid+1,end);
	merge(arr,start,mid,end);
}

mid를 선언해서 배열을 반으로 갈라준다.
(start=0, mid=0, end=1일 때 까지 반복한다.)
어렵지 않으니 이정도로만 정리하자.

이제 merge 코드를 보자.

int[] sorted = new int[arr.length];

sorted 배열을 선언해서 정렬된 결과를 저장한다. 정렬을 하고 나면 arr 배열에 옮긴다.

int l = start;
int r = mid+1;
int idx = start; //sorted에 넣어줄 인덱스

l는 왼쪽 블록의 첫번째 인덱스를 의미하고,
r 는 오른쪽 블록의 첫번째 인덱스를 의미한다.

while(l<=mid && r<=end) {
		if(arr[l] < arr[r]) sorted[idx++] = arr[l++];
		else sorted[idx++] = arr[r++];
}

다음 코드에서 왼쪽 블록과 오른쪽 블록을 비교해서 크기 순서대로 sorted 배열에 넣는다. 하지만 이 과정만으로는 왼쪽 블록과 오른쪽 블록의 모든 값을 sorted에 넣지 못한다! 그래서 아래 과정이 반드시 필요하다.
4.

while(l<=mid) sorted[idx++] = arr[l++];
while(r<=end) sorted[idx++] = arr[r++];
		
while(--idx >= start) {
	arr[idx] = sorted[idx];
}

그래서 위 while문은 왼쪽, 오른쪽 블록 중 어느 하나가 전부 삽입되어 더 이상 정렬이 필요없는 경우이다.
그리고 마지막 while문을 이용해서 arr 배열에 넣어준다.

• 시간 복잡도 : O(nlogn)

3. 마무리하면서

정렬 코드를 하나하나 작성해보면서 원리를 기억하면 코드를 자연스레 작성할 수 있다는 것을 알았다. 자주 보면서 익숙해지도록 노력해야겠다.