$1.$ Please check and fix error below:

Output:

The original array: $[]$ The original list: The list is empty. The sorted list: The list is empty. The original array: $[1,1,1,1,1,1,1]$ The original list: $1->1->1->1->1->1->1$ The sorted list: $1->1->1->1->1->1->1$ The original array: $[10,8,-4,89,2,0,4,-19,200]$ The original list: $10->8->-4->89->2->0->4->-19->200$ Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index $201$ out of bounds for length $46$ at ListOnArray$\_23123456$d$\_$GigiYimMingHay.quicksort$($Main$.$java:$56)$ at ListOnArray$\_23123456$d$\_$GigiYimMingHay.quicksort$($Main$.$java:$77)$ at ListOnArray$\_23123456$d$\_$GigiYimMingHay.quicksort$($Main$.$java:$51)$ at ListOnArray$\_23123456$d$\_$GigiYimMingHay.main$($Main$.$java:$113)$

$2.$ Note:

Here's the code. other classes don't need to be heavily changed as that is the default setting $!!!$

The tasks that I wrote were the quicksort and partitions. Check this part mainly.

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;

public ListOnArray$\_23123456$d$\_$GigiYimMingHay$($int n$)\{$

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

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

data$[0]=0$; $//$ Head index

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

data$[$i$]=$ i $+1$; $//$ Next pointers

data$[$size $-2]=0$; $//$ End of list

data$[$size $-1]=1$; $//$ Tail index

$\}$

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

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

$\}$

$\}$

private void quicksort$($int prevIndex, int headIndex$)\{$

if $($headIndex $==0||$ data$[$headIndex $+1]==0)$ return;

int pivotValue $=$ data$[$headIndex$]$;

int leftTail $=$ prevIndex;

int current $=$ data$[$headIndex $+1]$;

int last $=$ headIndex;

while $($current $!=0)\{$

if $($data$[$current$]<$ pivotValue$)\{$

int next $=$ data$[$current $+1]$;

data$[$current $+1]=$ data$[$leftTail $+1]$;

data$[$leftTail $+1]=$ current;

leftTail $=$ current;

current $=$ next;

$\}$ else $\{$

last $=$ current;

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

$\}$

$\}$

data$[$last $+1]=0$; $//$ Properly terminate the list for the last segment

quicksort$($prevIndex$,$ data$[$prevIndex $+1])$;

quicksort$($headIndex$,$ data$[$headIndex $+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$("").$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$()$;

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

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

list.quicksort$()$;

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

$\}$

$\}$

$\}$

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:

1 / 3 81% +] [G] Your objective is to implement the following three algorithms: From the list of quadratic time algorithms: Cocktail Sort From the list of linearithmic time algorithms: Quick Sort...

Q:

#include #include #include #include #define MAX_NAME_LENGTH 35 struct studentList { struct student *student; struct studentList *next; } *list = NULL; struct student { char name[MAX_NAME_LENGTH];...

Q:

The next exercise is based on this implemetation for an OrderedArrayList of integers: //Interface: ArrayListADT public interface ArrayListADT { //same as above, you already have it! } //Class:...

Q:

Question 1 (4 Sections) 100 points 95 mins This question concerns placing key values into hash tables using different probing/hashing techniques. First, run the following code cell to define the...

Q:

I need help with my C++ project. There's one part that I'm having trouble with and I don't know how to fix it. Develop a high-quality, object-oriented C++ program that performs a simulation using a...

Q:

Introduction Note: Circular Buffers are described in Section 5.2.4 of our textbook (p. 211). Please read that section before proceeding. An interesting, relatively straightforward data structure is...

Q:

string-input.txt Craig Dern Ford Goodman Macy int-input.txt 3 9 10 19 37 45 63 84 100 int-input2.txt 2 5 7 7 19 21 21 21 25 32 41 float-input.txt 3.1 9.6 10.3 19.3 37.3 45.9 63.5 84.5 100.7 This...

Q:

I need help with my Computer Science 2 project. Develop a high-quality, object-oriented C++ program that performs a simulation using a heap implementation of a priority queue. A simulation creates a...

Q:

Write the software for a list class called LinkedList that is contained in LinkedList.cpp that meets the following requirements: The LinkedList.h file is provided. Do not change any of the interfaces...

Q:

Write the software for a list class called LinkedList that is contained in LinkedList.cpp that meets the following requirements: The LinkedList.h file is provided. Do not change any of the interfaces...

Q:

Suppose that in Figure B = 0.6 T, the distance d = 0.4 m, and ? = 24o. Find the speed v and the angle ? if the particles are (a) Protons and (b) Deuterons Bout

Q:

You will construct a report of 2000 words of a product launch. (Eg; iphone 12 launch) Your report should include, how you select the target market, the prominent tools you plan to use in the...

Q:

Death benefits from a life insurance policy are normally considered to be: A . subject to attachments from the insured's creditors B . exempt from federal income tax C . subject to the cost recovery...

Q:

struggling company and where is it in the positioning matrix

Previous Question Next Question