티스토리 뷰
분할정복으로 행열을 쪼갤만큼 쪼갠다음 merge하면서 sort한다 항상 nlogn 하지만 일반적으로 quick sort가 빠름
출처 : http://yujuwon.tistory.com/entry/%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%ACMerge-Sort
예제 파일 : https://gist.github.com/yujuwon/5810996#file-gistfile1-c
import java.util.Arrays;
public class MeargeSort20160305 {
public static void main(String args[]) {
int[] arr = { 1, 3, 3, 4, 5, 2, 7 };
int[] temp = new int[arr.length];
mergeSort(arr, temp, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr, int[] temp, int l, int r) {
if (l < r) {
int mid = l + (r - l) / 2;
mergeSort(arr, temp, l, mid);
mergeSort(arr, temp, mid + 1, r);
// Copy both parts into the helper array
for (int i = l; i <= r; i++) {
temp[i] = arr[i];
}
int i = l;
int j = mid + 1;
int k = l;
// Copy the smallest values from either the left or the right side back
// to the original array
while (i <= mid && j <= r) {
if (temp[i] <= temp[j]) {
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
k++;
}
// Copy the rest of the left side of the array into the target array
while (i <= mid) {
arr[k] = temp[i];
k++;
i++;
}
}
}
}
'알고리즘' 카테고리의 다른 글
Merge Sort : Alalysis (0) | 2017.03.03 |
---|---|
BinaryTree (0) | 2016.02.07 |
QuickSort (0) | 2016.02.06 |
- Total
- Today
- Yesterday
- GC
- oops
- Kafka
- AWS
- CompressedOops
- OOP
- ranking
- authentication
- Dynamodb
- shenandoah
- Intermediate Certificate
- kerberos
- Consumer
- SSL
- JVM
- DESIGN
- Java
- Certificate Chain
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |