Note.

해당 글은, 퀵정렬의 기본적인 개념은 알고 있다는 전제로 진행합니다.

또한 틀린 내용이 있다면, 가감없이 알려주시면 감사하겠습니다. (_ _)

오늘은 퀵정렬 알고리즘에 대해 포스팅합니다.

퀵정렬 알고리즘은 매우 유명해서 검색하면 많은 자료를 찾아볼 수 있을텐데요.

저도 오랜만에 퀵정렬을 공부하려고, 많은 자료를 찾아봤는데 비슷 비슷한 코드를 볼 수 있었습니다.

그런데 말입니다.(김상중 아찌톤) 코드를 왜 그렇게 구성했는지 한번에 이해가지 않았으며, 후에 분석해본 결과 틀린 코드들도 정말 많았습니다.

어쩌면, 퀵정렬 구현이 공식처럼 알려진게 아닌가 싶고 제대로 된 코드 이해없이 비슷하게만 따라하다가 틀린 코드를 작성하는 경우가 많을거 같다는 생각을 했습니다.

그렇기에, 퀵정렬 코드를 단번에 이해못하는 멍청한 저를 위해, 나름대로 개념을 뽀개 봤습니다.

해당 포스팅은 아래와 같이 쓸때없는(?) 것을 연구하고 도출한 결과를 설명 해볼까합니다.

• 왜 많은 자료들의 코드는 pivot index를 항상 끝 방향에 두고 코딩을 하는걸까? 가운데다가 두고 하면 안돼는가?

• 왜 어떤 코드는 탐색 할 때, pivot 의 값만 비교하고, 어떤 코드는 pivot 값과 왼쪽 index 와 오른쪽 index 크기 비교까지 하는 걸까?

  x
  while(data[beginIndex] <= pivotData) beginIndex++;
  ​
  or
    
  while(data[beginIndex] <= privotData && beginIndex < endIndex) beginIndex++;
  

• 왜 다들 오른쪽 부터, 탐색하는 코드만 작성 하는가? 왼쪽부터 탐색하면 안되는가?

• SWAP 작업을 마치고, 마지막에 pivot index를 옮길 때, 주의해야할점

Pivot을 끝방향(왼쪽 끝 또는 오른쪽 끝)에 두는 이유

저는 이상한 고집이 있어서, 남들이 pivot 을 끝에다가 두면 굳이 가운데다가 해보고싶은 욕구가 있습니다. 지식을 습득할 때, 당연하게 외우기 보다 왜 그렇게만 해야하는지에 대해 아는게 중요하다고 생각하기 때문이지요.

결론적으로, pivot 을 가운데다가 배치를 하게 되면, 코드를 작성하기가 매우 까다로워 집니다.

퀵정렬의 기본개념은, 왼쪽방향과 끝쪽방향에서 서로 접근하며 바꿀 수 있는 수가 나올때 SWAP 을 시도하는것과, SWAP 작업을 마친 후, pivot 자리를 찾아주는 것이 중요합니다. 그래야 pivot 기준으로 왼쪽, 오른쪽 배열로 쪼개서 분할정복 을 시도할 수 있기 때문이지요.

문제는 pivot 이 가운데에 끼여 있으면, pivot 도 SWAP 될수도 있다는것 입니다. 그럴경우, pivot index를 업데이트를 꼭 해주어야 합니다.

그렇지 않으면, 마지막에 pivot 자리를 찾아주는 과정에서 pivot 이 아닌 다른 값을 배치하기 때문이지요.

정리하자면, pivot을 가운데 잡아서 SWAP 작업을 진행하느니, 맨끝쪽에 pivot을 배치하여 SWAP 작업으로부터 안전하게 빼면 index 업데이트를 할 필요가 없습니다.

탐색할 때 비교해야할 요소

코드는 짧고 명료하고 간단한것이 매력적입니다. 멍청해서, 어려운건 이해하가 힘들거든요. (나도 똑똑해지고 싶다!!!)

그래서 그런지, 아래 코드가 끌리긴 했습니다. 굳이 왼쪽 index 와 오른쪽 index 를 비교해야 하나 싶었지요.

xxxxxxxxxx
while(data[beginIndex] <= pivotData) beginIndex++;

결론적으로는, 비교를 해야 하는게 맞습니다.

만약 하지 않는다면, index 가 배열 밖으로 벗어날 위험이 있습니다.

아래와 같은 배열이 있다고 가정해봅시다. (pivot 은 맨 왼쪽입니다.)

위 코드를 실행하면, beginIndex 는 결국 배열 크기 밖으로 빠지면서, OutOfIndex 에러가 발생하게 됩니다.

이를 방지하기 위해, beginIndex 의 조건을 배열 크기 보다 작은 경우로 줄 수도 있겠습니다.

하지만 우리가 원하는 것은 beginIndex 와 endIndex 가 만나는 순간이고, endIndex는 배열 크기 보다 무조건 작거나 같으므로 아래와 같이 더 적은 횟수를 수행하는 조건으로 작성할 수 있습니다.

xxxxxxxxxx
while(data[beginIndex] <= pivotData && beginIndex < endIndex) beginIndex++;

생각보다 많은 자료의 코드들이 OutOfIndex 에러가 발생하는것을 목격할 수 있었습니다.

탐색 순서가 중요한 이유

아까도 말씀드렸다 시피, 저는 이상한 고집이 있어서... 오른쪽 부터 탐색하는 코드가 많으면, 굳이 왼쪽으로 해보고 싶어집니다.(삐뚤게 살거야ㅋㅋㅋ)

해봤더니, 코드가 제대로 동작하지 않았습니다.

이상합니다. 어떤 코드는 왼쪽부터 동작하게 짰었거든요. 그렇다면 탐색 순서가 중요하긴 한가 봅니다.

고민해본결과, 왼쪽 부터 먼저 탐색하는것과 오른쪽 부터 탐색하는 결과의 차이점은 다음과 같습니다.

다음 그림에서, pivot을 맨 왼쪽 으로 잡았습니다.

탐색하는 코드는 다음과 같이 왼쪽부터 수행한다고 가정 한다면,

x
while (data[beginIndex] <= pivotData && beginIndex < endIndex) {
  beginIndex++;
}
​
while (data[rightIndex] >= pivotData && beginIndex < endIndex) {
  endIndex--;
}

beginIndex 는 8 에 endIndex 도 마찬가지로 8 에 위치하게 됩니다. (index 가 아니라 값입니다.!!! )

beginIndex 와 endIndex 가 만났으니 pivot SWAP 작업을 거쳐야 하는데, 자세히 살펴보면 해당 작업을 수행하면 정렬 이 깨져 버립니다.

8 과 5 를 바꾼 후, 살펴보면 pivot 값인 5를 기준으로 왼쪽에 작은수만 있어야 하는 8 이 있어버리는 바람에 정렬이 깨져버립니다.

그렇다면 오른쪽부터 수행하면 어떻게 될까요?

해보시면 알겠지만, beginIndex 도, endIndex 도 5 에 도달하게 됩니다.

pivot SWAP 작업을 거치더라도, 정렬이 깨지지 않는걸 알 수 있죠.

정리하자면 이렇습니다.

왼쪽부터 탐색을 수행하면, pivot 값 보다 큰 값 으로 beginIndex 와 endIndex 가 만나게 되며,

오른쪽 부터 탐색을 수행하면, pivot 값 보다 작은 값 으로 beginIndex 와 endIndex 가 만나게 됩니다.

이를 통해, 아래와 같이 생각 할 수 있습니다.

이는, 만약 맨-왼쪽으로 pivot 값 을 잡는다면, SWAP 대상이 pivot 값 보다 작은 값 이여야 하며,

맨-오른쪽으로 pivot 값 을 잡는다면, SWAP 대상이 pivot 값 보다 큰 값 이여야 함을 알 수 있습니다.

즉... 왼쪽부터냐 오른쪽 부터냐는 취향대로 하면 안되고,

pivot의 위치에 따라 반대방향으로 탐색 순서를 잡아야 함을 알 수 있습니다.

pivot swap 할 때, 주의 해야할점.

SWAP 작업의 마지막은 pivot SWAP 으로 pivot 자리를 찾아주는 것으로, 이는 매우 중요한 작업입니다.

많은 자료의 코드들이 단순하게 beginIndex 와 endIndex 가 만나는 지점의 index 와 SWAP 을 시켜주는데, 이는 잘못된 코드가 될 수 있습니다.

아래와 같은 배열이 있다고 가정해봅시다. (pivot 은 맨 왼쪽입니다.)

배웠드시, 맨 왼쪽 pivot 이므로 오른쪽 부터 탐색을 수행해야 합니다.

그렇게 되면 beginIndex 와, endIndex 도 5 에 도달하게 됩니다.

이때, pivot SWAP 을 진행하고 살펴보면 정렬이 깨지는걸 알 수 있습니다.

이런 현상이 왜 발생하냐면, beginIndex 가 수행할 기회 없이, 일방적으로 endIndex 가 끝으로 와버렸기 때문입니다. 즉 합의에 의한 만남이 아니라 일방적인 만남인것이지요. (말이좀 이상하네)

이런 경우가 있을 수 있기 때문에, pivot SWAP 을 진행할 때는, 데이터 크기 비교 후 진행해야 합니다.

xxxxxxxxxx
if (leftIndex == rightIndex && data[leftIndex] < pivotData) {
    swap(data, pivotIndex, leftIndex);
    pivotIndex = leftIndex;
}

정리하자면,

• pivot 은 가운데다가 둘 수 있지만, SWAP 작업에 영향을 받을 수 있으니, 안전한 장소인 양끝에 두는걸로 하자.
• index 탐색 작업을 수행 할 때, 배열 크기를 넘을 수 있으니 반드시 left < right 조건과 같이 탐색을 진행하자.
• pivot 을 오른쪽 끝에 둘거면, 탐색 순서를 왼쪽부터! pivot 을 왼쪽 끝에 둘거면, 탐색 순서를 오른쪽 부터 진행하자.
• pivot SWAP 을 진행할 때는, 해당 요소의 크기 조건이 안맞는 경우도 있으니 크기 조건을 반드시 추가하자.

마무으리

위에 진행한 코드는 아래에 경로에서 볼 수 있습니다.

https://github.com/Mommoo/Programmers/blob/master/src/com/mommoo/practice/sort/QuickSort.java

코드를 봐도 이해가 안간다는건 참 속상한 일입니다.

이렇게 분석을 나름 열심히 했는데도 틀린 분석이라면 더 속상할 거 같습니다.

만약에 이 게시글을 보고 틀린점이 있다면, 꼭 알려주셨으면 합니다.

읽어주셔서 감사합니다.