How would you write this without the help of any packages ? (same layout where mergeSort(int[] A) (take input of one array) and same with merge(int[] a, int[] l, int[] r)). Main issue is transalting Arrays.copyOfRange into the non -package version of java into this code. Thank you for answering this question.
Another question of mine would be of how to implelment a merge function with 3 arrays this time in its parameters.
this is code i tried:
public static int[] mergeArrays3(int[] a, int[] b, int[] c) {
int[] result = new int[a.length b.length c.length];
int i = 0, j = 0, k = 0, l=0;
while(i<a.length &&j<b.length && l<c.length)
{
// if (b[i] < a[j] || b[i] <c[i]) {
// result[k] = c[i];
// j ;
// }
if (c[i] < b[j] || c[i] <a[i]) {
result[k] = c[i];
l ;
}
if (a[i] < b[j] || a[i] <c[i]) {
result[k] = a[i];
i ;
}
else {
result[k] = b[j];
j ;
}
k ;
}
while(i<a.length)
{
result[k] = a[i];
i ;
k ;
}
while(j<b.length)
{
result[k] = b[j];
j ;
k ;
}
while(l<c.length)
{
result[k]=c[l];
l ;
k ;
}
return result;
}
```
import java.io.*;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) throws IOException{
BufferedReader R = new BufferedReader(new InputStreamReader(System.in));
int arraySize = Integer.parseInt(R.readLine());
int[] inputArray = new int[arraySize];
for (int i = 0; i < arraySize; i ) {
inputArray[i] = Integer.parseInt(R.readLine());
}
mergeSort(inputArray);
for (int j = 0; j < inputArray.length; j ) {
System.out.println(inputArray[j]);
}
}
static void mergeSort(int[] A) {
if (A.length > 1) {
int q = A.length/2;
//changed range of leftArray from 0-to-q to 0-to-(q-1),how would you edit Arrays.copyOfRange to manually make the same function without using any packages?
*int[] leftArray = Arrays.copyOfRange(A, 0, q-1);
//changed range of rightArray from q-to-A.length to q-to-(A.length-1)
int[] rightArray = Arrays.copyOfRange(A,q,A.length-1);*
mergeSort(leftArray);
mergeSort(rightArray);
merge(A,leftArray,rightArray);
}
}
static void merge(int[] a, int[] l, int[] r) {
int totElem = l.length r.length;
//int[] a = new int[totElem];
int i,li,ri;
i = li = ri = 0;
while ( i < totElem) {
if ((li < l.length) && (ri<r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i ;
li ;
}
else {
a[i] = r[ri];
i ;
ri ;
}
}
else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i ;
ri ;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li ;
i ;
}
}
}
}
//return a;
}
}
CodePudding user response：
This method not so fast as Arrays.copyOfRange and it not covers all cases, such as negative indexes, it is necessary to check also for size
private static int[] copyArray(int[] original, int from, int to) {
int [] res = new int[to-from];
for (int i = from; i< to; i ) {
res[i - from] = original[i];
}
return res;
}
CodePudding user response：
Top down merge sort with for loop for a one time array copy and alternating parameters to change direction of merge with each level of recursion. MergeSort is entry function that allocates and copies to a second array. MergeSortR is recursive function. Merge is never called unless all 3 sub-arrays have at least one element. It would be a bit more efficient to use nested if else, so that a maximum of 2 compares are used to determine the smallest element, but that will duplicate code for one of the cases. If this was a 4 way merge, there would be duplicate code for all four cases (with C | C , goto can be used to use common code instead of duplicate code).
static void MergeSort(int[] a)
{
if(a.length < 2) // if < 2 elements, nothing to sort
return;
int [] b = new int[a.length]; // b[] = a[] | int[]b = a.clone();
for(int i = 0; i < a.length; i )
b[i] = a[i];
MergeSortR(b, a, 0, a.length); // sort b[] to a[]
}
static void MergeSortR(int[] b, int[] a, int bb, int ee)
{
if(ee - bb < 2) // if < 2 elements, nothing to sort
return;
if(ee - bb == 2){ // if 2 elements
if(a[bb] > a[bb 1]){
int t = a[bb];
a[bb] = a[bb 1];
a[bb 1] = t;
}
return;
}
int m1 = bb (ee 0-bb)/3; // split into 3 parts
int m2 = m1 (ee 1-bb)/3;
MergeSortR(a, b, bb, m1); // sort a[] to b[]
MergeSortR(a, b, m1, m2);
MergeSortR(a, b, m2, ee);
Merge(b, a, bb, m1, m2, ee); // merge b[] to a[]
}
static void Merge(int[] a, int[] b, int bb, int m1, int m2, int ee)
{
int b0 = bb; // b[] index
int a0 = bb; // a[] indexes
int a1 = m1;
int a2 = m2;
while(true){ // 3 way merge
// if a[a0] is smallest
if(a[a0] <= a[a1] && a[a0] <= a[a2]){
b[b0] = a[a0];
b0 ;
a0 ;
if(a0 < m1) // if not end of run
continue; // continue
a0 = a1; // else setup for 2 way merge
a1 = a2;
m1 = m2;
m2 = ee;
break;
}
// if a[a1] is smallest
if(a[a1] <= a[a2]){
b[b0] = a[a1];
b0 ;
a1 ;
if(a1 < m2) // if not end of run
continue; // continue
a1 = a2; // else setup for 2 way merge
m2 = ee;
break;
}
// else a[a2] is smallest
else {
b[b0] = a[a2];
b0 ;
a2 ;
if(a2 < ee) // if not end of run
continue; // continue
break; // else setup for 2 way merge
}
}
while(true){ // 2 way merge
if(a[a0] <= a[a1]){
b[b0] = a[a0];
b0 ;
a0 ;
if(a0 < m1) // if not end of run
continue; // continue
a0 = a1; // else setup for copy
m1 = m2;
break;
}else{
b[b0] = a[a1];
b0 ;
a1 ;
if(a1 < m2) // if not end of run
continue; // continue
break; // else setup for copy
}
}
while(true){ // 1 way "merge"
b[b0] = a[a0]; // copy rest of remaining run
b0 ;
a0 ;
if(a0 < m1)
continue;
break;
}
}