기본 정렬 알고리즘(Sorting Algorithm)

정렬 알고리즘(Sorting Algorithm)

개요

정렬 알고리즘은 데이터 요소의 집합을 일정한 순서로 배열하는 방법이다.
모든 상황에 최선의 결과를 도출하는 알고리즘은 없으며 알고리즘 선택 시 고려할 점은 아래와 같다

• 데이터의 양
• 키값들의 분포 상태
• 정렬에 필요한 기억공간의 크기
• 소요공간 및 작업시간
• 초기 데이터의 배열상태

실행 방법에 따른 분류

• 비교식 정렬(Comparative Sort) : 비교하고자 하는 각 키 값들을 한 번에 두 개씩 비교하여 교환하는 방식
  
  
• 분산식 정렬(Distribute Sort) : 키 값을 기준으로, 자료를 여러 개의 부분집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를 정렬하는 방식

정렬 장소에 따른 분류

• 내부 정렬(Internal Sort) : 정렬할 데이터를 메인 메모리에 올려서 정렬하는 방식
  
  
• 외부 정렬(External Sort) : 정렬할 데이터를 보조 기억장치에서 정렬하는 방식

해당 알고리즘들 중에 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬, 기수 정렬 을 알아보려고 한다.

버블 정렬 O(N²)

인접한 값과 비교하여 정렬하는 방식으로 끝의 값부터 정해짐

static int[] BubbleSort(int[] data) {
    int tmp;
    for(int i = 0; i < data.length - 1; i++) {
        for(int j = 0; j < data.length - 1 - i; j++) {
            if(data[j] > data[j + 1]) {
                tmp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = tmp;
            }
        }
    }
    return data;
}

선택 정렬 O(N²)

선택된 값과 나머지 값들을 비교하여 정렬하는 방식

static int[] SelectionSort(int[] data) {
	int min, tmp;
	for(int i = 0; i < data.length - 1; i++) {
		min = i;
		for(int j = i + 1; j < data.length; j++) {
			if(data[j] < data[min])
				min = j;
		}
		tmp = data[i];
        data[i] = data[min];
        data[min] = data[i];
	}
	return data;
}

삽입 정렬 O(N²)

데이터 집합을 순회하며 정렬이 필요한 요소를 뽑아내 적당한 곳으로 삽입하는 방식

static int[] InsertionSort(int[] data) {
	int key;
	int j;
	for(int i = 1; i < data.length; i++) {
		key = data[i];
		for(j = i - 1; j >= 0; j--) {
			if(data[j] > key)
				data[j + 1] = data[j];
			else
				break;
		}
		data[j + 1] = key;
	}
	return data;
}

병합 정렬 O(N logN)

둘 이상의 부분집합으로 나누고, 각 부분집합을 정렬한 후 부분집합들을 다시 정렬된 형태로 합치는 방식

// 메모리 낭비를 방지하기 위해 전역선언
static int[] tmp = new int[8];

// 병합 정렬 2-way
    static int[] MergeSort(int[] data, int L, int R) {
    	int middle;
 
    	if(L < R) {
    		middle = (L + R) / 2;
    		// divide
		data = MergeSort(data, L, middle);
		data = MergeSort(data, middle+1, R);
		// merge
		int p1 = L, p2 = middle + 1, p3 = L;
		while(p1 <= middle && p2 <= R) {
			if(data[p1] < data[p2])
				tmp[p3++] = data[p1++];
			else
				tmp[p3++] = data[p2++];
		}
		while(p1 <= middle)
			tmp[p3++] = data[p1++];
		while(p2 <= R)
			tmp[p3++] = data[p2++];
		for(int i = L; i <= R; i++)
			data[i] = tmp[i];
	}
	return data;
}

퀵 정렬 O(N logN)

데이터 집합 내 임의의 피봇값을 정하고 해당 피봇을 기준으로 피봇보다 작은 집합, 큰 집합으로 나누며, 더 이상 나눌 수 없을 때까지 재귀호출하는 방식

static int[] QuickSort(int[] data, int L, int R) {
	int left = L, right = R;
	int pivot = data[(left + right) / 2];
	do {
		while(data[left] < pivot)
			left++;
		while(data[right] > pivot)
			right--;
		if(left <= right) {
			int tmp = data[left];
			data[left] = data[right];
			data[right] = tmp;
			left++;
			right--;
		}
	} while(left <= right);
	
	if(L < right)
		data = QuickSort(data, L, right);
	if(left < R)
		data = QuickSort(data, left, R);
	
	return data;
}

힙 정렬 O(N logN)

트리 기반으로 최대 힙 트리(내림차순) 또는 최소 힙 트리(오름차순)를 구성해 정렬하는 방식

static int[] HeapSort(int[] data) {
	// 노드 교체시 필요한 size값 저장
	int size = data.length;
	
	// 데이터 크기만큼 반복
	for(int i = 0; i < size; ++i) {
		// Heapify :: 힙 상태 만들기
    	for(int j = 1; j < size; ++j) {
    		int child = j;
    		do {
    			int root = (child-1) / 2;
    			if(data[root] < data[child]) {
    				int tmp = data[root];
    				data[root] = data[child];
    				data[child] = tmp;
    			}
    			child = root;
    		} while(child != 0);
    	}
    	// Heap :: 루트(최상단 노드)와 최하단 노드 교체
    	int tmp = data[0];
    	data[0] = data[size-1];
    	data[size-1] = tmp;
    	// 맨 마지막 원소 제외하고 다시 힙 생성을 위해 size값 내림
    	--size;
	}
	return data;
}

기수 정렬 O(dN)

낮은 자리수부터 비교해가며 정렬하는 방식

static int[] RadixSort(int[] data) {
	Queue<Integer>[] bucket = new LinkedList[10];
	for(int i = 0; i < 10; ++i)
		bucket[i] = new LinkedList();
	
	int factor = 1;
	
	// d는 데이터의 자릿수를 의미함 (자릿수만큼 반복)
	for(int d = 0; d < 2; ++d) {
		for(int i = 0; i < data.length; ++i) {
			bucket[(data[i] / factor) % 10].add(data[i]);
		}
		for(int i = 0, j = 0; i < 10; ++i) {
			while(!bucket[i].isEmpty()) {
				// 큐의 맨 앞에있는 값 반환 후 삭제
				data[j++] = bucket[i].poll();
			}
		}
		factor *= 10;
	}
	return data;
}

간만에 배웠던걸 정리하려니까 머리가 터질 것 같다