04 정렬 알고리즘 - 퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort)

 

기준이 되는 원소를 기준으로 하여 기준 원소보다 작거나 같은 값을 지닌 자료는 앞으로 큰 값을 진ㄴ 자료는 뒤로 가도록 하여 기준 원소를 중심으로 분할해가며 정렬을 진행하는 방식입니다.

 

■ 정렬방식

1. 기준이 되는 원소를 정합니다. 배열의 시작 원소를 pivot으로 설정합니다.

 2. 좌우 인덱스를 지정합니다. 해당 인덱스는 다음을 의미합니다.

 - left : pivot 보다 큰 값을 찾으러 다니는 index

 - right : pivot 보다 작은 값을 찾으러 다니는 index

 - left_hold : pivot을 제외하고 정렬 대상의 시작점

 - right_hold : pivot을 제외하고 정렬 대상의 끝점

 3. left를 pivot보다 큰 값을 찾을 때 까지 이동합니다.

 4. right를 pivot보다 작은 값을 찾을 때 까지 이동합니다.

 5. left <= right 조건이라면 두 원소를 스왑합니다.

 6. 3번 4번 과정을 left<=right 만족 할때까지 반복합니다.

 7. left 와 right가 교차하게 되면 right 위치에 pivot 값을 대입합니다.

 8. right를 기준으로 분열된 배열에대해서 퀵 정렬을 반복합니다.

  

: pivot

 

: Swap 되는 원소

  

5

4

8

2

9

3

11

1

다음 원소들에 대해서 퀵 정렬을 실행 해보겠습니다.

5

4

8

2

9

3

11

1

  pivot        left                                                                         right

 

먼저 배열의 첫 번째 요소인 5가 pivot이 됩니다. left는 pivot을 제외한 배열의 가장 앞에로 지정을 하고 right도 pivot을 제외한 배열의 끝점으로 지정을 합니다.

5

4

8

2

9

3

11

1

  pivot                     left                                                            right

 

이제부터 left부터 5보다 큰 수를 찾아가보겠습니다. 4는 5보다 작으므로 left를 이동시킵니다.

5

4

8

2

9

3

11

1

  pivot                      left                                                           right

 

8은 5보다 크므로 멈춥니다. 다음으로 right를 피벗보다 작은 수를 찾아 이동시키겠습니다. 이번 경우는 시작부터 5보다 작은 수 1이므로 그대로 멈추게 됩니다.

  

5

4

1

2

9

3

11

8

  pivot                      left                                                           right

이제 left와 right가 가르키는 원소를 서로 스왑합니다. 다음으로 아직 left와 right가 교차하지 않았으므로 다시 left부터 맞는 위치를 찾아갑니다.

 

5

4

1

2

9

3

11

8

   pivot                                               left                                 right

  

다음으로 5보다 큰 수 9에서 left는 멈추게 됩니다.

  

5

4

1

2

9

3

11

8

   pivot                                               left       right 

 

right의 다음위치는 3이 됩니다. 

 

5

4

1

2

3

9

11

8

   pivot                                               left        right

left와 right를 교환합니다.

 

5

4

1

2

3

9

11

8

   pivot                                              right       left

 

다음으로 left와 right를 이동시키게 되면 드디어 right와 left가 교차하게 됩니다. 

 

3

3

1

2

5

9

11

8

   pivot                                              right     left

  

right와 pivot이 가르키는 원소를 서로 교환해줍니다.

그림을 보면, 현재 5를 기준으로 하여 왼쪽에는 5보다 작은 수 오른쪽에는 5보다 큰수가 놓이게 됩니다. 즉 5는 제자리를 찾게 되는 겁니다. 이제 계속해서 5를 기준으로 분열 된 두 배열에 대해서도 똑같은 작업을 반복을 해주면 됩니다.

 

■ 특징

1. 최악의 경우 O(n＾2) 비교를 수행하고, 평균적으로 O(nlog n)번의 비교를 수행 

2. 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘 설계가 가능

3. 다른 정렬 알고리즘에 비해 빠르게 동작 가능

 

■ 소스코드 (Source Code)

    public int[] Quick_Sort(int[] data,int left,int right)
    {
        int pivot_index = left;
        int pivot = data[pivot_index];
        int hold_left = left;
        int hold_right = right;
        
        left++;


        while(right>=left)
        {
            while(left<=right &&data[left]<=pivot)
            {
                left++;
            }
            while(data[right]>=pivot && left<=right)
                right--;
            if(left <=right)
            {
                int tmp = data[left];
                data[left] = data[right];
                data[right]  = tmp;
            }

        }

        int tmp =data[pivot_index];
        data[pivot_index] = data[right];
        data[right]=tmp;
        
        if(right >hold_left)
            data = Quick_Sort(data,hold_left,right-1);
        
        if(hold_right>right)
            data= Quick_Sort(data,right+1,hold_right);
        
        return data;
    }

 

출처 : https://lktprogrammer.tistory.com/33?category=672214