$//$Partitions the list taking the first element as the pivot

$$ static Node partition$($Node head, Node tail$)\{$

$//$Select the first node as the pivot node

$$ Node pivot $=$head;

$//\text{'}$pre$\text{'}$ and 'curr' are used to shift all

$//$smaller nodes' data to the left side of the pivot node

$$ Node pre $=$head;

$$ Node curr $=$head;

$//$Traverse the list until you reach the node after the tail

$$ while $($curr $!=$tail$.$next$)\{$

$//$If current node's data is less than the pivot's data

$$ if $($curr$.$data $<$pivot$.$data$)\{$

$$ int temp $=$curr$.$data;

$$ curr.data $=$pre$.$next.data;

$$ pre.next.data $=$temp;

$//$Move 'pre' to the next node

$$ pre $=$pre$.$next;

$\}$

$//$Move 'curr' to the next node

$$ curr $=$curr$.$next;

$\}$

$//$Swap the pivot's data with 'pre' data

$$ int currData $=$pivot$.$data;

$$ pivot.data $=$pre$.$data;

$$ pre.data $=$currData;

$//$Return 'pre' as the new pivot

$$ return pre;

$\}$

$//$Helper function for quick sort

$$ static void quickSortHelper$($Node head, Node tail$)$

$//$Base case: if the list is empty or consists of a single node

$$ if $($head $==$null $||$head $==$tail$)\{$

$$ return;

$\}$

$//$Call partition to find the pivot node

$$ Node pivot $=$partition$($head$,$tail$)$;

$//$Recursive call for the left part of

$//$the list $($before the pivot$)$

$$ quickSortHelper$($head$,$pivot$)$;

$//$Recursive call for the right part of

$//$the list $($after the pivot$)$

$$ quickSortHelper$($pivot$.$next, tail$)$;

$\}$

$//$The main function for quick sort.

$//$This is a wrapper over quickSortHelper

$$ static Node quickSort$($Node head$)\{$

$//$Find the tail of the list

$$ Node tail $=$getTail$($head$)$

$//$Call the helper function to sort the list

$$ quickSortHelper$($head$,$tail$)$;

$$ return head;

$\}$

In the previous answers, it doesn't work for my test data it only check empty and $1,1,1,1,...$ That is basically not doing anything...Please do the question properly. Also, $$Please only focus on quicksort, partition, and getNextIndex. You can modify other class but try not too and do not delete any lines from other classes. BUT please don't just copy my code. rewrite it in your own way.

$1.$use above code as reference to change the below code. $2."$Algorithm should change the links of the simulated nodes It is not allowed to modify the element of any node." $3.$Also$,$has to be in$-$place quicksort.

import java.util.Arrays;

import java.security.SecureRandom;

public class ListOnArray$\_23100448$d$\_$UNGSethyPagna $\{$

private int$[]$ data;

int size;

public ListOnArray$\_23100448$d$\_$UNGSethyPagna$($int n$)\{$

size $=($n $+1)<<1$;

data $=$ new int$[$size$]$;

data$[0]=0$; $//$ may be omitted in Java.

for $($int i $=2$; i $<$ size $-2$; i $+=2)$

data$[$i$]=$ i $+1$;

data$[$size $-1]=1$;

data$[$size $-2]=0$;

$\}$

public boolean isEmpty$()\{$

return data$[0]==0$;

$\}$

public boolean isFull$()\{$

return data$[$size $-1]==0$;

$\}$

public void err$()\{$

System.out.println$("$Oops$...")$;

$\}$

public void insertFirst$($int x$)\{$

if $($isFull$())\{$ err$()$; return; $\}$

int i $=$ data$[$size $-1]$;

data$[$size $-1]=$ data$[$i $+1]$;

data$[$i $+1]=$ data$[0]$;

data$[0]=$ i;

data$[$i$]=$ x;

$\}$

public void quicksort$()\{$

public void quickSort$($ListOnArray$\_23100448$d$\_$UNGSethyPagna list, int start, int end$)\{$

public int partition$($ListOnArray$\_23100448$d$\_$UNGSethyPagna list, int start, int end$)\{$

public String toString$()\{$

if $($isEmpty$())$ return "The list is empty.";

StringBuilder sb $=$ new StringBuilder$()$;

int i $=$ data$[0]$;

sb$.$append$($data$[$i$++])$;

while $($data$[$i$]!=0)\{$

i $=$ data$[$i$]$;

sb$.$append$("->").$append$($data$[$i$++])$;

$\}$

return sb$.$append$(\text{'}\backslash$u$2193\text{'}).$toString$()$;

$\}$

public static void main$($String$[]$ args$)\{$

int$[][]$ testData $=\{//$ try different inputs.

$\{\},$

$\{1,1,1,1,1,1,1\},$

$\{10,8,-4,89,2,0,4,-19,200\},$

$\{5,4,3,2,1,1,0,0,-1\},$

$\{1,2,3,4,5,6,7,8,9,10,11\},$

$\{1,3,2,6,7,5,4,12,13,15,14,10,11,9,8\},$

$\{3,2,6,13,8,4,10,7,14,11,12,5,9\},$

$\{65,85,17,88,66,71,45,38,95,48,18,68,60,96,55\},$

$\{10,8,14,89,32,50,77,38\}$

$\}$;

for $($int$[]$ a : testData$)\{$

int n $=$ a$.$length;

SecureRandom random $=$ new SecureRandom$()$;

ListOnArray$\_23100448$d$\_$UNGSethyPagna list $=$ new ListOnArray$\_23100448$d$\_$UNGSethyPagna$($n $+$ random.nextInt$(1+($n $<<2)))$; $//$ you don't need to understand this line.

System.out.println$("$The original array: $"+$ Arrays.toString$($a$))$;

for $($int i $=$ n $-1$; i $>=0$; i$--)$ list.insertFirst$($a$[$i$])$;

System.out.println$("$The original list: $"+$ list$)$;

$//$ You can uncomment the following line to print out how the elements are stored

$//$System$.$out.println$("$The internal storage: $"+$ Arrays.toString$($list$.$data$))$;

list.quicksort$()$;

System.out.println$("$The sorted list: $"+$ list$)$;

$\}$

$\}$

$\}$