Im trying to write a selection sort with ascending and descending options

Question

I have a selection sort method to sort my objects by there year variable. I got it working to sort in ascending order, I can't seem to get the descending order working. It would be awesome if somebody could look at the code and possibly point me in the right direction

public static void sortYears(ArrayList<Movies3> list, int ad){
    int max, min,  i, j;
    Movies3 temp;

    if(ad == 1){
        for (i = 0; i < list.size() - 1; i++){
            max = i;

            for (j = i + 1; j < list.size(); j++){
                if (list.get(max).getYear() > list.get(j).getYear()){
                    max = j;
                }
            }

            temp = list.get(i);
            list.set(i, list.get(max));
            list.set(max, temp);
        }
    }else if(ad == 2){
        for (i = 0; i < list.size() - 1; i++){
            min = i;

            for (j = i + 1; j > list.size(); j++){
                if (list.get(min).getYear() < list.get(j).getYear()){
                    min = j;
                }
            }

            temp = list.get(i);
            list.set(i, list.get(min));
            list.set(min, temp);
        }
    }
}

Answer 1

I suggest you that your class Movies3 must implement the interface Comparable and use the sort method of the java class List and create a custom Comparator. I think is the better and more elegant way to do it.

It could be something like this:

For the Movie3 class

public class Movie3 implements Comparable<Movie3> {


private int year;
    private String author;
    private String genre;
    public Movie3(int year, String author, String genre) {
        super();
        this.year = year;
        this.author = author;
        this.genre = genre;
    }
    /**
     * @return the year
     */
    public int getYear() {
        return year;
    }
    /**
     * @param year the year to set
     */
    public void setYear(int year) {
        this.year = year;
    }
    /**
     * @return the author
     */
    public String getAuthor() {
        return author;
    }
    /**
     * @param author the author to set
     */
    public void setAuthor(String author) {
        this.author = author;
    }
    /**
     * @return the genre
     */
    public String getGenre() {
        return genre;
    }
    /**
     * @param genre the genre to set
     */
    public void setGenre(String genre) {
        this.genre = genre;
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("Year: "+this.getYear());
        sb.append("Author: "+this.getAuthor());
        sb.append("Genre: "+this.getGenre());
        return sb.toString();
    }
    public int compareTo(Movie3 m) {
        return Integer.compare(this.year, m.year);
    }

}

On the other hand the Custom comparator is simply:

import java.util.Comparator;

public class MovieYearComparator implements Comparator<Movie3> {
    private boolean reverse;

    public MovieYearComparator(boolean reverse) {
        super();
        this.reverse = reverse;
    }

    @Override
    public int compare(Movie3 m1, Movie3 m2) 
    {
        if (reverse)
            return m1.getYear() < m2.getYear() ? 1 : m1.getYear() == m2.getYear() ? 0 : -1;
        else
            return m1.getYear() < m2.getYear() ? -1 : m1.getYear() == m2.getYear() ? 0 : 1;
    }
}

And finally the test:

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

import data.Movie3;
import data.MovieYearComparator;

public class test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<Movie3> movies = new ArrayList<Movie3>();
        movies.add(new Movie3(1000,"sds","sdf"));
        movies.add(new Movie3(1001,"sds","sdf"));
        movies.add(new Movie3(2001,"sds","sdf"));
        movies.add(new Movie3(2444,"sds","sdf"));
        movies.add(new Movie3(1002,"sds","sdf"));
        movies.add(new Movie3(1003,"sds","sdf"));
        System.out.println(movies.toString());
        boolean reverse = true;
        movies.sort(new MovieYearComparator(!reverse));
        System.out.println(movies.toString());
        movies.sort(new MovieYearComparator(reverse));
        System.out.println(movies.toString());  

    }
}

Answer 2

Your variable names and scopes really confusing, a lot of duplicated code.

for (j = i + 1; j > list.size(); j++) - this line of code will never be executed in majority of cases.

This s a fix for your descending order:

// the same walk as for ASC but reversed comparison
for (int i = 0; i < list.size() - 1; i++) {
    candidateIndex = i;

    for (int j = i + 1; j < list.size(); j++) {
        if (list.get(candidateIndex).getYear() < list.get(j).getYear()) {
            candidateIndex = j;
        }
    }

    temp = list.get(i);
    list.set(i, list.get(candidateIndex));
    list.set(candidateIndex, temp);
}

You definitely need to look at Comparator:

A comparison function, which imposes a total ordering on some collection of objects. Comparators can be passed to a sort method (such as Collections.sort or Arrays.sort) to allow precise control over the sort order. Comparators can also be used to control the order of certain data structures (such as sorted sets or sorted maps), or to provide an ordering for collections of objects that don't have a natural ordering. The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S.

I will write a full example using comparators:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Main {
    /**
     * Defining comparator for ascending order by default
     */
    public static final Comparator<Movies3> COMPARATOR = (m1, m2) -> m1.getYear() - m2.getYear();

    public static void main(String[] args) {
        List<Movies3> movies = new ArrayList<>(
            Arrays.asList(new Movies3(1990), new Movies3(1995), new Movies3(2000)));

        sortYears(movies, true);
        System.out.println(movies);

        sortYears(movies, false);
        System.out.println(movies);
    }

    public static void sortYears(List<Movies3> list, boolean asc) {
        int candidateIndex; // index of candidate whatever min or max
        Movies3 temp;
        Comparator<Movies3> comparator;

        if (asc) {
            comparator = COMPARATOR;
        } else {
            comparator = COMPARATOR.reversed(); // switch to DESC order
        }

        for (int i = 0; i < list.size() - 1; i++) {
            candidateIndex = i;

            for (int j = i + 1; j < list.size(); j++) {
                if (comparator.compare(list.get(candidateIndex), list.get(j)) > 0) {
                    candidateIndex = j;
                }
            }

            temp = list.get(i);
            list.set(i, list.get(candidateIndex));
            list.set(candidateIndex, temp);
        }
    }
}

Output:

[year 1990, year 1995, year 2000]
[year 2000, year 1995, year 1990]

You can also let your class implement Comparable to define natural ordering for it and use it instead of Comparator.

Answer 3

Replace direct comparisons like list.get(max).getYear() > list.get(j).getYear() with a Comparator: comparator.compare(list.get(max).getYear(), list.get(j).getYear()) > 0

You can then easily achieve inverted sorting with Comparator.reversed()

Answer 4

for (j = i + 1; j > list.size(); j++){

The predicate should be j < list.size(); instead of >, otherwise your loop would never iterate as i+1 always <=n, so j is always <=n