2

I can be considered new in Java . I ' ve been struggling with one question which was given to us by our professor in our school. I am supposed to make a natural merge sort algorithm which has to find two sorted sub-arrays everytime and merge them.(which is a version of bottom up merge sort). But i am stuck here is my code 

public class NaturalMergeMine {
  private static Comparable[] aux;

  public static void sort(Comparable[] a) {
    aux = new Comparable[a.length];
    sort(a, 0, a.length - 1);
  }

  public static boolean isSorted(Comparable[] a) {
    for (int i = 1; i < a.length; i += 1) {
      if (a[i - 1].compareTo(a[i]) < 0) {
        return false;
      }
    }
    return true;
  }

  private static void sort(Comparable[] a, int lo, int hi) {
    int i = lo;
    int j = 0;
    int mid = 0;
    int az = 0;

    while (true) {
      i = 0;
      System.out.println("outter");
      while (i < a.length) {
        System.out.println("inner 1");
        if (i == a.length - 1) {
          break;
        } else if (a[i].compareTo(a[i + 1]) < 0) {
          break;
        }
        i++;
      }

      j = i + 1;

      while (j < a.length) {
        System.out.println("inner 2");
        if (j == a.length - 1) {
          break;
        } else if (a[j].compareTo(a[j + 1]) < 0) {
          break;
        }
        j++;
      }
      mid = lo + (j - lo) / 2;
      Merge(a, lo, mid, j);
      lo = 0;

      if (isSorted(a)) {
        break;
      }
    }
  }

  public static void Merge(Comparable[] a, int lo, int mid, int hi) {
    int i = lo;
    int j = mid + 1;

    for (int k = lo; k <= hi; k++) {
      aux[k] = a[k];
    }

    for (int k = lo; k <= hi; k++) {
      if (i > mid) {
        a[k] = aux[j++];
      } else if (j > hi) {
        a[k] = aux[i++];
      } else if (aux[i].compareTo(aux[j]) < 0) {
        a[k] = aux[j++];
      } else {
        a[k] = aux[i++];
      }
    }
  }

  public static void show(Comparable[] a) {
    for (int i = 0; i < a.length; i++) {
      System.out.print(a[i] + " ");
    }
  }

  public static void main(String[] args) {
    Integer[] arr = {6, 4, 5, 7, 8, 3, 2, 1};
    sort(arr);
    show(arr);
  }
}

what happens is that it is not merging correctly and it goes in an infinite loop in the outter loop ,which is because it is not sorted properly. Is there anyone who can advice me a better way or can tell me the mistake i make here. Thanks in advance.

Improve this question

2 Answers 2

Reset to default
1

The issue is in the mid calculation, im not quite sure why you do that,but if the mid is less than i in you merge method you wont reach the fault case so you will stuck in discovering it without solving, for each run you need to pick up two arrays to sort, so instead of mid you can insert i to the merge method so you start the merging from the fault in.

 public class NaturalMergeMine {
private static Comparable[] aux;

 public static void sort(Comparable[] a) {
  aux = new Comparable[a.length];
  sort(a, 0, a.length - 1);
}

 public static boolean isSorted(Comparable[] a) {
   for (int i = 1; i < a.length; i += 1) {
     if (a[i - 1].compareTo(a[i]) > 0) {//changed operator to greater than
      return false;
    }
  }
  return true;
}

private static void sort(Comparable[] a, int lo, int hi) {
  int i = lo;
  int j = 0;
  int mid = 0;
  int az = 0;

  while (true) {
   i = 0;
    System.out.println("outter");
    while (i < a.length) {
     System.out.println("inner 1");
     if (i == a.length - 1) {
       break;
      } else if (a[i].compareTo(a[i + 1]) > 0) {//changed operator to greater than
       break;
      }
      i++;
    }

    j = i + 1;

    while (j < a.length) {
    System.out.println("inner 2");
    if (j == a.length - 1) {
      break;
    } else if (a[j].compareTo(a[j + 1]) > 0) {//changed operator to greater than
      break;
    }
    j++;
  }
 //      mid = lo + (j - lo) / 2;
  Merge(a, lo, i, j);
  lo = 0;

  if (isSorted(a)) {
    break;
  }
 }
}

public static void Merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo;
int j = mid + 1;

for (int k = lo; k <= hi; k++) {
  aux[k] = a[k];
}

for (int k = lo; k <= hi; k++) {
  if (i > mid) {
    a[k] = aux[j++];
  } else if (j > hi) {
    a[k] = aux[i++];
  } else if (aux[i].compareTo(aux[j]) > 0) {//changed the operator to greater than
    a[k] = aux[j++];
  } else {
    a[k] = aux[i++];
  }
 }
 }

  public static void show(Comparable[] a) {
   for (int i = 0; i < a.length; i++) {
    System.out.print(a[i] + " ");
   }
  }

 public static void main(String[] args) {
  Integer[] arr = {6, 4, 5, 7, 8, 3, 2, 1};
  sort(arr);
  show(arr);
  }
 }
Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

Thank you, but isn't this one the normal implementation of top down merge sort. What i have problem with is to find the 2 sorted subarrays and as soon as I find them I should merge them. And this might not exactly be the half of the array.
This is the standard merge sort algorithm, not the natural merge sort algorithm. OP stated clearly that the problem resides within the merge-part. If you found and corredted some kind of bug in this part, it would be beneficial if you explain the changes in detail.
Actually I ve implemented the merge method in the standard merge sort algorithm and it worked correctly. I ve used the same merge method here. The only part that I changed in the code that I wrote above is sort(Comparable [] a, int lo.....) method. But it doesnt do what i initially desired.
Sorry my bad , i missed the natural, i will edit the answer
Thank you , but after doing what you said. It sorted the array in descending order. Which is exactly opposite of what I wanted to do.
|
1

Amer Qarabsa's answer fixes the problems with the original code. Below are some alternate examples that are a bit more optimized, scanning the array for pairs of ascending sequences, rather than starting over at the beginning each time. If the array was reversed, then the first pass creates runs of 2, the next pass runs of 4, ... . With the original version, the run size would only increase by one on each loop. The example code below uses open intervals (last index is end of array instead of last element of array).

public class jsortns {
    private static Comparable[] aux;

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        int i;
        int j;
        int k;
        while (true) {                  // merge pass
            i = 0;
            while(true) {               // find, merge pair of runs
                j = i;                  // find left run
                while (++j < a.length) {
                    if (a[j-1].compareTo(a[j]) > 0)
                        break;
                }
                if(j == a.length){      // if only one run left
                    if(i == 0)          //   if done return
                        return;
                    else                //   else end of merge pass
                        break;
                }
                k = j;                  // find right run
                while (++k < a.length) {
                    if (a[k-1].compareTo(a[k]) > 0){
                        break;
                    }
                }
                Merge(a, i, j, k);      // merge runs
                i = k;
                if(i == a.length)       // if end of merge pass, break
                    break;
            }
        }
    }

    // merge left and right runs
    // ll = start of left run
    // rr = start of right run == end of left run
    // ee = end of right run
    public static void Merge(Comparable[] a, int ll, int rr, int ee) {
        int i = ll;
        int j = rr;
        int k;
        for (k = ll; k < ee; k++)
            aux[k] = a[k];
        k = ll;
        while(true){
            // if left element <= right element
            if (aux[i].compareTo(aux[j]) <= 0) {
                a[k++] = aux[i++];      // copy left element
                if(i == rr){            // if end of left run
                    while(j < ee)       //   copy rest of right run
                        a[k++] = aux[j++];
                return;                 //   and return
                }
            } else {
                a[k++] = aux[j++];      // copy right element
                if(j == ee){            // if end of right run
                    while(i < rr){      //   copy rest of left run
                        a[k++] = aux[i++];
                    }
                return;                 //   and return
                }
            }
        }
    }

No copy back version, instead merges back and forth between two arrays, and only copies at the end if the sorted data ends up in the wrong array.

public class jsortns {
    private static Comparable[] b;      // temp array
    private static Comparable[] o;      // original array reference
    private static Comparable[] t;      // used to swap a, b

    public static void sort(Comparable[] a) {
        o = a;                          // save ref to a
        b = new Comparable[a.length];   // allocate temp array
        int i;
        int j;
        int k;
        while (true) {                  // merge pass
            i = 0;
            while(true) {               // find, merge pair of runs
                j = i;                  // find left run
                while (++j < a.length) {
                    if (a[j-1].compareTo(a[j]) > 0)
                        break;
                }
                if(j == a.length){      // if only one run left
                    if(i != 0){         //   if not done
                        while(i < j){   //     copy run to b
                            b[i] = a[i];
                            i++;
                        }
                        break;          //   break to end merge pass
                    } else {            // else sort done
                        if(a != o){     //   if a not original a, copy
                            for(i = 0; i < a.length; i++)
                                b[i] = a[i];
                        }
                        return;
                    }
                }
                k = j;                  // find right run
                while (++k < a.length) {
                    if (a[k-1].compareTo(a[k]) > 0){
                        break;
                    }
                }
                Merge(a, b, i, j, k);   // merge left, right into b
                i = k;
                if(i == a.length)       // break if end pass
                    break;
            }
            t = a;                      // swap a and b (references)
            a = b;
            b = t;
        }
    }

    // merge left and right runs from a[] to b[]
    // ll = start of left run
    // rr = start of right run == end of left run
    // ee = end of right run
    public static void Merge(Comparable[] a, Comparable[] b, int ll, int rr, int ee) {
        int i = ll;
        int j = rr;
        int k = ll;
        while(true){
            // if left element <= right element
            if (a[i].compareTo(a[j]) <= 0) {
                b[k++] = a[i++];        // copy left element
                if(i == rr){            // if end of left run
                    while(j < ee)       //   copy rest of right run
                        b[k++] = a[j++];
                return;                 //   and return
                }
            } else {
                b[k++] = a[j++];        // copy right element
                if(j == ee){            // if end of right run
                    while(i < rr){      //   copy rest of left run
                        b[k++] = a[i++];
                    }
                return;                 //   and return
                }
            }
        }
    }
Improve this answer

1 Comment

Thank you so much . These perspectives of applying the algorithm and Amer Qarabsa's answer helped me solve the problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.