퀵정렬알고리즘

퀵정렬 알고리즘

- 피벗을 활용한 알고리즘 

- 피벗을 통해서 그룹을 두 그룹씩 나누는 것을 반복한다.

- 피벗이 그룹 요소가 하나일 때 최종적으로 정렬이 완료된다.

PIVOT 위치에 있는 6을 기준으로 포인터 PL이 가리키는 값은 6보다 작을 경우 계속 우측으로 이동하고 

6보다 클 경우 해당 위치에서 멈춘다. 

가령, 값이 7인 부분에서 PL 포인터는 멈출 것이다.

반대로 PR 부분은 6보다 클 경우 계속 좌측으로 이동한다.

6보다 작을 경우 해당 위치에서 멈춘다.

가령, 값이 4인 부분에서 PR 포인터는 멈출 것이다.

그렇게 될 경우, 7과 4의 위치를 교환하여 다시 정렬한다.

이 과정을 PL의 포인터와 PR포인터가 교차될 경우 멈춘다.

그러면 정렬은 아래와 같이 바뀔 것이다.

1차 퀵소트를 진행하면 PL이 PR보다 같아질 때까지 돌고 PL이 커질 경우 퀵소트는 마무리됩니다.

이를 여러 차례 진행해야합니다.

단! 피벗을 각 그룹마다 두어 PL , PR을 피벗과 비교하면서 정렬하는 방법을 계속해서 작업하면 됩니다.

그렇다면 기저조건은 어떻게 될까요?

PL 포인터와 PR 포인터가 각각 가장자리를 넘어 설 때 끝나게됩니다.

재귀 조건으로 설정한다면 PL포인터가 오른쪽 가장자리를 넘지 않을 경우 QuickSort가 진행됩니다.

오른쪽 가장자리는 계속해서 유지된 상태로 QuickSort 함수가 재귀적으로 호출되고 

반대로 PR포인터가 왼쪽 가장자리를 넘지 않을 경우 계속해서 QuickSort가 진행됩니다.

이 또한, Left(왼쪽 가장자리)는 유지된채로 QuickSort가 재귀적으로 호출됩니다.

왼쪽 가장자리를 지나야 끝나야 재귀 호출이 끝나는걸로 해야하기 때문입니다.

코드는 아래와 같습니다. 

우선 피벗을 통해서 PL포인터 PR포인터 각각 가리키는 값과 비교하면서 인덱스를 이동시키고, 

swap을 통해서 값의 위치를 변경시킨다.

---

int pl = 0;

int pr = a.length - 1;

int pivot = a[(pl+pr)/2];

do{

while(a[pl] < pivot) pl++; // 값이 피벗보다 작을 경우는 pl의 인덱싱이 우측으로 한 칸씩 증가된다.

while(a[pr] > pivot) pr--; // 값이 피벗보다 클 경우 pr의 인덱싱이 좌측으로 한 칸씩 감소된다.

if(pl <= pr){

swap(a,pl++,pr--);   

// pl포인터와 pr포인터가 각 자리에 맞게 매칭되어 있을경우, (아직 Grouping 작업을 더 할 수 있을 경우)

// pl, pr이 가리키는 값들을 a배열에 대해서 swap한다. 

// 단, swap 한 뒤에는 pl과 pr은 각각 우측으로 한 칸, 좌측으로 한 칸 씩 이동해야 하므로 후위연산자를 통해 표현

// 한다.

}

} while(pl <= pr);

---

다음 코드는 한 차례만 Pivoting 작업을 하여 Grouping 한 것이다.

위 과정을 여러 번 반복하면 퀵 정렬이 완성된다.

과정은 아래와 같다.

---

static void quickSort(int[] a,int left,int right){

int pl = left;

int pr = right;

int pivot = a[(pl+pr)/2];

do{

while(a[pl] < pivot) pl++;

while(a[pr] > pivot) pr--;

if(pl <= pr)

swap(a,pl++,pr--);

}while(pl<=pr);

// 다음 과정을 pl 값이 right를 넘지 않을 경우 재귀적 호출 

// 다음 과정을 pr 값이 left를 넘지 않을 경우 재귀적 호출

if(pl < right)

quickSort(a,pl,right);

if(pr > left) 

quickSort(a,left,pr);

}

---

[전체 코드]

import java.util.Scanner;

public class 퀵정렬 {

private static Scanner scanner;

private static void swap(int[] a, int pl, int pr) {

int tmp = a[pl];

a[pl] = a[pr];

a[pr] = tmp;

}

private static void quickSort(int[] a, int left, int right) {

int pl = left;

int pr = right;

int pivot_value = a[(pl + pr) / 2];

do {

while (a[pl] < pivot_value)

pl++;

while (a[pr] > pivot_value)

pr--;

if (pl <= pr)

swap(a, pl++, pr--);

} while (pl <= pr);

if (left < pr)

quickSort(a, left, pr);

if (right > pl)

quickSort(a, pl, right);

}

public static void main(String[] args) {

// TODO Auto-generated method stub

int[] a = new int[9];

System.out.println("배열을 나눕니다. 값을 넣어주세요 (10개)");

scanner = new Scanner(System.in);

for (int i = 0; i < a.length; i++) {

a[i] = scanner.nextInt();

}

System.out.println("요솟수 : " + a.length);

quickSort(a,0,8);

System.out.println("퀵정렬 완료");

for (int i = 0; i < 9; i++) {

System.out.print(a[i] + " ");

}

System.out.println("");

}

}

---

감사합니다.