[HackerRank_C] Quicksort1 - partition

자료구조 복습용 sorting 문제입니다.

-문제

Quicksort 1 - Partition | HackerRank

퀵 정렬을 할 때, pivot을 arr[0]으로 사용하여 left, equal, right을 분류하고 그 리스트를 반환한다.

작동하는 원리

---

- 풀이

int* quickSort(int arr_count, int* arr, int* result_count) {
    int *result = (int*)malloc(sizeof(int)*arr_count);
    int *left = (int*)malloc(sizeof(int)*arr_count);
    int *equal = (int*)malloc(sizeof(int)*arr_count);
    int *right = (int*)malloc(sizeof(int)*arr_count);
    int pivot = arr[0], left_pos = 0, equal_pos = 0, right_pos = 0, result_pos = 0;
    
    for(int i=0; i<arr_count; i++){
        if(arr[i]>pivot)
            *(right + right_pos++) = arr[i];  
        
        else if(arr[i]<pivot)
            *(left + left_pos++) = arr[i];
        
        else 
            *(equal + equal_pos++) = arr[i];
        
    }
    
    for(int i=0; i<left_pos; i++)
        *(result + result_pos++) = left[i];
    for(int i=0; i<equal_pos; i++)
        *(result + result_pos++) = equal[i];
    for(int i=0; i<right_pos; i++)
        *(result + result_pos++) = right[i];
        
    *result_count = result_pos;    
    return result;
}

1. arr_count 크기 만큼 left, equal, right, result 배열을 만들어 준다.
2. arr_count 크기만큼 for문을 실행하는데 만약 pivot이 더 크다면 right, 작다면 left, 같다면 equal 배열에 arr[i]값을 넣는다.
3. result에 left, equal, right 순서로 값을 넣어주고, result_count에 result_pos 값을 넣어준다. (이후 프린트에 사용)

---

- 실행결과