[자바] 퀵소트(Quick Sort) 란?

 [자바] 퀵소트(Quick Sort) 란?

프로그래밍 (Programming)

Quick Sort(빠른 정렬;퀵정렬이라 불림)

임의의 Pivot 값을 골라서 Pivot 보다 큰값과 작은 값을 바꾸는 정렬방식으로,
삽입등 바로 옆의 자료와 자리를 변경하지 않기때문에 좀더 효과적이다.

왼쪽에서 오른쪽으로는 P보다 큰 값을 찾고, 오른쪽에서 왼쪽으로는 P보다 작은 값을 찾는다.
그 후 그 값을 바꿔준다. 그리고 왼쪽과 오른쪽의 P가 교차 될경우 마지막에 찾은 가장
작은 값과 맨 앞의 값을 바꾼다. 그 뒤 맨 앞에 있던 값이 옴겨진 자리를 기준으로 나누어서 또 정렬 ...
P 값을 기준으로 왼쪽은 P보다 작은 값들의 집합, 오른쪽은 P보다 큰값 들의 집합이 된다.

아래와 같은 값이 배열에 들어있다고 가정 해서 실습을 보자.

그러면 우선 Pivot(기준)이 되는 숫자를 정하는데 기준이 되는 값은 배열의 맨 왼쪽의 값이 된다.
그리고 Left와 Right부분을 잡게 되는데 처음엔 맨 왼쪽이 Left, 맨 오른쪽이 Right가 된다.

3  5  6  2  1  4

Pivot : 3
Left   : 3
Right : 4

이렇게 초기값이 설정을 한 후
Left  는 Pivot값보다   클 때까지 우측으로 이동한다.
Right는 Pivot값보다 작을때까지 좌측으로 이동한다.

3  5  6  2  1  4

Pivot : 3
Left   : 5
Right : 1

이 될 것이다. 이렇게 되면 Left와 Right의 값을 Swap한다. 그리고 Left는 우측 한칸, Right는 좌측 한칸으로
이동해서 또 위의 같은 조건으로 움직인다.

3  1  6  2  5  4

Pivot : 3
Left   : 6
Right : 2

3  1  2  6  5  4

Pivot : 3
Left   : 6
Right : 2

이렇게 보면 Left의 위치는 4번째고, Right는 3번째 위치를 가리키고 있다.
즉, Left랑 Right가 교차된 상황이다. 그러면 Left랑 Right중 작은 값이랑 Pivot값이랑 Swap을 한다.

2  1  3  6  5  4

이제 한 주기가 돌았다. 

[ 2  1 ]  3  [ 6  5  4 ]

마지막 Swap했던 3을 기준으로 좌측은 3보다 작은 값, 우측은 3보다 큰 값들로 정렬이 되어버렸다.
이제 [ 2  1 ]과 [ 6  5  4 ] 값을 또 위와 같은 방식으로 정렬을 돌려보자.

[ 2  1 ]

Left는 2보다 큰 값이 없으므로 우측 맨 끝으로 간걸로 간주한다.
그러면 Right보다 우측이 있는 즉, 교차 되버린것이다. 그래서 작은 값인 1이랑 Swap된다.

1  2  3  [ 6  5  4 ]

또 교차 되어서 4와 Pivot값인 6과 Swap을 한다.

1  2  3  [ 4  5 ] 6

1  2  3  4  5  6

퀵 소트 정렬이 끝났다.

아직 이해가 잘 안갔을 수도 있으므로 아래의 예를 하나 더 들여보았다.
(아래 예제는 곰팅인간님 블로그에서 가져왔습니다.)

정렬할 값
   [ 26  5  37  1  61  11  59  15  48  19 ]

1차
   [ 26  5  37  1  61  11  59  15  48  19 ] 
   [ 26  5  19  1  61  11  59  15  48  37 ] 
   [ 26  5  19  1  15  11  59  61  48  37 ]
   [ 11  5  19  1  15 ] 26 [ 59  61  48  37 ]

2차
   [ 11  5  19  1  15 ] 26 [ 59  61  48  37 ]
   [ 11 5  1  19  15 ] 26 [ 59  61  48  37 ]
   [ 1  5 ] 11 [ 19  15 ] 26 [ 59  61  48  37 ]

3차
   [ 1  5 ] 11 [ 19  15 ] 26 [ 59  61  48  37 ]
   1  5  11 [ 19  15 ] 26 [ 59  61  48  37 ]
   
4차
   1  5  11 [ 19  15 ] 26 [ 59  61  48  37 ]
   1  5  11  15  19  26 [ 59  61  48  37 ]

5차
   1  5  11  15  19  26 [ 59  61  48  37 ]
   1  5  11  15  19  26 [ 59  37  48 61 ]
   1  5  11  15  19  26 [ 48  37 ] 59 [ 61 ]

6차
   1  5  11  15  19  26 [ 48  37 ] 59 [ 61 ]
   1  5  11  15  19  26  37  48  59 [ 61 ]

7차(완료)
   1  5  11  15  19  26  37  48  59  61