[HackerRank C] Sorting : Quicksort 1 - Partition

arr[0]이 pivot이 되어 pivot보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 배열하는 문제다.

 

배열도 반환할 수 있다는 것을 새로 알게됐다.

int* quickSort(int arr_count, int* arr, int* result_count) {
    *result_count = arr_count;
    int *ret_a = (int*)malloc(arr_count * sizeof(int));
    int p = arr[0], i, flag=0;
    for(i=1; i<arr_count; i++){
        if(arr[i] < p){
            *(ret_a+flag) = arr[i];
            flag++;
        }
    }
    *(ret_a+flag) = p;
    for(i=1; i<arr_count; i++){
        if(arr[i] > p){
            flag++;
            *(ret_a+flag) = arr[i];
        }
    }
    return ret_a;
}

리턴을 위해 동적할당으로 배열을 하나 생성하고, 거기에 정렬된 값을 저장해준다.

효율적이지 않을 수 있지만, 마땅히 생각나는 방법이 없어 for문을 두 번 돌려 작은 값을 먼저 배열에 저장해주고, pivot값을 저장한 뒤 큰 값을 저장해주었다. flag로 배열의 위치를 저장해 빠지는 곳 없이 저장되도록 해주었다. for문을 한 번 돌려서 해결할 수 있는지 고민해봐야 할 것 같다.

 

작은 수를 저장할 때 원래 배열 값을 0으로 만들면 0이 아닌 나머지만 큰 값에 저장하면 되는게 아닐까 생각해봤는데, 이렇게 되면 배열 값 자체가 0일 때 오류가 난다는 것을 깨달았다. 그렇지만 테스트케이스는 통과한 것을 보아 이 테스트케이스 배열 값에 0은 없나보다.

int* quickSort(int arr_count, int* arr, int* result_count) {
    *result_count = arr_count;
    int *ret_a = (int*)malloc(arr_count * sizeof(int));
    int p = arr[0], i, flag=0;
    for(i=1; i<arr_count; i++){
        if(arr[i] < p){
            *(ret_a+flag) = arr[i];
            flag++;
            arr[i] = 0;
        }
    }
    *(ret_a+flag) = p;
    for(i=1; i<arr_count; i++){
        if(arr[i]){
            flag++;
            *(ret_a+flag) = arr[i];
        }
    }
    return ret_a;
}