Why does this insertion sort does not work?

Question

I have created a movie class that defines movie objects. This is the client class that test the class. I have created a method to sort the array of Movie objects by the year it is created. When I test the program, I found that some of the Movie objects will be sorted and some will not. Can someone help me why this doesn't work?

public class MovieTesterv2 {
public static void main(String[] args) {
    Movie[] movies = {new Movie("Meet the Robinsons", 2007, "Disney"),
            new Movie("Avengers: Infinity War", 2018, "Pinewood"),
            new Movie("Iron Man", 2008, "Tim Miller"),
            new Movie("Aquaman", 2018, "Hollywood"),
            new Movie("Bumblebee", 2018, "Hollywood"),
            new Movie("Transformers", 2007, "Universal"),
            new Movie("The Lion King", 1994, "Disney"),
            new Movie("Mummy", 1999, "Universal"),
            new Movie("Minions", 2015, "Universal"),
            new Movie("Cinderella", 1950, "Disney")};
    insertionYear(movies);
}

public static void printMovies(Movie[] movies) {
    System.out.println("                 Movie     Year       Studio");
    System.out.println("--------------------------------------------");
    for (Movie movie: movies) {
        if (movie != null) {
            System.out.printf("%22s%9s%13s%n", movie.getTitle(),
                    movie.getYear(), movie.getStudio());
        }
    }
}

public static void insertionYear(Movie[] movies) {
    Movie[] sorted = new Movie[movies.length];

    for (int i = 0; i < movies.length; i++) {
        int k = i;
        while (k > 0) {
            if (movies[i].getYear() <= movies[k - 1].getYear()) {
                sorted[k] = sorted[k - 1];
                k--;
            } else {
                break;
            }
        }
        sorted[k] = movies[i];
        printMovies(sorted);
        System.out.println();
    }

    for (int i = 0; i < movies.length; i++) {
        movies[i] = sorted[i];
    }
}

}

This is the movie class.

public class Movie
{
    private int year;
    private String title;
    private String studio;

    public Movie(String title, int year, String studio)
    {
        this.title = title;
        this.year = year;
        this.studio = studio;
    }

public String getTitle()
{
    return title;
}

public void setTitle(String title)
{
    this.title = title;
}

public String getStudio()
{
    return studio;
}

public void setStudio(String studio)
{
    this.studio = studio;
}

public int getYear()
{
    return year;
}

public void setYear(int year)
{
    this.year = year;
}

public String toString()
{
    String str = String.format("%-30s %4d   %-20s", title, year, studio);
    return str;
}

}

See [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) — Andreas, Feb 03 '19 at 00:01

score 1 · Answer 1 · answered Feb 03 '19 at 00:26

1

Look at this this line:

if (movies[i].getYear() <= movies[k - 1].getYear()) {

You want to compare the movie against the sorted list instead of its own movie list.

answered Feb 03 '19 at 00:26

mrfujin

11
2

score 0 · Accepted Answer · answered Feb 03 '19 at 00:41

You're not comparing each element to the sorted list like insertion sort normally does. In this line,

if (movies[i].getYear() <= movies[k - 1].getYear())

You compare the current movie you're iterating to the movies that come before it in the original list. This should be changed to

if (movies[i].getYear() <= sorted[k - 1].getYear())

The reason is that now you're comparing the current movie at index i to the movies in indices less than i in the sorted array. This way, you can find the right spot for the current movie in the sorted movies so far.

@YuchengHuo no problem. If you found the answer helpful, please consider accepting or upvoting it. Good luck coding! — Chris Gong, Feb 03 '19 at 05:46

Why does this insertion sort does not work?

2 Answers2