[20211021] 퀵 정렬

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]);
	}
}