Mergesort mit ArrayList

[imboar]

Guten Tag liebe Freunde der Javaprogrammierung.

Ich muss aktuell den Mergesortalgorithmus in Java implementieren unter zuhilfenahme von Arraylisten. Soweit ist der Algorithmus nicht schwer, doch sitze sich seit einigen Stunden an dem Problem, das nach dem ausführen von mergeSortInt() auf das übergebene Array, dies mit der Größe 0 und ohne Inhalt wieder zurückgegeben wird. Ich finde partout nicht den Grund dafür.

Edit: Zum testen erzeuge Ich eine Arrayliste mit 50 Zufallszahlen(int) die Ich der Methode übergebe. Diese kommen im Programm auch korrekt an.

import java.math.BigInteger;
import java.util.ArrayList;


public class Mergesort {
  public static void sortInt(ArrayList<Integer> array) {
    
    //Hier ist die Arraygröße noch korrekt.

    array = mergeSortInt(array);

    //Hier ist die Arraygröße = 0, demzufolge auch ohne Inhalt
  }  
  
  
  public static void sortBig(ArrayList<BigInteger> array) {
    
    
    
  }
  
  public static ArrayList<Integer> mergeSortInt (ArrayList<Integer> array) {
    
    int p = (array.size() / 2);
    int x = 0;
    ArrayList<Integer> links = new ArrayList<Integer>(p);    
    ArrayList<Integer> rechts = new ArrayList<Integer>(p);
    
    if (array.size() > 1) {
      
      for (int i = 0; i < array.size() / 2; i++) {
        
        links.add(i, array.get(i));                                    //Erzeugt linke Teilliste
        
      } // Ende for-Schleife zum erzeugen der linken Liste
      
      for (int i = array.size(); i < (array.size() - 1); i++) {
        
        rechts.add(x, array.get(i));                                  //Erzeugt rechte Teilliste
        x++;
      } // Ende for-Schleife zum erzeugen der rechten Liste 
      
      links = mergeSortInt(links);
      rechts = mergeSortInt(rechts);                                  //Teillisten via MErgesort sortieren
      array = mergeInt(links,rechts);                                 //danach Teillisten zusammenfügen
      return array;
      
    } // Ende if
    else{
      
      return array;
      
    }
    
  }
  
  public static ArrayList mergeInt (ArrayList<Integer> links, ArrayList<Integer> rechts){
    
    int gesamt = links.size() + rechts.size();         
    ArrayList<Integer> sortiert = new ArrayList<Integer>(gesamt);
    int left = 0;
    int right = 0;   
      
      for (int i = 0; i < gesamt - 1; i++) { 
        
        if (links.get(left) >= rechts.get(right)) {
          
          sortiert.add(i, rechts.get(right));                //Falls aktuelles Listenelement rechts > links, füge rechtes Element in neue Liste ein
          right++;
          
        }
        else{
          
          sortiert.add(i, links.get(left));                 //ansonsten das Linke
          left++;
          
        } // Ende else
        
      } //Ende for 
      
    return sortiert;
  }
  
}

 

[gescom]

sicher das es so stimmt?

for (int i = array.size(); i < (array.size() - 1); i++)

 

[VfL_Freak]

Moin,

sicher das es so stimmt?

for (int i = array.size(); i < (array.size() - 1); i++)

Mit Sicherheit NICHT !!

Sollte wohl i-- heißen

Gruß
Klaus

 

[Flown]

Also wir haben das auch mal an der Uni machen müssen. Die Vorredner haben schon deinen Fehler aufgezeigt und ein zweiter ist:

[JAVA=64]
for (int i = 0; i < gesamt - 1; i++) { ... }
[/code]

Das -1 muss weg weil du es gesamt befüllen musst!

Also damit eine saubere Lösung auch mal hier kursiert, hier mein Code:

Spoiler: Mergesort

package sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Mergesort {
	
	public static <T extends Comparable<T>> void sort(List<T> list) throws IllegalArgumentException {
		if(list == null) throw new IllegalArgumentException("Array must not be null!");
		Collections.copy(list, mergeSort(list));
	}

	private static <T extends Comparable<T>> List<T> mergeSort(List<T> list) {

		if (list.size() <= 1) return list;
		
		int p = (list.size() / 2);
		
		List<T> left = new ArrayList<T>(p);
		List<T> right = new ArrayList<T>(p);

		left.addAll(list.subList(0, p));
		right.addAll(list.subList(p, list.size()));
		
		return merge(mergeSort(left), mergeSort(right));
	}

	private static <T extends Comparable<T>> List<T> merge(List<T> left, List<T> right) {
		int total = left.size() + right.size();
		List<T> sorted = new ArrayList<T>(total);
		int leftIndex = 0;
		int rightIndex = 0;

		for (int i = 0; i < total; i++) {
			if(rightIndex < right.size() && leftIndex < left.size()) {
				if (left.get(leftIndex).compareTo(right.get(rightIndex)) >= 0) {
					sorted.add(right.get(rightIndex++));
				} else {
					sorted.add(left.get(leftIndex++));
				}
			}
			else if(rightIndex < right.size()) {
				sorted.add(right.get(rightIndex++));
			}
			else {
				sorted.add(left.get(leftIndex++));
			}
		}
		return sorted;
	}
}

 

[imboar]

Wunderbar - jetzt funktioniert es problemlos. Ich bedanke mich für die Hilfe.

so long
imboar