[알고리즘] 퀵 정렬(Quick Sort)

http://proneer.tistory.com/295

 

http://glocalit.skhu.ac.kr/~mckim1/Lecture/DS/dna/class08/class08_05.html

 

 

<개인 코멘트>

 

pivot을 기준으로, 왼쪽에는 pivot보다 작거나 같은, 오른쪽에는
pivot보다 크거나 같은 애들만 올 수 있다.

Left : 왼쪽 구역에 있으면 안되는 애들을 찾는다.
Right: 오른쪽 구역에 있으면 안되는 애들을 찾는다.

quickSort의 구성은

(재귀호출임으로..)
1. 기저사례를 작성
2. 가장 좌측의 값을 pivot으로 임의로 정해놓고
 그 값을 적절한 위치에 놓은 후, 그 index값을 return 해주는
 partition 함수를 호출한다.

3. 2번에서 구한 index 값을 기준으로 ,
  좌측 부분에 대해 또 Quick sort를 호출, 우측 부분도 quick sort 재귀 호출.

<partition()의 핵심>

left와 right가 교차되었을 때,
right의 오른쪽은 Pivot보다 모두 크거나 같고,
left의 왼쪽은 pivot보다 모두 작거나 같을 것이다.

교차가 되면, right가 현재 위치한 index의 값과(pivot보다 작은 값에 멈춰있을 것이다.)
Pivot의 값을 교환 해주고, right의 index를 return 해주면 된다.

 

Partition 함수를 짤 때, 가장 왼쪽을 pivot으로 일단 둘지,

오른쪽 값을 pivot으로 할지에 따라, 코드가 조금 달라진다. 밑에 예제를 보자.

 

(1) pivot을 가장 left 의 값으로 하고 시작하는 경우.

 

27 6 38 2 62

27이 pivot이다.

left : 38

right : 2 가 되고, 교체가 이루어 진다.

----------------------------------

27 6 2 38 62

left : 38

right : 2

left와 right의 index가 교차 되었다.

이 떄가 중요 하다.

left는 현재 38을 가리키고 있고, right는 2를 가리키고 있다.

이때 보장되는 것들은

현재 left의 위치를 기준으로 왼쪽은 모두 pivot보다 작거나 같음을 보장.

현재 right의 위치를 기준으로 오른쪽은 모두 pivot보다 크거나 같음을 보장 한다.

 

이 때, 우리가pivot을 가장 왼쪽에 놓고 시작했다. 즉, 왼쪽은 pivot값보다 작은 것들이 위치해야 하는 구역이다.

그렇기 떄문에, 현재 right가 위치하고 있는 곳의 값은 pivot보다 작거나 같은 값이므로,

pivot값 27과 right가 위치한 값이 2를 교체해준다.

------------------------------------------------------------------------

2 6 27 38 62

즉. pivot을 임의로 가장 왼쪽의 값으로 가정하고 진행되는 Quick  sort의 경우, 위와 같은 이유 때문에

left ,right가 교차되면, right가 위치하고 있는 값과 임의로 결정한 가장 좌측의 pivot값을 교체 해준다.

그리고 right가 위치한 index값을 return 해주면 된다.

 

 

반대로 가장 오른쪽의 값을 무조건 초기 pivot값으로 한다고 가정하는 경우에는 반대이다.

 

left와 right가 교차하면,  그때의 left값이 가리키고 있는 값은

pivot값보다 크거나 같은 값을 가리키고 있음을 보장하기 때문에,

left가 가리키고 있는 값과, pivot값을 교체 해준다.

 

[개인코드]

#include <iostream>

using namespace std;

#define SIZE 10

int list[SIZE] = { 24,52,11,94,28,36,13,80, 56, 71 };

void quickSort(int left, int right);
int partition(int left, int right);
void swap(int index1, int index2);

void main(void)
{
 quickSort(0, SIZE-1);
 cout<<"Sort Result : ";
 for(int i = 0 ; i < SIZE; i ++)
  cout<<list[i]<<" ";
}

void quickSort(int left, int right)
{
 int pivotIndex;

 if(left < right){       //left가 right보다 작지 않다는 것은, 즉 left가 right와 같거나, 더 크다는 것을 의미한다.
            //이는 검사해야 할, 조각이 하나 이하라는 뜻으로, 즉 더 이상 쪼개서 정렬할 필요가 없음을 의미하기에,
            //quickSort 함수가 종료되야 한다.
  pivotIndex = partition(left, right); //partition 함수가 실행 되면, 가장 왼쪽에 임의로 정한 Pivot 값이, 위치해야할 곳으로 자료가 이동되고,
            //이동한 위치 값 pivotIndex를 return 한다.

            //이제 중간 값이 결정되어, 구간이 두 곳으로 나뉘었으므로, 왼쪽, 오른쪽 구역을 각각 정렬한다.
  quickSort(left, pivotIndex-1);
  quickSort(pivotIndex+1, right);
 }
}

int partition(int left, int right)
{
 int pivotIndex = left;
 
 right++;         //do~while문으로 구현되어, right-1이 진행되기 때문에, 미리 +1을 해준다.
 
 while(true){
  do{
   right--;
  }while(list[right] > list[pivotIndex]); //right은 가장 오른쪽 끝에서 부터, 한칸신 왼쪽으로 이동하면서, pivot 값보다 작거나 같은 값을 찾는다.
  
  do{
   left++;
  }while(list[left] < list[pivotIndex]); //left는 왼쪽 pivot값 다음 부터 시작해서, 한칸씩 오른쪽으로 이동하며 Pivot값보다 크거나 같은 값을 찾는다.

  if(left < right)      //left와 right가 정지 한 후, left, right가 교차 하지 않은 경우.
   swap(left,right);     //left와 right가 찾은 값을 교환 해준다.
  else{         //left와 right가 교차한 경우.
   swap(right,pivotIndex);    //right가 가리키고 있는 값은, pivot보다 작거나 같은 값일 것이기 때문에, 교체 해준다.(pivot이 위치할 곳)
   return right;
  }
 }
}

void swap(int index1, int index2)
{
 int temp;
 printf("swap\n");
 temp = list[index1];
 list[index1] = list[index2];
 list[index2] = temp;

}