[대학교 알고리즘] QuickSort

int Partition (int A[ ], int Left, int Right) {
/* 입력 : A[Left:Right] - 분할하려는 부분배열, A[Left] - 분할 원소,
  A[Right] - 더미 키.
출력 : A[Left:Right], Right - 분할 원소를 제자리에 위치시키고,
그 인덱스를 변수 Right에 담아서 복귀한다. */
int PartElem, Value;
PartElem = Left; // 분할 배열의 첫 번째 인덱스 복사.
Value = A[PartElem]; // 기준이 되는 인덱스의 값을 복사해서 비교값으로 사용한다 기준이지
do {
do { } while (A[++Left] < Value); // 첫값은 기준값이기 때문에 ++사용
do { } while (A[--Right] > Value); // 함수 입력받을때 +1로 원래 배열의 수보다 많이받아서 이것도 통일성을 위해 --사용
if (Left < Right) Swap(&A[Left], &A[Right]); // 위에서 두개 비교한 인덱스 값이 오른쪽이 더 크다면
else break; // 오른쪽에 작은값이 있고 왼쪽에 큰값이 있다는 것이다.
} while (1); // 둘이 같을수는 없고 Right이 더 작다면 정렬이 끝난 상태로 반복문 탈출
A[PartElem] = A[Right]; // 정렬이 끝난 그 기준값과 가운데 있는 값을 교환한다. 원래 Right값은 당연히 기준값보다 작다.
A[Right] = Value;
return Right; // 분할할때 중앙인덱스를 반환.

}
void QuickSort (int A[ ], int Left, int Right) {
/* 입력 : A[Left:Right+1] - 정렬할 배열, A[Right+1]은 배열 내의 최대값보다 큰 값.
   Left, Right - 배열 내의 정렬할 원소의 위치를 알리는 최소, 최대 인덱스.
출력 : A[Left:Right] - 정렬된 배열. A[Right+1]은 더미 키가 있는 곳.*/
int Middle;
if (Right > Left) { // Right가 Left보다 더 크다는건 정렬이 안끝났다는 말이다.
Middle = Partition(A[ ], Left, Right+1); // 반의 인덱스를 리턴받아서 새로운 Right값으로 사용. '
QuickSort(A[ ], Left, Middle-1); // 기준이 되는 인덱스는 최선의 값이기 때문에 제외하고 정렬
QuickSort(A[ ], Middle+1, Right); // 위와 마찬가지
} // 계속 반의 반의 반 이런식으로 하나가 남는다면 Right 와 Left가 같아진다. 그럼 반복문 종료 재귀함수 생각하면 편함.

}