• 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);
}

/* code in c */

include

include

include

include

include

void quickSort(int *ar, int size)

{

if(size > 1){

int temp, pivot = ar[0], ub = size-1;

for(int i = size-1; i >= 0; --i){

if(ar[i] >= pivot){

temp = ar[i];

int j = i;

while(j < ub){//Variation of Insertion Sorting

ar[j] = ar[j+1];

++j;

}

ar[ub--] = temp;

}

}

++ub;

quickSort(ar, ub);

quickSort(ar+ub+1, size-ub-1);

//Output

for(int i = 0; i < size; ++i){

printf("%d ", ar[i]);

}

printf("\n");

}

}

int main(void)

{

int N;

scanf("%d", &N);

int ar[N];

for(int i = 0; i < N; i++){

scanf("%d", &ar[i]);

}

quickSort(ar, N);

return 0;

}

In the previous challenge, you wrote a partition method to split an array into two sub-arrays, one containing smaller elements and one containing larger elements than a given number. This means you 'sorted' half the array with respect to the other half. Can you repeatedly use partition to sort an entire array?

Guideline In Insertion Sort, you simply went through each element in order and inserted it into a sorted sub-array. In this challenge, you cannot focus on one element at a time, but instead must deal with whole sub-arrays, with a strategy known as "divide and conquer".

When partition is called on an array, two parts of the array get 'sorted' with respect to each other. If partition is then called on each sub-array, the array will now be split into four parts. This process can be repeated until the sub-arrays are small. Notice that when partition is called on just one of the numbers, they end up being sorted.

Can you repeatedly call partition so that the entire array ends up sorted?

Print Sub-Arrays In this challenge, print your array every time your partitioning method finishes, i.e. whenever two subarrays, along with the pivot, are merged together.

The first element in a sub-array should be used as a pivot. Partition the left side before partitioning the right side. The pivot should be placed between sub-arrays while merging them. Array of length or less will be considered sorted, and there is no need to sort or to print them. Note Please maintain the original order of the elements in the left and right partitions while partitioning around a pivot element.

For example: Partition about the first element for the array A[]={5, 8, 1, 3, 7, 9, 2} will be {1, 3, 2, 5, 8, 7, 9}

Input Format There will be two lines of input:

• the size of the array
• the n numbers of the array Output Format Print every partitioned sub-array on a new line.

Constraints

Each number is unique.

Sample Input

7 5 8 1 3 7 9 2 Sample Output

2 3 1 2 3 7 8 9 1 2 3 5 7 8 9 Explanation This is a diagram of Quicksort operating on the sample array:

quick-sort diagram

python3

def QuickSort(p, arr):
    
    if len(arr) == 1:
        return arr
    
    left = list(filter(lambda x: x < p, arr))
    middle = list(filter(lambda x: x == p, arr))
    right = list(filter(lambda x: x > p, arr))
    
    if left :
        left = QuickSort(left[0], left)
        
    if right:
        right = QuickSort(right[0], right)
    
    print(*left, *middle, *right)
    return left + middle + right
    

def main():
    n = int(input())
    arr = list(map(int, input().split()))
    sorted_arr = QuickSort(arr[0], arr)
    
    
if __name__ == '__main__':
    main()

This solution is going crazy for me: I have tried like this

I have this code:

function processData(input) {
    //Enter your code here
    //left<p, right>p
    let ar;
    let p = input[0]
    let left = []
    let right = []


    if (input.length <= 1) return input
    else {

        for (let i = 1; i < input.length; i++) {
            if (input[i] > p) {
                right.push(input[i])
            } else {
                left.push(input[i])
            }
        }
  
        ar = [...processData(left.slice(0).filter((d) => d < p)), p, ...processData(right.slice(0).filter((d) => d > p))]
        
    }
    console.log(...ar)

    return ar

}



process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});


process.stdin.on("end", function () {
    processData(_input.replace(/\s+$/g, '').split('').map((num) => parseInt(num), 10));
});

And output is like this:

2 3
1 2 3
1 2 3 5 //How to get rid of this part
8 9 // and this part
1 2 3 5 7 8 9

if anybody knows please suggests me!!

`