[HackerRank] Find the Median

# Find the Median (Sorting)

[문제]

 

[코드]

void quickSort(vector<int>* arr, int start, int end){
    int pivot = (*arr)[start], temp;
    int left = start+1, right = end;
    
    if(left < right)
    {
        while(left <= right)
        {
            while((*arr)[left] <= pivot && left <= end) left++;
            while((*arr)[right] > pivot && right >= start) right--;
            if(left <= right)
            {
                temp = (*arr)[left];
                (*arr)[left] = (*arr)[right];
                (*arr)[right] = temp;
            }
            else
            {
                temp = (*arr)[right];
                (*arr)[right] = pivot;
                (*arr)[start] = temp;
            }  
        }
        quickSort(arr, start, right-1);
        quickSort(arr, right+1, end);
    }
}

int findMedian(vector<int> arr) {
    quickSort(&arr, 0, arr.size()-1);
    return arr[arr.size()/2];
}

 

[코드설명]

요소의 개수가 홀수인 정수 리스트의 중간값을 구하는 문제다.

quick sort로 정수 리스트를 정렬하였다.

요소의 개수가 홀수이므로 중간값은 마지막 인덱스(n-1)를 2로 나눈 인덱스에 위치한다.

 

quick sort는 pivot을 정해서 pivot보다 큰 수와 작은 수를 판별하여 정렬하는 알고리즘이다.

divide and conquer 방식으로, 정렬한 리스트에서 pivot을 기준으로 sub list로 나누어서 또 정렬한다.

 

 

[채점 결과]