Quicksort Multiple Variable [Java]

Question

Goodday! I am trying to sort a data (Name - age) by its age. I have use the QUICKSORT algorithm and works fast for sorting AGEs but how do I sort Age with their respective name?

I also googled the Comparable and Comparator but I don't understand how to implement it with quicksort.

here is my code for quicksort.

private int array[];
private int length;

public void sort(int[] inputArr) {
    if (inputArr == null || inputArr.length == 0) {
        return;
    }
    this.array = inputArr;
    length = inputArr.length;
    quickSort(0, length - 1);
}

private void quickSort(int lowerIndex, int higherIndex) {
    int i = lowerIndex;
    int j = higherIndex;
    int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
    while (i <= j) {
        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(i, j);
            i++;
            j--;
        }
    }
    // call quickSort() method recursively
    if (lowerIndex < j)
        quickSort(lowerIndex, j);
    if (i < higherIndex)
        quickSort(i, higherIndex);
}

private void swap(int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public static void main(String a[]){

    GUIAdvanceSort sorter = new GUIAdvanceSort();
    int[] input = {5,4,3,2,1};
    sorter.sort(input);
    for(int i:input){
        System.out.print(i);
        System.out.print(" ");
    }
}

The < and > operators work on ints in the array but not objects. You need to invoke a Comparator on the two objects to get the same information. — Thorbjørn Ravn Andersen
– Thorbjørn Ravn Andersen, Commented Mar 6, 2016 at 0:44
yes sir, but how do I stick together the Comparator and Quicksort? — something
– something, Commented Mar 6, 2016 at 0:53
Basically: Collections.sort(myList, new MySpecialNameAndAgeComparator());. See: docs.oracle.com/javase/8/docs/api/java/util/… — Andrew Regan
– Andrew Regan, Commented Mar 6, 2016 at 0:55

Andrew Regan · Accepted Answer · 2016-03-07 00:20:24Z

1

To summarise the links and comments, you first need to create a NameAndAge class to encapsulate the two properties. Then you have two options:

Make NameAndAge 'naturally' comparable, by implementing Comparable<NameAndAge>
If you don't believe they're inherently comparable, create a dedicated Comparator<NameAndAge> and apply it to a list.

I think (1) is the right choice here.

The following example is far from complete (equals() and hashCode() should be overridden), but it demonstrates natural ordering of NameAndAge: name first (case-insensitive), then age (ascending), and it works when using Java's existing Collections.sort() method.

What you need to do for your own algorithm is:

Switch your algorithm from dealing with int => NameAndAge, or ideally Comparable<T>
Instead of using < and >, use current.compareTo(pivot) instead.

Comparable example:

public static void main(String a[]){

    List<NameAge> entries = new ArrayList<>();
    entries.add( new NameAge("Zack", 2) );
    entries.add( new NameAge("John", 37) );
    entries.add( new NameAge("John", 11) );
    entries.add( new NameAge("John", 5) );
    entries.add( new NameAge("Andrew", 9) );

    Collections.sort(entries);

    for (NameAge each : entries) {
        System.out.println(each.name + " (" + each.age + ")");
    }
}

public static class NameAge implements Comparable<NameAge> {
    String name;
    int age;

    public NameAge(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo( NameAge other) {
        int nc = name.compareToIgnoreCase( other.name );
        if (nc != 0) {
            return nc;
        }
        return (age < other.age) ? -1 : ((age > other.age) ? 1 : 0);
    }
}

Produces:

Andrew (9)
John (5)
John (11)
John (37)
Zack (2)

edited Mar 7, 2016 at 0:20

answered Mar 6, 2016 at 23:05

Andrew Regan

5,1237 gold badges41 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

something Over a year ago

thankyou for your answer. but where can I insert my quicksort algorithm?

Andrew Regan Over a year ago

I'll see if I can paste my complete example later , but for the time being you just need to replace the Collections.sort(entries); line with a call to sort() and your int[] with List<NameAge> (or whatever name you use - obviously the above is an example)

Collectives™ on Stack Overflow

Quicksort Multiple Variable [Java]

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related