QUICK SORT

#include <iostream> 
#include <cstdio> 
using namespace std; 

struct Node 
{ 
    int data; 
    struct Node *next; 
}; 
void push(struct Node** head_ref, int new_data) 
{ 
    /* allocate node */
    struct Node* new_node; 
    new_node=(struct Node *)malloc(sizeof(struct Node));

    /* put in the data */
    new_node->data = new_data; 

    /* link the old list off the new node */
    new_node->next = (*head_ref); 

    /* move the head to point to the new node */
    (*head_ref) = new_node; 
} 
void printList(struct Node *node) 
{ 
    while (node != NULL) 
    { 
        printf("%d ", node->data); 
        node = node->next; 
    } 
    printf("\n"); 
} 
struct Node *getTail(struct Node *cur) 
{ 
    while (cur != NULL && cur->next != NULL) 
        cur = cur->next; 
    return cur; 
} 

struct Node *partition(struct Node *head, struct Node *end, 
                    struct Node **newHead, struct Node **newEnd) 
{ 
    struct Node *pivot = end; 
    struct Node *prev = NULL, *cur = head, *tail = pivot; 

    while (cur != pivot) 
    { 
        if (cur->data < pivot->data) 
        { 
            if ((*newHead) == NULL) 
                (*newHead) = cur; 

            prev = cur;  
            cur = cur->next; 
        } 
        else 
        { 
            if (prev) 
                prev->next = cur->next; 
            struct Node *tmp = cur->next; 
            cur->next = NULL; 
            tail->next = cur; 
            tail = cur; 
            cur = tmp; 
        } 
    } 
    if ((*newHead) == NULL) 
        (*newHead) = pivot; 
    (*newEnd) = tail; 

    return pivot; 
} 
struct Node *quickSortRecur(struct Node *head, struct Node *end) 
{ 
    // base condition 
    if (!head || head == end) 
        return head; 

    Node *newHead = NULL, *newEnd = NULL; 
    struct Node *pivot = partition(head, end, &newHead, &newEnd); 
    if (newHead != pivot) 
    { 
        // Set the node before the pivot node as NULL 
        struct Node *tmp = newHead; 
        while (tmp->next != pivot) 
            tmp = tmp->next; 
        tmp->next = NULL; 
        newHead = quickSortRecur(newHead, tmp); 
        tmp = getTail(newHead); 
        tmp->next = pivot; 
    } 
    pivot->next = quickSortRecur(pivot->next, newEnd); 

    return newHead; 
} 
void quickSort(struct Node **headRef) 
{ 
    (*headRef) = quickSortRecur(*headRef, getTail(*headRef)); 
    return; 
} 
int main() 
{ int t;scanf("%d",&t);
while(t--)
{
  int n;scanf("%d",&n);
  int x[n];
  for(int i=0;i<n;i++)scanf("%d",&x[i]);
  struct Node *a = NULL; 
  for(int i=n-1;i>=0;i--)
  push(&a,x[i]);
  quickSort(&a);
  printList(a); 
}
    return 0; 
} 

import java.util.*;
import java.io.*;
class QuickSort 
{ 
    int partition(int arr[], int low, int high) 
    { 
        int pivot = arr[high];  
        int i = (low-1); 
        for (int j=low; j<high; j++) 
        { 
            if (arr[j] < pivot) 
            { 
                i++; 
                int temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        } 
        int temp = arr[i+1]; 
        arr[i+1] = arr[high]; 
        arr[high] = temp; 

        return i+1; 
    } 
    void sort(int arr[], int low, int high) 
    { 
        if (low < high) 
        { 
            int pi = partition(arr, low, high); 
            sort(arr, low, pi-1); 
            sort(arr, pi+1, high); 
        } 
    } 

    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    } 

    public static void main(String args[]) 
    { Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
            int arr[]=new int[n];
            for(int i=0;i<n;i++)
            {
                arr[i] = sc.nextInt();
            }
        QuickSort ob = new QuickSort(); 
        ob.sort(arr, 0, n-1); 
        printArray(arr); }
    } 
}