quick sort

퀵소트따위야.. 했던게 오늘 막힐줄이야...

그래서 이렇게 정리한다.

 

보시는 분들에게도 도움이 되기를...

 

 

퀵소트는 뭐

말에서 보다 싶이, 나름 빠름을 구현했다고 해서 퀵 소트이다. 퀵소트라 불릴만도 하지...

 

퀵소트는 O(n logn)의 복잡도를 가진다.

 

 

퀵소트의 메인 알고리즘은 직관적이지는 않다.

천천히 설명을 따라와봐야 이해할 듯 싶다.

 

일단, 퀵소트의 Parameter, 즉 인풋을 먼저 보자.

(모든 알고리즘을 볼 때에는 인풋을 항상 먼저봐서 따라가는 건 당연한 얘기!)

일단 쉽게 설명하기 위해서, 배열을 static으로 선언했다고 가정하자.

 

 

private void quick_sort(int left, int right);

 

 

자, 그럼 이놈은 뭐 길래, left, right라는 인풋을 가지면서 소트를 진행시켜가는지 알아보자.

일단 간단하게 설명하면 보통 소트는 한번의 연산과정에서 그 해당하는 놈을 적절한 위치에 놓는 과정을 수행한다. 그래서 가장간단하게 짜면 O(n^2)의 복잡도가 나온다. quickSort의 기본적인 개념은 left와 right사이에 pivot(중심축,, 뭐 그런뜻임, 퀵소트 알고리즘에서는 =Left ) 을 설정하고 그 피봇이 맞는 위치에 가져다 둔다. 이것만 말해준다면 해당하는놈을 적절한 위치에 놓는다는 다른 소트와 다를 것이 없다.

 

하지만 pivot에 있는 값을 적절한 위치에 배치시키기전에, 그 배치된 자리 왼쪽으로는 pivot보다 작은값들이, 오른쪽으로는 pivot보다 큰값들이 정리되게 된다. 그냥 간단하게 Pivot 이 5인 퀵소트를 한번 실행시키면

 

1 3  2 5 8 19 9 20

 

연산후 5값을 갖는 피봇이 적당한 위치에 박히고, 그 왼쪽으로는 그보다 작은값, 반대편은 큰값이 정렬된다는 얘기, 하지만 그 양쪽값들은 정렬되어있는지 확신할 수 없다. 그렇다면?

 

왼쪽값들로 또 퀵소트 알고리즘을 적용,

오른쪽값들로 또 퀵소트 알고리즘을 적용,

 

==> Recursive(재귀) 함수로 해결한다.

 

 

 

일단 left, right 는 배열(input이라고 가정)의 input[left]~input[right]에 이 알고리즘을 적용시키겠단 얘기다.

 

아래와 같은 예제를 가지고 한번 생각해보자.

 

4

1

5

3

2

 

 

 

자 이런 배열을 퀵소트로 소트해보자.

 

일단

quickSort(0 ,  input.length-1 );  // (input.length :: 예제에서는 5)

그럼 input[0]에서부터 input[4]까지 퀵소트라는 메쏘드를 적용하겠다는 의지!!

 

 

 

4

1

5

3

2

 

 ....Pivot.................................................................

......Left ........................................................Right....

 

 

자, 시작하자.

 

처음에는 Pivot위치에 있는 값과 left위치에 있는 값을 비교해서 left의 적절한 위치를 잡는다.

(input[pivot] >= input[left]) 라는 조건, 즉 pivot위치의 값보다 left의 위치의 값이 작으면

(앞으로는 pivot=p, left = L , right = R로 적겠다 ㅠ) L++;시킨다.

 

 

 

4

1

5

3

2

 

 .....Pivot..................................................................

.....................................Left..........................Right....

 

 

이렇게 된다. 만약 피봇의 있는 값보다 큰값을 만나면 거기서 정지,

정지가 되었다면 R값의 적절한 위치를 찾아준다.

 

R은 L과 반대로 right위치에 있는 값이 크면 왼쪽으로 이동한다. (input[pivot] <= input[R]) R--;

그럼 지금 상황에서 R은 어떻게 되나? 4보다 2가 작으므로 R값은 움직이지도 못하고 위 그림처럼

스탑,

 

자 그럼 이렇게 값을 찾았으면 L위치의 값과 R위치의 값을 swap (자리바꿈) 해준다.

 

 

 

4

1

2

3

5

 

 .....Pivot..................................................................

.....................................Left..........................Right....

 

값의 위치가 바뀐것이지 L과 R은 바뀌지 않는다.

또 그럼 아까의 방법대로 진행해 간다.

 

Left는 Pivot의 위치보다 큰값이 보일때까지 오른쪽으로 갈테니 아까 바꿧던 5의 자리로 도착하게 되고,

Right는 Pivot의 위치보다 작은값이 보일때가지 왼쪽으로 갈테니 3에서 멈추게 된다.

 

 

4

1

2

3

5

 

 .....Pivot..................................................................

..................................................Right..........Left.......

 

 

여기서 왜 이걸 고안해냈던 사람이 인덱스를 Left, Right해줬는지 알수 있게 된다.

Right가 Left의 왼쪽에 오는 순간, 우리는 묘함을 느끼게 된다. 오른쪽인덱스란놈이 왼쪽에...-_-+

그래서 퀵소트 알고리즘의 일단락은 여기서 발생한다. 그렇게 되면 L과 R로 인덱싱하는게 끝났고, 그럼 이제 pivot으로 관심을 돌려보자.

 

이제 pivot을 적당한 자리에 넣어야 한다.

right나 left 둘중에 하나로 놓어야 하는데, left의 위치와 바꿔버리면 아까 5는 4보다 크다는 이유때문에 오른쪽으로 박혀졌는데 그것을 다시 왼쪽으로 소환하는 뵹딘같은 짓이 되어버린다. 따라서 right위치와 pivot위치의 수를 바꾼다.

 

 

3

1

2

4

5

 

 .....Pivot..................................................................

..................................................Right..........Left.......

 

 

우왕쿧, 그럼 아까 말했듯이 이번 턴의 Pivot인 4는 제 위치를 찾았고, 오른쪽 왼쪽의 수들은 4를 기준으로 크고, 작은 속성이 있는 것들끼리 있다.

 

이와같은 방법으로 왼쪽, 오른쪽의 놈들을 다시 퀵소트 한다.

쉽게말해

 

quickSort(oriLeft, right-1);

quickSort(rignt+1, orRight);

 

이놈이 수행된다는 말,

 

oriLeft, oriRight는 이 함수가 시작될때 받았던 인풋, left, right를 따로한번 저장해 둔 것이다.

 

quickSort(0, right-1);

quickSort(right+1, input.lengt-1 );

 

하면 어떻게 될지 생각해보길 바란두아..

아래는 wikipedia에서 퍼온, gif파일로 만든 퀵소트의 꼬라지? 순서이다.

 

보면 회색의 블럭이 보임을 알수 있는데 회색의 블럭이 현재돌아가고 있는 Quicksort의 범위이고 붉은색 막대기가 Pivot이다.

 

 

여러분의 전산건강을 위해서 소스코드는 올리지 않켓두아.

 

 

메모자: 한국정보통신대학교 박순찬

[출처] [Algorithms] 퀵소트 (Quick sort)|작성자 mr스네이크