quickSort

quickSort.java

/**
* 비순환 드라이버 method
* @param arr
*/
void quickSort(int[] arr) {
  quickSort(arr,0,arr.length);
}
	
/**
* 퀵 정렬
* @param arr 배열
* @param startIndex 시작 index
* @param last 처음에 배열의 길이를 입력 받고, -1 해서 마지막 인덱스로 사용됩니다. 
*/
void quickSort(int[] arr, int startIndex, int last) {
  if(last - startIndex < 2) return;
  int j = partition(arr, startIndex, last); 
  quickSort(arr, startIndex, j);
  quickSort(arr, j + 1, last);
}
	
/**
* pivot 보다 큰 원소를 우측으로 작은 원소를 좌측으로 보내면서 마지막에 pivot 의 위치를 찾고 반환
* @param arr
* @param startIndex
* @param last
* @return pivot 의 index 를 반환합니다. 
*/
int partition(int[] arr, int startIndex, int last) {

  int pivot = arr[startIndex]; // 맨 앞에 있는 원소를 pivot정한 경우입니다.
  int i = startIndex, j = last;
  while (i < j) {  // i == j 가 되면 loop 가 종료됩니다. 회전할때 마다 i가 증가되거나 j가 감소 됩니다.
    while (j > i && arr[--j] >= pivot) ; //empty loop, j는 pivot 이 될때까지 1을 선감소 
    if(j > i) arr[i] = arr[j]; // arr[j]는 arr[i]로 복사되고, 빈공간이되었다고 봅니다. 
    while (i < j && arr[++i] <= pivot) ; //empty loop, i는 pivot 이 될때까지 1을 선 증가
    if(i < j) arr[j] = arr[i]; // arr[i]는 arr[j]로 복사되고, 빈 공간이 되었다고 봅니다. 
  }
  arr[j] = pivot; // i == j 인 상태입니다. 
  return j;
}