정말 신기하게도 합병정렬 보단 이해하기가 쉬웠습니다.
뭔가 왼쪽, 오른쪽 따로 움직이는게 확실히 상상된다는 느낌이랄까 머리속에 그림도 그려지고
이거 역시 재귀를 쓰지않고 만들어보려 했는데 잘 안되네요. ㅠㅠ
재귀를 쓰지 않음으로써 오는 손해가 너무 큰듯하고 만들면 계속 스파게티화 되버려서....
시간은 합병정렬 보다 빠르긴 한데 때때로 삽입정렬보다 느릴때가 있어서 당황스럽습니다.
이론상으로는 합병정렬과 퀵정렬의 정렬시간이 거의 비슷해야 할텐데 말이죠.
public int[] quickSort(int[] array) {
long startTime = System.nanoTime();
Quick_Sort(array, 0 , array.length - 1);
long endTime = System.nanoTime();
System.out.println("QuickSort TIME : " + (endTime - startTime) / 1000.0 + "(ms)");
return array;
}
private int[] Quick_Sort(int[] array, int start, int end) {
int part = partition(array, start, end);
if(start < part - 1) {
Quick_Sort(array, start, part - 1);
}
if(part < end) {
Quick_Sort(array, part, end);
}
return array;
}
private int partition(int[]array, int start, int end) {
int pivot = array[(start + end) / 2];
int temp;
while(start <= end) {
while(array[start] < pivot) start++;
while(pivot < array[end]) end--;
if(start <= end) {
temp = array[start];
array[start] = array[end];
array[end] = temp;
start++; end--;
}
}
return start;
}
글쓰기