[알고리즘][정렬] 퀵 정렬

■ 퀵 정렬이란

 

"병합 정렬" 과 같이 가장 많이 사용되고 빠른 정렬 알고리즘  

기준 데이터(Pivot)을 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

시간 복잡도는 평균 O(NlogN) 이지만 이미 정렬이 되어잇는 경우 최대 O(N2) 까지 늘어날 수 있다.

---

■ 정렬 방법

기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 형식

호어 분할방식을 기준으로 리스트에 첫 번쨰 데이터를 pivot으로 설정

 

[Step 1]

왼쪽으로 부터는 기준 데이터보다 큰 데이터를 찾고 

오른쪽으로 부터는 기준 데이터보다 작은 데이터를 찾는다

 

[Step 2]

두 데이터 값의 인덱스가 교차하지 않는다면

값을 교환 후 다시 반복한다.

 

[Step 3]

만약 두 데이터의 인덱스 값이 교차 된다면

오른쪽으로부터의 RightIndex의 값을 기준 데이터(pivot)와 교체 후 

RightIndex에 할당되어 있는 값을 기준 데이터(pivot)로 잡고 양쪽으로 분할한다.

 

[Step 4]

그후 왼쪽에는 RightIndex - 1 값을 끝으로 

오른쪽에는 RightIndex +1 값을 시작으로  

설정하여 재귀를 반복하여 정렬한다.

---

■ 예시 자료

 

 

 

설명 : 5를 기준 데이터(pivot)으로 잡고 왼쪽으로부터 기준 데이터보다 큰값 7과

오른쪽으로 부터 기준데이터보다 작은 값 4를 발견했으나 두 값의 Index가 교차하지 않으므로 두 값만 교체한다.

 

 

 

 

 

설명 : 위와 같이 5를 기준 데이터(pivot)으로 잡고 왼쪽으로부터 기준 데이터보다 큰 값 9과

오른쪽으로 부터 기준 데이터보다 작은 값 2를 발견했으나 두 값의 Index가 교차하지 않으므로 두 값만 교체한다.

 

 

 

설명 : 하지만 왼쪽으로 부터 기준 데이터보다 큰 값 6과

오른쪽으로 부터 기준 데이터보다 작은 값 1를 발견했으나 두 값의 Index가 교차하므로 RightIndex의 값 1과

기준 데이터 5를 교체한후 양쪽으로 분할한다. 

 

 

 

 

 

 

 

 

 

설명 : 그 후 위와 같은 식으로양옆으로 각각 다시 반복하는 재귀함수를 통해 정렬한다.

 

---

■ 직접 작성한 코드(c#)

public static class MyCode
{
    public static void MyQuickSort(int[] _arr, int _startIndex, int _endIndex)
    {
        if (_startIndex >= _endIndex) { return; }   // 재귀함수 끝내는 조건
 
        int pivotIndex = _startIndex;                // 기준 데이터는 첫번째 데이터
        int leftIndex  = _startIndex + 1;            // 왼쪽 다음부터 비교 시작
        int rightIndex = _endIndex;                    // 마지막 데이터
        
        // 양 끝의 인덱스 값이 교차할떄가지 반복
        while (leftIndex <= rightIndex)
        {
            // 왼쪽값들로부터 기준 데이터보다 큰 값을 찾음
            while (leftIndex <= _endIndex && _arr[leftIndex] <= _arr[pivotIndex])
            { leftIndex++; }
            
            // 오른쪽값들로부터 기준 데이터보다 작은 값을 찾음
            while (rightIndex > _startIndex && _arr[rightIndex] >= _arr[pivotIndex])
            { rightIndex--; }
            
            // 만약 인덱스 값이 교차할 경우 rightIndex의 값을 기준 데이터와 바꾸고 While문 종료 
            if (leftIndex > rightIndex)
            {
                int temp         = _arr[rightIndex];
                _arr[rightIndex] = _arr[pivotIndex];
                _arr[pivotIndex] = temp;
            }
            else
            {    // 아닐 경우 왼쪽 값과 오른쪽 값을 바꿈 다시 반복
                int temp         = _arr[rightIndex];
                _arr[rightIndex] = _arr[leftIndex];
                _arr[leftIndex]  = temp;
            }
        }
        
        MyQuickSort(_arr, _startIndex, rightIndex - 1);        // rightIndex 값을 기준으로 분할되어 endIndex를     새로운 기준 데이터 인덱스의     -1 왼쪽 정렬
        MyQuickSort(_arr, rightIndex + 1, _endIndex);        // rightIndex 값을 기준으로 분할되오 startIndex를 새로운 기준 데이터 인덱스의     +1 한 후 오른쪽 정렬
    }
}