퀵 정렬이란? 퀵 정렬은 이름대로 가장 빠른 정렬 알고리즘 중 하나이다.
1959년 토니 호어(Sir Tony Hoare, 본명은 Charles Antony Richard Hoare 인데 왜 Tony인지는 모르겠다)가 제안한 정렬 방법으로 일반적이고 폭넓게 사용되는 아주 빠른 정렬 알고리즘이다.
퀵 정렬의 시간복잡도는 O(n log n)으로 알려져 있다. 다만 배열의 초기값이나 피벗(아래서 배움)선택 방법에따라 복잡도가 오를 수 있다.
최악의 경우 O(n^2)이 된다.
또 퀵 정렬은 요솟수가 적은 배열을 처리할 땐 그다지 효율적이지 않은데 요솟수의 길이를 미리 파악해 퀵 정렬 - 단순 삽입 정렬 사이에 선택할 수 있으면 더욱 효율적이겠다.
퀵 정렬 살펴보기
int[] arr = {175,170,160,168,165,170,155,150};위 배열은 학생 8명의 키를 담은 배열이며 퀵 정렬로 정렬하는 과정을 알아보자.
먼저 어느 한 사람의 키를 선택한다. 키가 168cm인 학생 A를 선택하고 그 학생을 기준으로 A의 키보다 작은 사람의 그룹가 큰 사람의 그룹으로 나눠보자. 이때 학생 A(그룹을 나누는 기준)를 피벗(pivot)이라 칭한다. 퀵 정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1명이 되면 정렬을 마친다.
{175,170,160,168,165,170,155,150}
키가 168미만 키가 168이상
{160,165,155,150} {175,170,168,170}
155이하 155초과 170이하 170이상
{155,150} {160,165} {170,168} {170,175}
{150,155,160,165,168,170,170,175}배열을 두 그룹으로 나누기
퀵 정렬 알고리즘은 먼저 배열을 두 그룹으로 나눠야 한다. 다음 배열에서 피벗으로 6을 선택하여 시작 요소의 인덱스를 pl, 배열의 끝 요소의 인덱스를 pr커서라고 해 보자.
│ 5 │ 7 │ 1 │ 4 │ 6 │ 2 │ 3 │ 9 │ 8 │
pl pivot pr그룹을 나누기 위해서는 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이상의 요소를 배열 오른쪽으로 옮겨야 한다.
- a[pl] >= pivot이 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔한다.
- a[pr] <= pivot이 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔한다.
위의 과정을 거치면 pl과 pr은 다음 위치에서 멈추게 된다.
│ 5 │ 7 │ 1 │ 4 │ 6 │ 2 │ 3 │ 9 │ 8 │
pl pivot pr이 상태에서 pl과 pr의 위치에 있는 요소들을 교환한다. 그러면 피벗 이하 값은 왼쪽으로, 이상값은 오른쪽으로 이동하게 된다. 다시 스캔을 계속하면 pl,pr커서는 다음 위치에서 멈추게 된다.
│ 5 │ 3 │ 1 │ 4 │ 6 │ 2 │ 7 │ 9 │ 8 │
pl pr이렇게 다시 멈췄을 때 pl과 pr위치의 요소를 교환한다.
다시 스캔을 실행하면 pl과 pr의 위치가 교차된다.
│ 5 │ 3 │ 1 │ 4 │ 2 │ 6 │ 7 │ 9 │ 8 │
pr pl이 상태가 그룹을 나누는 과정이 끝나는 조건이다. 배열은 다음처럼 두 그룹으로 나누어진다.
- 피벗 이하의 그룹: a[0], ... ,a[pl-1]
- 피벗 이상의 그룹: a[pr+1], ... , a[n-1]
또, 그룹을 나누는 작업이 끝난 후 pl > pr + 1이면 다음과 같은 그룹이 생길 수 있다.
- 피벗과 같은 값을 갖는 그룹: a[pr+1], ... , a[pl-1]
(위 배열에는 존재하지 않는 경우임)
아래 배열에서는 존재할 수 있는 경우이다.
│ 1 │ 8 │ 7 │ 4 │ 5 │ 2 │ 6 │ 3 │ 9 │
pl pivot pr
│ 1 │ 8 │ 7 │ 4 │ 5 │ 2 │ 6 │ 3 │ 9 │
pl pr
pl,pr을 교환
│ 1 │ 3 │ 7 │ 4 │ 5 │ 2 │ 6 │ 8 │ 9 │
pl pr
pl,pr을 교환
│ 1 │ 3 │ 2 │ 4 │ 5 │ 7 │ 6 │ 8 │ 9 │
pl
pr
│ 1 │ 3 │ 2 │ 4 │ 5 │ 7 │ 6 │ 8 │ 9 │
pr pl
{1,3,2,4,5} { 5 } {5,7,6,8,9}
왼쪽그룹 가운데그룹 오른쪽그룹위 경우, pl은 7다음 조건에 부합하는 경우가 pivot인 5에 커서가 가는것,
pr도 2 다음 조건에 부합하는 경우가 pivot인 5에 커서가 가는것. 따라서 둘이 겹치게 된다.
이때 동일한 요소를 교환하게 된다. 동일한 요소를 교환하는일은 아무런 의미가 없지만 발생할 경우가 고작 한 번이기 때문에 무시해도 된다.
이를 줄이기 위해 조건문을 추가하는 비용이 한번 교환하는 비용보다 더 크다.
그룹 나누기 예제
public class Partition {
// 배열 요소 교환
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
// 배열 나누기
static void partition(int[] a) {
int lng = a.length;
int pl = 0;
int pr = lng - 1;
int x = a[lng / 2]; // pivot
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr)
swap(a, pl++, pr--);
} while (pl <= pr);
System.out.println("피벗값은 " + x + "입니다.");
System.out.println("피벗 이하의 그룹");
for (int i = 0; i <= pl - 1; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
if (pl > pr + 1) {
System.out.println("피벗과 같은 그룹");
for (int i = pr + 1; i <= pl - 1; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
System.out.println("피벗 이상의 그룹");
for (int i = pr + 1; i < lng; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수 : ");
int[] x = new int[sc.nextInt()];
for (int i = 0; i < x.length; i ++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
partition(x);
}
}배열의 가운데 있는 요소를 피벗으로 정하고 그룹으로 나누는 코드입니다.
만약 pl,pr이 피벗과 동시에 일치하는 '가운데 그룹'이 있는 경우는 해당 경우도 출력됩니다.
※ 여기서의 피벗값 설정은 바람직한 방법이 아닙니다. 피벗값이 성능을 좌우합니다.
퀵 정렬 구현하기
앞에서는 배열을 피벗 기준으로 나누기만 했다. 이 방법을 좀 더 발전시키면 퀵 정렬 알고리즘이 완성된다.
아래 배열에서 피벗:6으로 지정하여 퀵정렬을 알아보자.
│ 5 │ 8 │ 4 │ 2 │ 6 │ 1 │ 3 │ 9 │ 7 │
↓ 나눔
│ 5 │ 3 │ 4 │ 2 │ 1 │ 6 │ 8 │ 9 │ 7 │
pr pl
│ 5 │ 3 │ 4 │ 2 │ 1 │ │ 6 │ 8 │ 9 │ 7 │
↓ 나눔 ↓ 나눔
│ 1 │ 3 │ 2 │ 4 │ 5 │ │ 6 │ 7 │ 9 │ 8 │
pr pl pr pl
... 생략 ...생략처음 길이9의 배열을 2개의 그룹으로 나누고, 2개의 그룹을 또 4개의 그룹으로 나누고,, 이런식으로 그룹의 요소가 1개가 될 때까지 그룹을 나눈다.
요솟수가 1인 그룹은 더이상 그룹을 나눌 필요가 없기에 요솟수가 2개 이상인 그룹만 나누면 된다. 따라서 다음처럼 배열을 반복해서 나누게 된다.
- pr이 맨 앞보다 오른쪽에 있으면(left < pr) 왼쪽 그룹을 나눕니다.
- pl이 맨 뒤보다 앞쪽에 있으면(pl < right) 오른쪽 그룹을 나눕니다.
- 가운데 그룹이 생기는 경우는 어차피 요솟수가 1이기에 나눌 대상x
퀵 정렬은 8퀸 문제와 마찬가지로 분할 정복 알고리즘이기에 재귀 호출을 사용해 간결하게 구현할 수 있다. 아래 코드의 quickSort()는 배열a 나눌구간의 맨 앞 요소(left), 맨 뒤 요소(right)의 인덱스를 매개변수로 받는다.
public class Quick {
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 {
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 sc = new Scanner(System.in);
System.out.print("요솟수 : ");
int[] x = new int[sc.nextInt()];
for (int i = 0; i < x.length; i ++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
quickSort(x, 0, x.length-1);
for (int i = 0; i < x.length; i++) {
System.out.println("x[" + i + "]=" + x[i]);
}
}
}위의 partition클래스 코드에서 재귀함수를 추가하고, 메서드가 호출 될 때마다 어디 부분을 작업중인지 볼 수 있게 바꾸었다.
하지만 '퀵'정렬인데 재귀함수가 들어가면 여러모로 성능이 안좋아질 수 있다.
- 함수 호출 오버헤드로 인해 각 호출마다 오버헤드가 발생, 스택 프레임을 생성하고 파라미터를 전달하는데 필요한 시간으로 재귀함수에 존재하는 성능 하락 요인
- 재귀함수는 각 호출마다 스택 메모리를 사용해야 하기에 재귀가 깊어지면 메모리 사용량이 증가하고 배열이 큰 경우 StackOverFlow가 발생할 가능성도 있음 또한 성능 하락 요인임.
비재귀적인 퀵 정렬 구현하기
물론 모든 코드가 비재귀적으로 작성하여 성능을 올려야 한다는 의미는 아니다. 재귀함수는 가독성이 뛰어나 코드를 유지/보수하기 편리하다는 장점이 있으나 적어도 매우 자주 사용할 수 있고 성능이 극대화 돼야 하는 코드에서는 비재귀적인 함수를 구현하는것이 좋다고 생각한다. 필요하다면 재귀함수 코드를 문서화 해서 설명하는것도 하나의 방법이라 생각한다.
퀵 정렬을 비재귀적으로 수정하기 위해서는 스택을 활용해야 한다.
아래는 int형 배열을 활용한 스택이므로 활용하도록 해 보자.
public class IntStack {
private int[] stk; // 스택 배열
private int capacity; // 스택 용량
private int ptr; // 스택 포인터
// 실행 시 예외: 스택이 비었음
public class EmptyIntStackException extends RuntimeException {
public EmptyIntStackException() {
}
}
// 실행 시 예외: 스택 가득 참
public class OverflowIntStackException extends RuntimeException {
public OverflowIntStackException() {
}
}
public IntStack(int maxlen) {
ptr = 0;
capacity = maxlen;
try {
stk = new int[capacity];
} catch (OutOfMemoryError e) {
capacity = 0;
}
}
public int push(int x) throws OverflowIntStackException {
if (ptr >= capacity)
throw new OverflowIntStackException();
return stk[ptr++] = x;
}
public int pop() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[--ptr];
}
public int peek() throws EmptyIntStackException {
if (ptr <= 0)
throw new EmptyIntStackException();
return stk[ptr - 1];
}
public void clear() {
ptr = 0;
}
public int indexOf(int x) {
for (int i = ptr - 1; i >= 0; i--)
if(stk[i] == x)
return i;
return -1;
}
public int getCapacity() {
return capacity;
}
public int size() {
return ptr;
}
public boolean isEmpty() {
return ptr <= 0;
}
public boolean isFull() {
return ptr >= capacity;
}
public void dump() {
if (ptr <= 0)
System.out.println("스택이 비어 있습니다.");
else {
for (int i = 0; i < ptr; i++)
System.out.print(stk[i] + " ");
System.out.println();
}
}
}위의 IntStack 클래스를 스택으로 활용하여 quickSort() 메서드를 아래처럼 고쳐주면 된다.
static void quickSort(int[] a, int left, int right) {
IntStack lstack = new IntStack(right - left + 1);
IntStack rstack = new IntStack(right - left + 1);
lstack.push(left);
rstack.push(right);
while(!lstack.isEmpty()) {
int pl = left = lstack.pop();
int pr = right = rstack.pop();
int x = a[(left + right) / 2]; // PivotValue
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr)
swap(a, pl++, pr--);
} while (pl <= pr);
if (left < pr) {
lstack.push(left); // 왼쪽 그룹 범위의
rstack.push(pr); // 인덱스를 푸시
}
if (pl < right) {
lstack.push(pl); // 오른쪽 그룹 범위의
rstack.push(right); // 인덱스를 푸시
}
}
}데이터를 일시적으로 저장하기 위해 '스택'을 활용한다.
quickSort메서드는 다음 2개의 스택을 사용한다.
- lstack ... 나눌 범위의 왼쪽 끝(맨 앞) 요소의 인덱스를 저장하는 스택.
- rstack ... 나눌 범위의 오른쪽 끝(맨 뒤) 요소의 인덱스를 저장하는 스택.
두 스택의 크기는 right-left+1이다(나눌 배열의 요솟수).
코드 해석
※ 아래 코드는 주석을 사용안하여 복/붙 사용 시 오류 발생
lstack.push(left); ───────┐
rstack.push(right); ───────(과정 1)
while (!lstack.isEmpty()) {
int pl = left = lstack.pop(); //─────┐
int pr = right = rstack.pop(); //─────(과정 2)
// 나누는 과정 생략
if (left < pr) { ──────────────────┐
lstack.push(left); │
rstack.push(pr); │
} │
if (pl < right) { ┝━━━(과정 3)
lstack.push(pl); │
rstack.push(right); │
} ──────────────────────────────────┘
}이렇게 과정 1,2,3으로 나누어 배열 {5,8,4,2,6,1,3,9,7}을 정렬하는 과정을 살펴보자
과정 1. lstack에 left를 rstack에 rigth를 푸시한다. 스택에 푸시한 값은 나눌 배열의 '첫 요소'와 '끝 요소'들의 '인덱스'이다. 9자리 배열을 예로 사용하면 lstack에 0을, rstack에 8을 푸시하게 된다.
다음에 이어지는 while문은 스택이 비어 있지 않으면 처리를 반복한다. 이때 스택에 들어있는 것은 분할할 배열이 없다는 것이다 → 정렬이 끝났다
과정 2. lstack에서 팝한 값을 left와 pl에 대입, rstack은 right와 pr에 대입한다. 1번째반복에서는 pl,left = 0, pr.right = 8이되어 0~8사이를 pivot을 구해 정렬한다.
과정 3. 첫 번째 if문에서 lstack과 rstack에 각각 0과 4를 푸시하고, 두 번째 if문에서 5와 8을 푸시한다.
과정 2. lstack에서 5가 팝돼 pl,left = 5가 되고 rstack에서는 8이 팝돼 pr,right = 8이 된 상태로 a[5 ~ 8] 부분을 정렬한다.
과정 3. 첫 번째 if문에서 lstack에 5, rstack에6을 푸시, 두 번째 if문에서 lstack에 7, rstack에8을 푸시한다.
7,8부분 정렬이 끝나고 5,6부분 정렬을 실시한 다음 비로소 제일 처음 넣었던 a[0 ~ 4]를 정렬한다. 나머지 과정은 a[5 ~ 8]부분이랑 똑같이 진행된다.
스택의 크기 구하기
위 코드에서의 스택의 크기는 배열의 요솟수로 초기화한다.
코드 해석에서 9의 크기를 갖는 스택이 생성되나, 최대로 사용된 스택은 3칸이었다.({7,8}{5,6}{0,4}일 때)
그러면 스택의 용량은 어느 정도의 크기여야 할까?
스택에 푸시하는 순서는 2가지 방법으로 수행할 수 있다.
방법1. 요솟수가 많은 그룹을 먼저 푸시한다.
방법2. 요솟수가 적은 그룹을 먼저 푸시한다.
배열 {6,5,4,2,7,3,1,8}을 위 코드를 사용해서 퀵 정렬해 보자.
첫번째 단계에서 pivot에 2가되며 {1,2,4,5,7,3,6,8}로 정렬될 것이다. 이 때 pl=3 pr=2로 {1,2}와{4,5,7,3,6,8}그룹으로 각각 나뉘어진다.
이제 여기서 방법1과 방법2로 나누어 어느쪽을 먼저 푸시할지 결정할 수 있다.
먼저 우리가 작성한 코드는 이를 구별하지 않고 왼쪽그룹을 먼저 푸시하고 오른쪽그룹을 후에 푸시하게 된다. (의도하진 않았지만 방법2가 된 것)
방법2로 위의 배열을 퀵 정렬할 때에는 스택에 최대 4칸이 쌓이게 된다.
({4,5}{2,3}{6,7}{0,1})
이번엔 반대로 방법1로 위의 배열을 퀵 정렬할 때 스택을 살펴보면, 스택에 최대 2칸밖에 안 쌓이게 된다.
일반적으로 요솟수가 적은 배열일수록 적은 횟수로 분할을 종료할 수 있다. 따라서 방법2처럼 요솟수가 많은 그룹을 나누기보다는 방법1처럼 요솟수가 적은 그룹을 먼저 분할하면 스택에 동시에 쌓이는 데이터의 최대 개수가 적어진다.
그렇다고 해서 방법 1,2의 스택 push(), pop()의 사용빈도가 줄어들진 않으나 동시에 스택에 쌓이는 최대 개수가 다르다.
방법1의 경우를 사용하면 요솟수가 n이라면 스택에 쌓이는 데이터의 최대 개수는 log n보다 적다. 따라서 요솟수가 100만개라도 스택의 용량은 20으로 충분하다.
피벗 선택하기
이 전 코드에서는 그저 배열의 중간혹은 중간 앞의 요소를 pivot으로 설정하여 그룹화를 진행했다.
하지만 피벗을 선택하는 방법은 퀵 정렬의 실행 효율에 큰 영향을 준다
다음 {8,7,6,5,4,3,2,1,0}배열을 통해 예시를 알아보자.
피벗값을 8로 지정해보자. 그러면 이 배열은 피벗값(8)만 있는 그룹가 나머지 그룹으로 나누어질 것이다. 하나의 요소와 나머지 요소로 나누어 지는(한쪽으로 치우친)분할을 반복하는 퀵 정렬은 성능이 좋게 나올 수 다.
정렬을 빠르게 하고 싶다면 배열을 정렬한 다음의 중앙값, 곧 값을 기준으로 한 중앙값을 피벗으로 하면 된다.
배열이 고르게 절반으로 나누어지기 때문에 정렬을 빠르게 할 수 있지만 중앙값을 구하는 과정 자체가 배열을 정렬해야 한다는 선행조건이 필요하기 때문에, 이는 배보다 배꼽이 큰 상황이 되기 마련이다.
이런 문제를 해결하기 위해 다음 방법을 사용하면 적어도 최악의 경우는 피하게 된다.
방법 1. 나눌 배열의 요솟수가 3 이상이면 임의로 요소 3개를 선택 후, 그중에서 중앙값인 요소를 선택한다.
{8,7,6,5,4,3,2,1,0}배열에서 3개의 임의의 요소를 선택하자 임의의 요소도 결국 우리가 코드로 정해야 하기 때문에 여기서는 처음, 중간, 끝값을 선택하겠다.
이렇게 나오느 8,4,0중 중간값인 4를 pivot으로 사용하겠다는 소리이다.
이 아이디어를 조금 더 발전시킨 방법이 다음 방법2이다.
방법 2. 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두 번째 요소를 교환한다. 피벗으로 끝에서 두 번째 요솟값(a[right - 1])을 선택하고, 나눌 대상의 범위를 a[left + 1] ~ a[right - 2]로 좁힌다.
┃ 8 ┃ 7 ┃ 6 ┃ 5 ┃ 4 ┃ 3 ┃ 2 ┃ 1 ┃ 0 ┃
┃ ┃ ┃
┠━━━━━━━━첫,가운데,끝요소 정렬━━━━━━┫
┃ ┃ ┃
┃ 0 ┃ 7 ┃ 6 ┃ 5 ┃ 4 ┃ 3 ┃ 2 ┃ 1 ┃ 8 ┃
┃ ┃
가운데 요소 - 끝에서 두번째 요소 교환
┃ 0 ┃ 7 ┃ 6 ┃ 5 ┃ 1 ┃ 3 ┃ 2 ┃ 4 ┃ 8 ┃
이렇게 만들어준다. 이 과정을 거치고 난 후 스캔하는 커서의 위치는 아래와 같이 변경된다
- pl의 시작 위치 --- left + 1
- pr의 시작 위치 --- right - 2
이 방법은 그룹의 크기가 한쪽으로 치우치는 것을 피함과 동시에 나눌 때 스캔하는 요소를 3개 줄일 수 있다. 이렇게 하면 평균 몇% 정도 빠른 속도로 정렬이 가능하다.
┃ 0 ┃ 7 ┃ 6 ┃ 5 ┃ 1 ┃ 3 ┃ 2 ┃ 4 ┃ 8 ┃
pl pr0과 4,8은 피벗보다 작은그룹, 피벗보다 큰그룹에 자동으로 속해지기 때문에 스캔하는 요소를 3개 줄일 수 있다
추가된 예제 코드
위의 과정을 추가하는 sort3elem 메서드를 만들어보자.
배열 x 안의 세 요소인 x[a], x[b], x[c]의 요솟값을 정렬(크기순)한 뒤 b값을 그대로 반환한다.
퀵 정렬을 수행하는 quickSort메서드에서 변경 내용은 배열을 나누기 전에 다음 코드를 실행하는 것이다.
- int m = sort3elem(a, pl, (pl + pr)/2, pr); 첫,중,끝 요소 정렬
- int x = a[m]; // 피벗 값
- swap(a, m, right-1); // 가운데와 끝에서 두번째 요소 교환
- pl++; // 왼쪽 커서를 1만큼 오른쪽으로 진행
- pr -= 2; // 오른쪽 커서를 2만큼 왼쪽으로 진행
최종 코드(재귀적)
public class QuickSort {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static int sort3elem(int[] x, int a, int b, int c) {
if(x[b] < x[a]) swap(x, b, a);
if(x[c] < x[b]) swap(x, c, b);
if(x[b] < x[a]) swap(x, b, a);
return b;
}
static void quickSort(int[] a, int left, int right) {
int pl = left;
int pr = right;
int m = sort3elem(a, pl, (pl + pr) / 2, pr);
int x = a[m];
swap(a, m, right-1);
pl++;
pr -= 2;
do {
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 sc = new Scanner(System.in);
System.out.print("요솟수 : ");
int[] x = new int[sc.nextInt()];
for (int i = 0; i < x.length; i ++) {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
quickSort(x, 0, x.length-1);
for (int i = 0; i < x.length; i++) {
System.out.println("x[" + i + "]=" + x[i]);
}
}
}sort3elem()메서드를 추가하고 quickSort()메서드를 재귀함수로 표현했다. quickSort()메서드의 do-while문 진입 이전에 위에서 설명한 5가지 과정을 모두 거친 후 본격적인 그룹 나누기에 들어간다.
