요즘 멍청이가 된 듯 하여 뜨문뜨문 시작하는 자료구조 시리즈...
버블, 머지, 퀵 소트를 한번에 쭉 찍어 보고 비교를 해 보자.
[ Sort.java ]
package com.kei;
public class Sort {
static int loopCount;
public static void main(String[] args) {
Sort sort = new Sort();
int sourceArray[] = {5, 7, 2, 3, 8, 4, 1, 6};
int workArray[];
sort.printArray(sourceArray, true);
loopCount = 0;
workArray = sourceArray.clone();
sort.bubbleSort(workArray);
System.out.print("Bubble Sort[" + loopCount + "] : ");
sort.printArray(workArray, true);
System.out.println();
sort.printArray(sourceArray, true);
loopCount = 0;
workArray = sourceArray.clone();
int tempArray[] = new int[sourceArray.length];
sort.mergeSort(workArray, tempArray, 0, workArray.length - 1);
System.out.print("Merge Sort[" + loopCount + "] : ");
sort.printArray(workArray, true);
System.out.println();
sort.printArray(sourceArray, true);
loopCount = 0;
workArray = sourceArray.clone();
sort.quickSort(workArray, 0, workArray.length - 1);
System.out.print("Quick Sort[" + loopCount + "] : ");
sort.printArray(workArray, true);
System.out.println();
}
// Bubble Sort ------------------------------------------------
// i 와 i + 1 을 비교해서 교환한다.
private void bubbleSort(int[] getArray) {
int tempData;
for(int x = 0 ; x < getArray.length ; x++) {
loopCount++;
for(int i = 0 ; i < getArray.length - 1 ; i++) {
loopCount++;
if(getArray[i] > getArray[i + 1]) {
tempData = getArray[i];
getArray[i] = getArray[i + 1];
getArray[i + 1] = tempData;
System.out.print("> "); printArray(getArray, true);
}
}
}
}
// ------------------------------------------------------------
// Merge Sort -------------------------------------------------
// 최소단위로 분할 정렬한 후 다시 병합 정렬한다.
private void mergeSort(int[] getArray, int[] tempArray, int start, int end) {
loopCount++;
if (start < end) {
int mid = (start + end) / 2;
mergeSort(getArray, tempArray, start, mid); // 좌측 처리, 최소 단위가 될 때까지 end값에 mid를 넣어서 호출 된다.
mergeSort(getArray, tempArray, mid + 1, end); // 우측 처리, 최소 단위가 될 때까지 start값에 mid를 넣어서 호출 된다.
int startPoint = start;
int midPoint = mid + 1;
int tempIdx = startPoint;
while (startPoint <= mid || midPoint <= end) {
loopCount++;
if (midPoint > end || (startPoint <= mid && getArray[startPoint] < getArray[midPoint])){
tempArray[tempIdx++] = getArray[startPoint++];
} else {
tempArray[tempIdx++] = getArray[midPoint++];
}
}
for (int i = start ; i <= end ; i++) {
getArray[i] = tempArray[i];
}
System.out.print(start + "/" + end + "> "); printArray(getArray, false);
System.out.print("| "); printArray(tempArray, false);
System.out.println();
}
}
// ------------------------------------------------------------
// Quick Sort -------------------------------------------------
// 피봇값을 지정하고 좌, 우 값과 비교한 후 교환한다.
private void quickSort(int[] getArray, int left, int right) {
if(left < right) {
loopCount++;
int index = partition(getArray, left, right);
quickSort(getArray, left, index - 1);
quickSort(getArray, index + 1, right);
}
}
private int partition(int[] getArray, int left, int right) {
int midIndex = (left + right) / 2;
int pivotValue = getArray[midIndex];
int tempData;
while(left < right) {
loopCount++;
while((getArray[left] < pivotValue) && (left < right)) {
loopCount++;
left++;
}
while((getArray[right] > pivotValue) && (left < right)) {
loopCount++;
right--;
}
if(left < right) {
//System.out.print("> " + pivotValue + "/" + getArray[left] + "(" + left +")/" + getArray[right] + "(" + right + ") : ");
tempData = getArray[left];
getArray[left] = getArray[right];
getArray[right] = tempData;
System.out.print("> "); printArray(getArray, true);
}
}
//System.out.println("-------------1 " + pivotValue + " / " + left + " / " + right);
return left;
}
// ------------------------------------------------------------
private void printArray(int[] getArray, boolean lf) {
for(int i : getArray) {
System.out.print(i + " ");
}
if (lf) {
System.out.println();
}
}
}
실행하면 결과는 아래와 같이 찍힌다.
5 7 2 3 8 4 1 6
> 5 2 7 3 8 4 1 6
> 5 2 3 7 8 4 1 6
> 5 2 3 7 4 8 1 6
> 5 2 3 7 4 1 8 6
> 5 2 3 7 4 1 6 8
> 2 5 3 7 4 1 6 8
> 2 3 5 7 4 1 6 8
> 2 3 5 4 7 1 6 8
> 2 3 5 4 1 7 6 8
> 2 3 5 4 1 6 7 8
> 2 3 4 5 1 6 7 8
> 2 3 4 1 5 6 7 8
> 2 3 1 4 5 6 7 8
> 2 1 3 4 5 6 7 8
> 1 2 3 4 5 6 7 8
Bubble Sort[64] : 1 2 3 4 5 6 7 8
5 7 2 3 8 4 1 6
0/1> 5 7 2 3 8 4 1 6 | 5 7 0 0 0 0 0 0
2/3> 5 7 2 3 8 4 1 6 | 5 7 2 3 0 0 0 0
0/3> 2 3 5 7 8 4 1 6 | 2 3 5 7 0 0 0 0
4/5> 2 3 5 7 4 8 1 6 | 2 3 5 7 4 8 0 0
6/7> 2 3 5 7 4 8 1 6 | 2 3 5 7 4 8 1 6
4/7> 2 3 5 7 1 4 6 8 | 2 3 5 7 1 4 6 8
0/7> 1 2 3 4 5 6 7 8 | 1 2 3 4 5 6 7 8
Merge Sort[39] : 1 2 3 4 5 6 7 8
5 7 2 3 8 4 1 6
> 1 7 2 3 8 4 5 6
> 1 3 2 7 8 4 5 6
> 1 2 3 7 8 4 5 6
> 1 2 3 4 8 7 5 6
> 1 2 3 4 6 7 5 8
> 1 2 3 4 6 5 7 8
> 1 2 3 4 5 6 7 8
Quick Sort[33] : 1 2 3 4 5 6 7 8
각 알고리즘의 시간복잡도를 찍어 봤는데... 카운터 위치가 이게 맞는 건지 모르겠다 -_-
왠지 아닌거 같아서 몹시 부끄러운건 기분 탓...
댓글