Inkorrekte Zusammenführungssortierung

Question

Ich arbeite an einem Zusammenführungssortierprogramm, das Filme alphabetisch nach Titel sortiert. Die Liste wird jedoch nicht vollständig sortiert. Ich habe Merge Sorting studiert und verschiedene andere Beispiele sowohl auf dieser Seite als auch anderswo betrachtet und kann meinen Fehler nicht finden.

public static Movie4[] myMovies; 

/** 
* printMovies traverses an array of movies and prints each respective title 
*/ 
public static void printMovies(Movie4[] movies) 
{ 
    for (int i = 0; i < movies.length; i ++) 
    { 
     System.out.println(movies[i]); 
    } 
} 

/** 
* sortTitles sorts an array of movies alphabetically by title 
*/ 
public static void sortTitles(Movie4[] movies, int low, int high) 
{ 
    if (low == high) 
    { 
     return; 
    } 
    else 
    { 
     Movie4[] firstHalf = new Movie4[movies.length/2]; 
     Movie4[] secondHalf = new Movie4[movies.length - movies.length/2]; 
     int midpoint = (low + high)/2; 
     for (int i = 0; i < firstHalf.length; i ++) 
     { 
      firstHalf[i] = movies[i]; 
     } 
     for (int i = 0; i < secondHalf.length; i ++) 
     { 
      secondHalf[i] = movies[i + movies.length/2]; 
     } 
     sortTitles(firstHalf, low, midpoint); 
     sortTitles(secondHalf, midpoint + 1, high); 
     mergeTitles(movies, firstHalf, secondHalf); 
    } 
} 

/** 
* mergeTitles works in conjunction with sortTitles to merge sort an array of Movie4 objects 
*/ 
public static void mergeTitles(Movie4[] movies, Movie4[] first, Movie4[] second) 
{ 
    int i = 0; 
    int i2 = 0; 
    for (int index = 0; index < movies.length; index ++) 
    { 
     if (i2 >= second.length || (i < first.length && 
             first[i].getTitle().compareTo(second[i2].getTitle()) < 0)) 
     { 
      movies[index] = first[i]; 
      i ++; 
     } 
     else 
     { 
      movies[index] = second[i2]; 
      i2 ++; 
     } 
    } 
} 

public static void main(String[] args) 
{ 
    myMovies = new Movie4[10]; 
     myMovies[0] = new Movie4("The Muppets Take Manhattan", 2001, "Columbia Tristar"); 
     myMovies[1] = new Movie4("Mulan Special Edition", 2004, "Disney"); 
     myMovies[2] = new Movie4("Shrek 2", 2004, "Dreamworks"); 
     myMovies[3] = new Movie4("The Incredibles", 2004, "Pixar"); 
     myMovies[4] = new Movie4("Nanny McPhee", 2006, "Universal"); 
     myMovies[5] = new Movie4("The Curse of the Were-Rabbit", 2006, "Aardman"); 
     myMovies[6] = new Movie4("Ice Age", 2002, "20th Century Fox"); 
     myMovies[7] = new Movie4("Lilo and Stich", 2002, "Disney"); 
     myMovies[8] = new Movie4("Robots", 2005, "20th Century Fox"); 
     myMovies[9] = new Movie4("Monsters Inc.", 2001, "Pixar"); 

    System.out.println("Original List:"); 
    System.out.println(); 
    printMovies(myMovies); 
    System.out.println(); 
    System.out.println("List Sorted by title, ascending:"); 
    System.out.println(); 
    sortTitles(myMovies, 0, myMovies.length - 1); 
    printMovies(myMovies); 
} 

Gehen Sie davon aus, dass die getTitle() Methode an anderer Stelle und einfach definiert ist, kehrt die ersten String jedes Objekt, der Titel. Hier ist die falsche Ausgabe;

List Sorted by title, ascending: 

Ice Age, 2002, 20th Century Fox. 
Lilo and Stich, 2002, Disney. 
Mulan Special Edition, 2004, Disney. 
Robots, 2005, 20th Century Fox. 
Monsters Inc., 2001, Pixar. 
Shrek 2, 2004, Dreamworks. 
The Curse of the Were-Rabbit, 2006, Aardman. 
The Incredibles, 2004, Pixar. 
Nanny McPhee, 2006, Universal. 
The Muppets Take Manhattan, 2001, Columbia Tristar. 

Ich glaube, der Fehler mit meiner bedingten Anweisung sein kann, denn wenn ich den compareTo Wert auf> 0, es sortiert richtig, nur in der falschen Reihenfolge.

Answer 1

Sie sollten keine neuen Arrays zuweisen oder Elemente kopieren. Alles innerhalb sortTitles() sollte mit low und high verwaltet werden. Ebenso sollten Sie nicht drei Arrays an mergeTitles() übergeben; Übergeben Sie stattdessen ein einzelnes Array und die Werte low, midpoint und high, um anzugeben, welche Teile des Arrays zusammengeführt werden sollen.

Ihr aktueller Code scheint ein Fencing-Problem zu haben: Sie berechnen midpoint mit (low + high)/2, aber verwenden Sie movies.length/2 für die Länge des ersten Arrays. Da low mit 0 beginnt und high mit myMovies.length - 1 beginnt, unterscheiden sich diese Längen, wenn myMovies.length gerade ist. Möglicherweise haben Sie andere Indizierungsprobleme, aber ich habe nicht zu sehr darauf geachtet, weil der gesamte Ansatz fehlerhaft ist, wie ich im ersten Abschnitt beschrieben habe.