QUICK SORT

최악의 퀵정렬이었음.
내가 머리가 나빠서 고생한 점도 있었지만, 책을 그대로 따라해도 퀵정렬이 안됐음!!

하도 안되서, 포기할까 하다가 혹시나 오타가 있지 않을까 한빛미디어 홈피가서 오탈자를 찾으니... 역시나 오탈자가 존재했음...

여하튼 좋은 경험 이었음...


문제점: 배열이 작으면 문제는 없으나, 배열이 커져 재귀함수가 늘어날수록 stack over flow의 위험성도 동시에 높아짐..

----------------------
package algorithm.sort.quick;

import algorithm.sort.Sort;

public class QuickSort extends Sort {

 public QuickSort(int[] arr) {
  super(arr);
 }

 protected void sort() {

  quickSort(0, arr.length - 1);
 }

 private void quickSort(int left, int right) {

  if (left < right) {

   int index = partition(left, right);   

   quickSort(left, index - 1);
   quickSort(index + 1, right);
  }
 }

 private int partition(int left, int right) {

  int first = left;
  int pivot = arr[first];

  ++left;

  while (left <= right) {

   while (arr[left] <= pivot && left < right) {
    ++left;
    increaseSearchTime();
   }

   while (arr[right] > pivot && left <= right) {
    --right;
    increaseSearchTime();
   }

   if (left < right) {
    swap(left, right);
   } else {
    break;
   }
  }

  swap(first, right);

  return right;
 }
}