Note: Please check my quicksort functions. I think the error is because I didn't consider insertFirst function, but it could be because of other errors.

$1.$ What I want is for you to make this code work. When running, the code must sort all the lists.

$2.$ IMPORTANT!! However, please mind that you ONLY change quicksort.

Do NOT remove any lines from other functions and main. ONLY quicksorts and partition.

package comp$2011.$a$2$;

import java.util.Arrays;

import java.security.SecureRandom;

$*$ Simulating a linked list with an array.

$*$

$*/$

public class ListOnArray$\_23123456$d$\_$GigiYimMingHay $\{$

private int$[]$ data;

int size;

$/*$

$*$ The constructor is slightly different to Lab $5.$

$*$ But the difference is irrevalent to the task.

$*/$

public ListOnArray$\_23123456$d$\_$GigiYimMingHay$($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$...")$;

$\}$

$/*$

$*$ Insert a new element as the new head of the list.

$*/$

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;

$\}$

$/**$

$*$ The $*$in$-$place$*$ quicksort algorithm.

$*$

$*$ VERY IMPORTANT.

$*$ I've sought help from the following Internet resources and books:

$*1.$

$*2.$

$*3.$

$*...$

$*$

$*$ Running time: O$().$

$*/$

public void quicksort$()\{$

if $(!$isEmpty$())\{$

quicksort$($data$,$ data$[0],$ data$[$size $-1]-1)$;

$\}$

$\}$

public void quicksort$($int $[]$ array, int start, int end$)\{$

if $($end$<=$ start$)$ return; $//$base case

int pivot $=$ partition$($array$,$ start, end$)$;

quicksort$($array$,$ start, end$)$;

quicksort$($array$,$ pivot$+1,$ end$)$;

$\}$

public static int partition$($int$[]$ array, int start, int end$)\{$

int pivot $=$ array $[$end$]$;

int i $=$ start $-1$;

for $($int j $=$ start; j $<=$ end $-1$; j$++)\{$

if$($array$[$j$]<$ pivot$)\{$

i$+=1$;

int temp $=$ array $[$j$]$;

array$[$i$]=$ array$[$j$]$;

array$[$j$]=$ temp;

$\}$else if $($array$[$j$]>=$ pivot$)$

return j$+=1$;

$\}$

i$+=1$;

int temp $=$ array$[$i$]$;

array$[$i$]=$ array$[$end$]$;

array$[$end$]=$ temp;

return i;

$\}$

$/*$

$*$ Output the elements stored in the list in order.

$*/$

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$()$;

$\}$

$/*$

$*$ Todo: add at least ten more test cases to test your code.

$*$ Todo: modify the list $($removing and adding elements$)$ and sort it again.

$*$

$*$ The use of data structures from Java libraries is allowed here and only here.

$*/$

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$\_23123456$d$\_$GigiYimMingHay list $=$ new ListOnArray$\_23123456$d$\_$GigiYimMingHay$($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$)$;

$\}$

$\}$

$\}$