기본기)정렬)c#)퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복 알고리즘으로 평균적으로 매우 빠른 수행 속도로 정렬을 한다고 해서 Quick이라는 이름이 붙여진 정렬이다. 불안정 정렬에 속하고 분할 정렬(merget sort)과 달리 비 균등하게 분할한다.

피벗(Pivot)이라는 개념으로 정렬을 수행한다.

피벗을 기준으로 피벗보다 작은 요소들은 왼쪽으로 옮겨지고 큰 요소들은 피벗의 오른쪽으로 옮겨진다.

피벗을 제욓나 리스트와 오른쪽 리스트를 다시 정렬한다. 분할된 리스트에 대해서 순환 호출을 이용해서 정렬을 반복한다. 리스트가 0이나 1이 될 때까지 반복한다.

 

퀵 정렬의 단계에 대한 설명은 다음과 같다.

분할(Divide) : 입력 정렬을 피벗을 기준으로 비 균등하게 분할(피벗을 기준으로 왼쪽, 오른쪽)

정복(Conqueer) : 부분 배열을 정렬한다. 순한호출을 이용한다.

결합(Combine) 정렬된 부분 배열을 하나의 배열에 합병한다.

 

 private void SetQuickSort(List<int> _data, int _start, int _end)
    {
        
        if(_start >= _end){
            return;
        }

        int key = _start;
        int i = key +1, j = _end, tempValue;

        while(i <= j  ){
            while(i <=_end && _data[i] <= _data[key]){
                i++;
                //키보다 큰 값을 만날때 까지 
            }
            while(j > _start && _data[j] >= _data[key]){
                j--;
                //키보다 작은 값을 만날때 까지
            }

            if( i > j){
                tempValue = _data[j];
                _data[j] = _data[key];
                _data[key] = tempValue;
            }
            else{
                 tempValue = _data[i];
                _data[i] = _data[j];
                _data[j] = tempValue;
            }
        }
        this.DebugText(_data);

        this.SetQuickSort(_data, _start, j -1);
        this.SetQuickSort(_data, j +1, _end);
    }

 

시간 복잡도 :O(nlogn)

공간 복잡도:  O(n)

 

 ★★★☆☆