[Algorithm] 정렬 Sort - Merge sort, Quick sort

분할 정복법 

• 기본적으로 순환(recursion)을 통해 해결
• 문제 해결을 위해 아래 세 단계를 거침
• 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
• 정복 : 각각의 작은 문제들을 순환적으로 해결
• 합병 : 작은 문제의 해를 합하여 전체 문제의 해를 구함

---

Merge Sort (합병 정렬)

• 배열의 크기가 1이 될 때까지 분할 후 합병을 진행하며 정렬된 원래의 리스트 완성 (분할정복법)

구현

• 두 부분으로 나뉘어 정렬되어 있는 배열을 합쳐가며 정렬된 하나의 배열로 만드는 알고리즘

//이미 정렬된 인덱스가 p에서 q까지인 배열1과 q+1에서 r까지인 배열2를 합치면서 정렬하는 함수
private static void merge(int[] data, int p, int q, int r) {
	int i = p; //배열1의 시작 인덱스
	int j = q+1; //배열2의 시작 인덱스
	int k = p; //임시 배열의 시작 인덱스
	int[] temp = new int[data.length]; //원래 데이터가 저장된 배열과 크기가 같은 임시 배열
	while(i<=q && j<=r) { //한쪽 배열의 탐색이 모두 끝날때까지
		if(data[i]<=data[j]) //배열1의 요소가 더 작다면
			temp[k++] = data[i++]; //임시 배열에 삽입 후 인덱스 증가
		else
			temp[k++] = data[j++];
	}
	//탐색이 끝난 후 남은 데이터를 옮기는 과정
	while(i<=q) //배열1에 남은 데이터가 있는 경우
	temp[k++] = data[i++];
	while(j<=r) //배열2에 남은 데이터가 있는 경우
		temp[k++] = data[j++];
	for(int t=0; t<data.length; t++) //임시 배열의 값을 원래 배열로 옮김
		data[t] = temp[t];
}

 

실행 코드

public class Sort_mergeSort {
	private static int data[] = {2, 12, 8, 7, 5, 15, 10};

	//이미 정렬된 인덱스가 p에서 q까지인 배열1과 q+1에서 r까지인 배열2를 합치면서 정렬하는 함수
	private static void merge(int[] data, int left, int mid, int right) {
		int i = left; //배열1의 시작 인덱스
		int j = mid+1; //배열2의 시작 인덱스
		int k = left; //임시 배열의 시작 인덱스
		int[] temp = new int[data.length]; //원래 데이터가 저장된 배열과 크기가 같은 임시 배열

		while(i<=mid && j<=right) { //한쪽 배열의 탐색이 모두 끝날때까지 반복문 실행
			if(data[i]<=data[j]) //배열1의 요소가 더 작다면
				temp[k++] = data[i++]; //임시 배열에 삽입 후 인덱스 증가
			else
				temp[k++] = data[j++];
		}
		//탐색이 끝난 후 남은 데이터를 옮기는 과정
		while(i<=mid) //배열1에 남은 데이터가 있는 경우
			temp[k++] = data[i++];
		while(j<=right) //배열2에 남은 데이터가 있는 경우
			temp[k++] = data[j++];
		for(int t=left; t<=right; t++) //임시 배열의 값을 원래 배열로 옮김
			data[t] = temp[t];
	}
	
	private static void mergeSort(int[] data, int left, int right) {
		if(left<right) {
			int mid = (left+right)/2;
			mergeSort(data, left, mid);
			mergeSort(data, mid+1, right);
			merge(data, left, mid, right);
		}
	}
	
	public static void main(String[] argf) {
		mergeSort(data, 0, data.length-1);
		for(int a : data)
			System.out.print(a+" ");
	}
}

---

Quick Sort (빠른 정렬)

• pivot을 하나 선택하고, 전체 데이터를 pivot보다 작은 값과 큰 값으로 나눔 (분할)
• 나눠진 두 부분을 순환적으로 정렬 (정복)

구현

• pivot을 기준으로 배열을 두개의 부분 배열로 나누는 partition 함수 호출
• 이후, 나눠진 두개의 배열로 quickSort 함수를 순환적으로 호출하여 정렬 수행

quickSort(A[], p, r) { //p는 배열의 시작 인덱스, r은 배열의 마지막 인덱스
  base case;// p>=r일 때, 정렬할 데이터가 0개 또는 1개이므로 할 일 없음.
  if (p < r) then {
    q = partition(A, p, r);  //분할 함수 호출, q는 pivot의 위치
    quickSort(A, p, q-1); //왼쪽 부분 배열 정렬
    quickSort(A, q+1, r); //오른쪽 부분 배열 정렬
  }
}

 

실행 코드

• 배열의 가운데 값을 pivot으로 사용

public class Sort_quickSort {
	private static int data[] = {5, 11, 8, 4, 9, 13, 6, 2, 7};
	
	private static int partition(int[] data, int left, int right) {
		int pivot = data[(left+right)/2]; //pivot을 배열의 가운데 값으로 지정
		int low = left;
		int high = right;
		
		while(low<high) { //low와 high의 교차가 일어나지 않는 동안
			while(data[low]<pivot) //왼쪽에서 pivot보다 큰 데이터가 나올때까지 인덱스 증가 
				low++;
			while(data[high]>pivot) //오른쪽에서 pivot보다 작은 데이터가 나올때까지 인덱스 감소
				high--;
			if(low<high) { //위 두개의 반복문을 모두 빠져나왔다면 두 개의 값을 교환
				int temp = data[low];
				data[low] = data[high];
				data[high] = temp;
			}
		}
		return low; //pivot의 위치 반환
	}
	
	private static void quickSort(int[] data, int left, int right) {
		if(left<right) { //정렬할 데이터가 2개 이상이면
			int p = partition(data, left, right); //partition 함수를 호출하여 pivot을 기준으로 리스트를 분할
			//pivot을 제외한 두 부분을 대상으로 quickSort를 순환 호출
			quickSort(data, left, p-1); //왼쪽 리스트 정렬 
			quickSort(data, p+1, right); //오른쪽 리스트 정렬
		}
	}
	
	public static void main(String[] args) {
		quickSort(data, 0, data.length-1);
		for(int a : data) {
			System.out.print(a + " ");
		}
	}
}