정렬 - 퀵 정렬 (Quick Sort)

#1 알고리즘

#1-1

어떤 원소를 기준으로 잡을 것이냐는 아무래도 상관없다. 여기에서는 각 배열의 맨 끝 원소를 기준으로 잡기로 한다.

혹시라도 기준을 대략적으로라도 원소들의 평균값에 가깝게 잡을 수 있는 조건이 존재한다면, 해당 조건을 이용해 기준을 잡게끔 응용할 수도 있을 것이다. 기준이 평균값에 가깝게 잡힐수록, 퀵 정렬의 성능이 좋아지기 때문이다.

 

#1-2

이 '분할(partition)'의 결과로 기준 원소의 자리가 최종적으로 결정되면, 그 원소는 앞으로의 모든 qucikSort() 재귀 호출에서 사용되지 않고 영원히 그 자리가 고정된다. 즉, 분할 한 번에 원소 하나가 정렬되는 것이다.

 

#1-3

퀵 정렬 - 위키백과, 우리 모두의 백과사전

퀵 정렬의 총 비교 횟수 계산은 해당 링크로 대체한다.

 

#2 코드

#2-1 자바

public static void quickSort(int[] array, int startIndex, int endIndex) {
    // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
    if(startIndex < endIndex) {
        int pivotIndex = partitionAroundPivot(array, startIndex, endIndex);
        quickSort(array, startIndex, (pivotIndex - 1));
        quickSort(array, pivotIndex, endIndex);
    }
    
}

// endIndex가 pivot(기준)의 역할 수행
private static int partitionAroundPivot(int[] array, int startIndex, int endIndex) {
    int endOfLower = startIndex - 1;
    
    for(int i = startIndex; i < endIndex; i++) {
        if(array[i] <= array[endIndex]) {
            // array[endIndex]보다 lower인 값 저장할 공간 확보를 위해 endOfLower++
            endOfLower++;
            
            // array[i]와 array[endOfLower]의 값 서로 교환
            int temp = array[endOfLower];
            array[endOfLower] = array[i];
            array[i] = temp;
        }
    }
    
    // array[endOfLower] 바로 뒤에 array[endIndex] (= 기준) 값이 오게 하기 위해서 endOfLower++
    endOfLower++;
    
    // array[endIndex]과 array[endOfLower]의 값 서로 교환
    int temp = array[endOfLower];
    array[endOfLower] = array[endIndex];
    array[endIndex] = temp;
    
    return endOfLower;
}

 

#2-2 코틀린

fun quickSort(array: Array<Int>, startIndex : Int, endIndex : Int) {

    // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
    if(startIndex < endIndex) {
        val pivotIndex = partitionAroundPivot(array, startIndex, endIndex)
        quickSort(array, startIndex, (pivotIndex - 1))
        quickSort(array, pivotIndex, endIndex)
    }
}

// endIndex가 pivot(기준)의 역할 수행
fun partitionAroundPivot(array: Array<Int>, startIndex : Int, endIndex: Int) : Int {
    var endOfLower = startIndex - 1

    for (i: Int in startIndex..<endIndex) {
        if (array[i] <= array[endIndex]) {
            // array[endIndex]보다 lower인 값 저장할 공간 확보를 위해 endOfLower++
            endOfLower++

            // array[i]와 array[endOfLower]의 값 서로 교환
            val temp = array[endOfLower]
            array[endOfLower] = array[i]
            array[i] = temp
        }
    }

    // array[endOfLower] 바로 뒤에 array[endIndex] (= 기준) 값이 오게 하기 위해서 endOfLower++
    endOfLower++

    // array[endIndex]과 array[endOfLower]의 값 서로 교환
    val temp = array[endOfLower]
    array[endOfLower] = array[endIndex]
    array[endIndex] = temp

    return endOfLower
}

 

#3 요약

퀵 정렬은 한번 수행될 때마다 기준 원소 하나를 정렬한다.

 

#4 이 개념이 사용된 글

28417 - 스케이트보드