Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Can you help me see what I am doing wrong in my code? public static int partition( int [] arr, int l, int r) {

image text in transcribed

image text in transcribed

Can you help me see what I am doing wrong in my code?

public static int partition(int [] arr, int l, int r)

{

int n = arr.length;

int [] left = new int [ (n+1)/2];

int [] right = new int [n - left.length];

l = left.length;

r = right.length;

int p = arr[l];

int i = l + 1;

int temp;

for(int j = l+1 ;j

{

if(arr[j]

{

temp = a[j];

arr[j] = arr[i];

arr[i] = temp;

i++;

}

temp = arr[l];

arr[l] = arr[i-1];

arr[i-1] = temp;

}

return (i-1); // report final pivot position

}

public static int quickSort (int [] arr, int l, int r)

{

int n = arr.length;

int [] left = new int [ (n+1)/2];

int [] right = new int [n - left.length];

l = left.length;

r = right.length;

if (l >= r) // 0- or 1-element subarray

{

return 0;

}

int i = choose(arr,l,r);

int temp = arr[l]; // make pivot first

arr[l] = arr[i];

arr[i] = temp;

int j = partition(arr,l,r);

int c = quickSort(arr, l, j-1);

int d = quickSort(arr, j+1, r);

}

public static int choose (int []arr, int l, int r)

{

return l;

}

public static void main(String[] arg)

{

int [] a = {2148,9058,7742,3153,6324,609, 7628,5469,7017,504 };

int n = a.length;

int [] left = new int [ (n+1)/2];

int [] right = new int [n - left.length];

int l = left.length;

int r = right.length;

int result = quickSort (a, 0, n);

System.out.println(result);

}

Partition Input: array A of n distinct integers, left and right endpoints ler e {1,2, ..., n} with l p do nothing swap A[j] and A[i] i:=i+1 // restores invariant swap A[l] and A[i 1] // place pivot correctly return - 1 // report final pivot position The Partition subroutine takes as input an array A but operates only on the subarray of elements A[4], ..., A[r], where l and r are given parameters. Looking ahead, each recursive call to QuickSort will be responsible for a specific contiguous subset of the original input array, and the parameters l and r specify the corresponding endpoints. QuickSort Input: array A of n distinct integers, left and right endpoints ler e {1, 2, ..., n}. Postcondition: elements of the subarray A[l], All + 1},..., A[r] are sorted from smallest to largest. if I >r then // 0- or 1-element subarray return i := ChoosePivot(A, l, r) // to-be-implemented swap A[l] and A[i] // make pivot first j := Partition(A, l,r) // j =new pivot position QuickSort(A, l, j - 1) // recurse on first part QuickSort(A, j +1,r) // recurse on second part

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Essential SQLAlchemy Mapping Python To Databases

Authors: Myers, Jason Myers

2nd Edition

1491916567, 9781491916568

Students also viewed these Databases questions

Question

What is meant by Career Planning and development ?

Answered: 1 week ago

Question

What are Fringe Benefits ? List out some.

Answered: 1 week ago