HackerRank | Sorting - Quicksort 1

質問する

https://www.hackerrank.com/challenges/quicksort1/problem
与えられた配列の最初の要素をpivot(金俊秀)とし、pivotより小さい数をpivotの左側に、pivotより大きい数を右側に、配列をソートする.

問題を解く

まずpivotを配列の最初の要素として指定し,pivotの左側はi,右側はjである.

新しいレイアウトbrrを動的に割り当て、ここではpivotを基準に既存のレイアウトをソートします.

i 0から、jはarr count-1として指定される.
左に個数iを足すと1が増加し、右に個数jを足すと1が増加する.

配列arrのインデックスkを1からarr count-1に増やし、arr[k]がpivotのサイズを比較する
後小はbrr[i+]に格納され、大はbrr[j--]に格納される.

コード#コード#

int* quickSort(int arr_count, int* arr, int* result_count) {
    int pivot = arr[0], i = 0, j = arr_count-1;
    int *brr = (int *)malloc(sizeof(int)*arr_count);
    for(int k=1;k<arr_count; k++){
        if(arr[k]<pivot)
            brr[i++]=arr[k];
        else
            brr[j--] = arr[k];
    }
    brr[i] = pivot;
    *result_count=arr_count;
    return brr;
}

結果