package Day15;
import java.util.Scanner;
//퀵 정렬
public class QuickSort {
// 배열 요소 a[idx1]과 a[idx2]의 값을 바꾼다.
static void swap(int a[], int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
// 배열을 나눈다.
static void quickSort(int a[], int left, int right) {
int pl = left; // 왼쪽 커서
int pr = right; // 오른쪽 커서
int x = a[(pl + pr) / 2]; // 피벗(가운데 위치의 값)
System.out.printf("a[%d] ~ a[%d]: {", left, right);
for (int i = left; i < right; i++)
System.out.printf("%d, ", a[i]);
System.out.printf("%d}\n", a[right]);
do { // 배열 a를 피벗 x를 기준으로 나눈다.
while (a[pl] < x)
pl++; // 왼쪽으로 증가
while (a[pr] > x)
pr--; // 오른쪽으로 감소
if (pl <= pr)
swap(a, pl++, pr--);
} while (pl <= pr);
if (left < pr)
quickSort(a, left, pr); // 재귀 호출
if (pl < right)
quickSort(a, pl, right); // 재귀 호출
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.println("퀵정렬");
System.out.print("요소 수: ");
int nx = stdIn.nextInt();
int x[] = new int[nx];
for (int i = 0; i < nx; i++) {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
}
quickSort(x, 0, nx - 1);
System.out.println("오름차순으로 정렬했습니다.");
for (int i = 0; i < nx; i++)
System.out.println("x[" + i + "] = " + x[i]);
}
}