All work needs to be done within the Sort method using recursion only. // (provi
ID: 3638837 • Letter: A
Question
All work needs to be done within the Sort method using recursion only.// (provided): This is essentially the algorithm of you merge
// from Assignment 1
// preconditions: 0 <= i <= j < k < A.length; A[i..j] is in sorted
// order and A[j+1..k] is in sorted order.
// postcondition: A[i..k] has been shuffled to be in sorted order.
//
// You must modify the algorithm of 'merge' from assignment 1. Instead
// of operating on two arrays A1 and A2, you are operating on two
// sections of A, namely, A[i..j] and A[j+1..k]. Merge these into
// a temporarily allocated array B of size k-i+1, and then copy
// its contents back into A[i..k] to meet the postcondition.
public static void merge(int [] A, int i, int j, int k)
{
int[] B = new int[k-i+1];
int counterA1 = i;
int counterA2 = j+1;
int counterB = 0;
// collate the two sorted sections until one of the counters runs
// off the end of its sorted section ...
while (counterA1 <= j && counterA2 <= k)
if (A[counterA1] < A[counterA2])
B[counterB++] = A[counterA1++];
else
B[counterB++] = A[counterA2++];
// while there are still elements of the first section to copy ...
while (counterA1 <= j)
B[counterB++] = A[counterA1++];
// while there are still elements of the second section to copy ....
// (There is a clever way to skip this step, if you also modify
// the next loop)
while (counterA2 <= k)
B[counterB++] = A[counterA2++];
// copy everything back from B to A[i..k]
counterB = 0;
int counterA = i;
while (counterA <= k)
A[counterA++] = B[counterB++];
}
// precondition: 0 <= i <= k < A.length
// postcondition: A[i..k] has been sorted
//
// Notice that once again, a looser precondition means a more
// more general and useful method.
//
// We can't use 'merge' on it, since it A[i..k] doesn't necessarily
// meet its preconditions. However, if we let j = (i+k)/2 (integer
// arithmetic), then somehow got A[i..j] and A[j+1..k] into sorted
// order, we would now meet the precondition of merge(A,i,j,k).
public static void Sort(int [] A, int i, int k)
{
}
Explanation / Answer
All work needs to be done within the Sort method using recursion only.
// (provided): This is essentially the algorithm of you merge
// from Assignment 1
// preconditions: 0 <= i <= j < k < A.length; A[i..j] is in sorted
// order and A[j+1..k] is in sorted order.
// postcondition: A[i..k] has been shuffled to be in sorted order.
//
// You must modify the algorithm of 'merge' from assignment 1. Instead
// of operating on two arrays A1 and A2, you are operating on two
// sections of A, namely, A[i..j] and A[j+1..k]. Merge these into
// a temporarily allocated array B of size k-i+1, and then copy
// its contents back into A[i..k] to meet the postcondition.
public static void merge(int [] A, int i, int j, int k)
{
int[] B = new int[k-i+1];
int counterA1 = i;
int counterA2 = j+1;
int counterB = 0;
// collate the two sorted sections until one of the counters runs
// off the end of its sorted section ...
while (counterA1 <= j && counterA2 <= k)
if (A[counterA1] < A[counterA2])
B[counterB++] = A[counterA1++];
else
B[counterB++] = A[counterA2++];
// while there are still elements of the first section to copy ...
while (counterA1 <= j)
B[counterB++] = A[counterA1++];
// while there are still elements of the second section to copy ....
// (There is a clever way to skip this step, if you also modify
// the next loop)
while (counterA2 <= k)
B[counterB++] = A[counterA2++];
// copy everything back from B to A[i..k]
counterB = 0;
int counterA = i;
while (counterA <= k)
A[counterA++] = B[counterB++];
}
// precondition: 0 <= i <= k < A.length
// postcondition: A[i..k] has been sorted
//
// Notice that once again, a looser precondition means a more
// more general and useful method.
//
// We can't use 'merge' on it, since it A[i..k] doesn't necessarily
// meet its preconditions. However, if we let j = (i+k)/2 (integer
// arithmetic), then somehow got A[i..j] and A[j+1..k] into sorted
// order, we would now meet the precondition of merge(A,i,j,k).
public static void Sort(int [] A, int i, int k)
{
int mid;
if(k>i)
{
mid=(i+k)/2
Sort(A,i,m); //sort the left half
Sort(A,m+1,k); //sort the right half
merge(A, i,mid+1, k); // merge the 2 halfs
}
}