6 Replies Latest reply: May 6, 2009 3:52 PM by 807588 RSS

    Sorting Alogrithm (Mergesort) fails to return sort.

    807588
      Hello,

      first I want to appologize if I've posted this post in the wrong section. Please correct this post, I will try not to do this in the future.

      I've a small assignment to implement a few sorting alogrithms for my university. My sorting alogrithms work, but however one fails to display the correct sorted answers on my console. But instead it gives me the same output as I've inputted.

      I've searched my code, but I couldn't find the cause of this. First of all there is only one sorting alogrithm with that issue. Third you can assume that mergSort(...) sorts the code perfectly, I've checked the answer it returned and it was the correct answer.

      Last of all: I may not edit Main.java.

      MergeSorteerder.java
      public class MergeSorteerder implements Sorteerder {
      
        public void sorteer(Dinges[] waarden) {
          // Vervang dit door je algoritme.
          // U moet hier code voor Mergesorteerder geven
             
             waarden = mergeSort(waarden);
      
        }
      Main.java
      import java.util.*;
      import java.io.*;
      
      public class Main {
      // Deze klasse is bedoeld om je in staat te stellen makkelijk je
      // sorteeralgoritmen uit te testen
      // U kunt naar U wenst deze file veranderen; U hoeft deze file niet in te
      // leveren
      
        public static void main(String [] args) throws Exception {
          DingesLezer lezer      = new GetalLezer();
          
      
      // Door hieronder sommige regels in commentaar te zetten kan je het testen tot
      // een of twee van de sorteeralgoritmen beperken
      
          // Probeer Bubble Sort uit
          System.out.println("Bubble Sort");
          Sorteerder  bubblesorteerder = new BubbleSorteerder();
          Dinges[] dingesrij = leesWaarden(lezer);
          bubblesorteerder.sorteer(dingesrij);
          printWaarden(dingesrij);
      
          // Probeer Insertion Sort uit
          System.out.println("Insertion Sort");
          Sorteerder  insertionsorteerder = new InsertionSorteerder();
          dingesrij = leesWaarden(lezer);
          insertionsorteerder.sorteer(dingesrij);
          printWaarden(dingesrij);
      
          // Probeer Merge Sort uit
          System.out.println("Merge Sort");
          Sorteerder  mergesorteerder = new MergeSorteerder();
          dingesrij = leesWaarden(lezer);
          mergesorteerder.sorteer(dingesrij);
          printWaarden(dingesrij);
      
        }
      
        public static Dinges[] leesWaarden(DingesLezer lezer) throws Exception {
          List<Dinges> dingesLijst = new ArrayList<Dinges>();
      
          BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
          
          System.out.println("Invoer:");
          String regel = in.readLine();
          while (regel != null && ! regel.equals("")) {
            Dinges dinges = lezer.leesDinges(regel);
            dingesLijst.add(dinges);
            
            regel = in.readLine();
          }
      
          Dinges[] waarden = dingesLijst.toArray(new Dinges[dingesLijst.size()]);
          return waarden;
        }
      
        public static void printWaarden(Dinges[] waarden) {
          System.out.println("Gesorteerd:");
          for (Dinges dinges : waarden) {
            System.out.println(dinges);
          }
        }
      
      }
      Thank you for your help,

      Greetings T.K. Man
        • 1. Re: Sorting Alogrithm (Mergesort) fails to return sort.
          807588
          This code snippet reassigns the argument passing variable (called waarden and local to your method) to the return value of mergeSort. This variable waarden disappears after the return from the method sorteer. So unless mergeSort has a side effect, that is, unless it manipulates its input, nothing is achieved.

          Met groeten ;-)
           public void sorteer(Dinges[] waarden) {
              // Vervang dit door je algoritme.
              // U moet hier code voor Mergesorteerder geven
                 
                 waarden = mergeSort(waarden);
           
            }
          • 2. Re: Sorting Alogrithm (Mergesort) fails to return sort.
            807588
            Yeah, that's what I thought too! Now how can I manipulate the input?\

            (Without using "return" because I may not edit Main.java)

            Thanks for your help I really appreciate it. Thanks for clearing things up!

            Groetjes ;)

            PS: for some reason there are **** in my comments... but it should the dutch word for can.

            Edited by: TKM on May 6, 2009 11:50 AM
            • 3. Re: Sorting Alogrithm (Mergesort) fails to return sort.
              807588
              This will swap the first two elements (woe if there are less) of the array.
              It is a "side effect" of the method visible on the state of the array waarden.
              public void meinSort(Dinges[] waarden) {
              Dinges d = waarden[0];
              waarden[0] = waarden[1];
              waarden[1] = d;
              }
              • 4. Re: Sorting Alogrithm (Mergesort) fails to return sort.
                807588
                Hello,

                I assume if I would replace "mergeSort" with "meinSort", it will swap the two values and it will be visible?

                Well I have a bit of bad news actually, I used something like this:
                public Dinges[] mergeSort(Dinges[] waarden){
                
                /* Some code */
                
                return result;
                
                }
                how can I get the "side effect" into my array waarden?

                Thanks for your response!

                PS: I should be able to get a "side effect" actually right? Because, I did:
                waarde = mergeSort(waarde);
                or am I incorrect? Can you please clarify?

                PS: I've fixed the problem, thanks for your help.

                Edited by: TKM on May 6, 2009 3:02 PM

                Edited by: TKM on May 6, 2009 7:54 PM
                • 5. Re: Sorting Alogrithm (Mergesort) fails to return sort.
                  807588
                  >
                  [snip]
                  >
                  PS: for some reason there are **** in my comments... but it should the dutch word for can.

                  Edited by: TKM on May 6, 2009 11:50 AM
                  I assumed this was because the English word that resembles the Dutch word for "can" was censored on this board, but according to my poor translation skills that would be "blik" (as in blink, without an "n"), and that doesn't seem too terribly offensive to me.

                  EDIT: oh, I bet that's "Can" as in a can of soda. "Can't" is translated to "kan niet", so I assume "Can" is "kan" (like Kane, from Citizen Kane, without the "e") which also seems innocent.

                  Edited by: tsith on May 6, 2009 8:25 PM
                  • 6. Re: Sorting Alogrithm (Mergesort) fails to return sort.
                    807588
                    It would be "kun" + "t".

                    Greetings TKM