We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Quicksort 2 - Sorting
  2. Discussions

Quicksort 2 - Sorting

  • michaelchen0611
     + 0 comments
    • Time Complexity: O(nlog(n))
    • Space Complexity: O(n)
    • Note: the relative order of the array must remain unchange. That is {4,2,1,6,5} -> {2,1,4,6,5}
    void printf_arr(int* arr, int l, int r){
    for (int i = l; i<(r+1); i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Note: The order of the array must remain unchanged
int partition(int* arr, int l, int r){
    int* res_arr = (int* )malloc((r+1)*sizeof(int));
    int pivot = arr[l];
    int ptr = l, idx = l;
    for (int i = l; i<(r+1); i++){
        if (arr[i] < pivot) res_arr[ptr++] = arr[i];
    }
    idx = ptr;
    res_arr[ptr++] = pivot;
    for (int i = l; i<(r+1); i++){
        if (arr[i] > pivot) res_arr[ptr++] = arr[i];
    }
    for (int i = l; i<ptr; i++){
        arr[i] = res_arr[i];
    }
    free(res_arr); 
    return idx;
}

void my_quick_sort(int* arr, int l, int r){
    if (l < r){
        int idx = partition(arr, l, r);
        my_quick_sort(arr, l, idx-1);
        my_quick_sort(arr, idx+1, r);
        printf_arr(arr, l, r);
    }
}

void quickSort(int ar_size, int *ar) {
	// Complete this function
    my_quick_sort(ar, 0, ar_size-1);
}