I want the code to be $1)$ in$-$place quicksort and $2)$ "Your algorithm should change the links of the simulated nodes $($blue numbers$).$ It is not allowed to modify the element of any node $($red numbers$).$ If the input is in the first row, the status after the sorting must be the second row

$(9$ blue$)(75$ red$)11(99$ red$)0($o red$)13(38$ red$)1(87$ red$)7(69$ red$)3($ o red$)0(5$red$)$

$(7$ blue$)(75$ red$)9(99$ red$)0($o red$)13(38$ red$)11(87$ red$)3(69$ red$)1($ o red$)0(5$ red$)"$

$3)$ also, do not remove anything from main, and other functions. You can modify but specify what changed. Focus on quicksort, partition, set value, getvalue, getnext.

It has to satisfy all the above. Thank you.

package comp$2011.$a$2$;

import java.util.Arrays;

import java.security.SecureRandom;

public class Main $\{$

private int$[]$ data;

int size;

public Main$($int n$)\{$

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

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

data$[0]=0$;

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$()\{$

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

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

int last $=$ first;

$//$ Find the last node

while $($data$[$last $+1]!=0)\{$

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

$\}$

quickSort$($this$,$ first, last$)$;

$\}$

$\}$

public void quickSort$($Main list, int start, int end$)\{$

if $($start $!=$ end && list.getNext$($start$)!=$ end$)\{//$ Base case

int pivotIndex $=$ partition$($list$,$ start, end$)$; $//$ Partition the list

quickSort$($list$,$ start, pivotIndex$)$; $//$ Sort left sub$-$list

quickSort$($list$,$ list.getNext$($pivotIndex$),$ end$)$; $//$ Sort right sub$-$list

$\}$

$\}$

public int partition$($Main list, int start, int end$)\{$

int pivotIndex $=$ start;

int pivotValue $=$ list.getValue$($pivotIndex$)$; $//$ Get the pivot value

int i $=$ pivotIndex; $//$ End of smaller values $($left partition$)$

int j $=$ list.getNext$($start$)$; $//$ Start iterating from the second node

while $($j $!=$ end$)\{$

if $($list$.$getValue$($j$)<=$ pivotValue$)\{$

$//$ Swap values at i$+1$ and j and move i forward

i $=$ list.getNext$($i$)$;

$//$ Swap values directly without the swapNodes method

int tempValue $=$ list.getValue$($i$)$; $//$ Temporarily store node$1$ value

list.setValue$($i$,$ list.getValue$($j$))$; $//$ Set node$1$ to node$2$ value

list.setValue$($j$,$ tempValue$)$; $//$ Set node$2$ to node$1$ value

$\}$

j $=$ list.getNext$($j$)$; $//$ Move to the next node

$\}$

int tempValue $=$ list.getValue$($pivotIndex$)$; $//$ Temporarily store pivot value

list.setValue$($pivotIndex$,$ list.getValue$($i$))$; $//$ Set pivot index to value at i

list.setValue$($i$,$ tempValue$)$; $//$ Set i to pivot value

return i; $//$ Return the index of the pivot after partition

$\}$

public int getValue$($int index$)\{$

return data$[$index$]$;

$\}$

public void setValue$($int index, int value$)\{$

data$[$index$]=$ value;

$\}$

public int getNext$($int index$)\{$

return data$[$index $+1]$;

$\}$

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 $=\{$

$\{\},$

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

Main list $=$ new Main$($n $+$ random.nextInt$(1+($n $<<2)))$;

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

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

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!

Q:

*****I posted the completed code for part 1**** Help me with part 2 at the bottom. Can you please write a code Java for the LQHashed class SP2017LAB6_LQHashedDataStructure_yourLastName OBJECTIVES...

Q:

please help me with this as my tutor fell through and I dont understand all sections these are the programs it gave me this is the main java above this is the grade book reader above these are the...

Q:

re Regular Languages and Finite Automata (a) Let L be the set of all strings over the alphabet {a, b} that end in a and do not contain the substring bb. Describe a deterministic finite automaton...

Q:

Developments in Technology Light is incident from air on the end face of a multimode optical fibre at angle of incidence as shown below. n n 1 2 The refractive indices of the core and cladding are...

Q:

Subaru Motors Corporation (SMC) today announced plans to revise its organisational structure. The changes will see the company's structure slim down from 230 departments to 131, which will hopefully...

Q:

Assessment 1 - Case study For this assessment you are going to use the 'simulated 'business: 'Blue fish grill.' Please download the copy of the customer service policies and procedures manual that...

Q:

) Explain the term overloading in the context of Java constructors and methods. [2 marks] (b) Without describing the details of either, outline the relationship between the Java methods...

Q:

need the code in c language MacBook Pro Abstract: Due March 1 or is computing involves 10 directly at point. This is in essence processor is generating its en enerating its values to computer e lri n...

Q:

Needs to be done in C++ 2020 Winter CIS 450 Programming Assignment 1 Job Scheduler Assignment date: January 13, 2020 Due: Part 1 January 22, 2020 Part 2: Janaury 29, 2020 Overview: This programming...

Q:

Question 8 0 / 1 point Given the code snippet below, what methods does an object of the Rectangle class have? class GeometricShape : def __init__(self, x, y) : self._x = x self._y = y self._fill =...

Q:

Describe how the project integration of interrelated actions and activities outlined in the process groups and knowledge area can help bring project success Identify the project scope statement...

Q:

Sept 15 10 000 shares of treasure stock reissued at 11 per share Oct 31 Declared 10 stock dividend for common stock traded at 8 Dec 31 The preferred dividend is declared and a common dividend of 50...

Q:

4 Consider two products with the same margins but with different salvage values. Which product should have a higher service level, and why?

Q:

Carefully study the following Income Statement and Statement of Balance Sheet for Obaa Yaa & Daughters Co. Ltd. for the year 2013 and answer questions 84 through 91. You are required to show how you...

Previous Question Next Question