Sorting objects in an ArrayList without using Collections.sort

Question

I would like to use my own sorting method instead of Collections.sort so that I can tinker around with my program to understand other sorts, generics, and ArrayLists better.

I have an employee class that has an employee number member. I know how to make an ArrayList of Employee objects, but could you explain how I could print and sort them? I started off by sorting a regular array and wanted to do the same with an ArrayList of Employee objects (the employee number). I'm having trouble understanding how to print ArrayLists of objects and sorting them.

package dataStructures;

import java.util.ArrayList;
import java.util.Arrays;

public class SortPractice {

    public static void main(String[] args) {
        int[] nums = {5,4,3,2,1};

        System.out.println(Arrays.toString(nums));

        BubbleSort1(nums);

        ArrayList<Employee> empList = new ArrayList<Employee>();

        for (int i=0; i<10; i++) {
            empList.add(new Employee(10-i));

        }

        BubbleSort(empList);  //This method doesn't work. I need help here.

    }


public static void BubbleSort (int[] A) {   //I included this because I know it works.
        int temp = 0;
        int firstLoopCount = 0;
        int SecLoopCount = 0;
        for (int i=0; i< A.length-1; i++) {
            firstLoopCount++;
            System.out.println(Arrays.toString(A) + i + " << First Loop interation");

           for (int j=0; j<A.length-1; j++) {
               if (A[j] > A[j+1]) {
                    temp = A[j];
                    A[j] = A[j+1];
                    A[j+1] = temp;
                }
               SecLoopCount++;
             System.out.println(Arrays.toString(A) + j + "  << Second Loop Interation");

           }
        }
        System.out.println((firstLoopCount+SecLoopCount));


    }

    public static void BubbleSort (ArrayList<Employee> empList) { //I tried to use the same
        int temp = 0;                                             //approach just with the List
        int firstLoopCount = 0;
        int SecLoopCount = 0;
        for (int i=0; i<empList.size()-1; i++) {
            firstLoopCount++;
            System.out.println(Arrays.toString(empList) + i + " << First Loop interation");

           for (int j=0; j<empList.size()-1; j++) {
               if (empList.get(j) > empList.get(j+1)) {    //I get errors here in Eclipse and 
                    temp = A[j];                           //up above when I use toString
                    A[j] = A[j+1];
                    A[j+1] = temp;
                }
               SecLoopCount++;
             System.out.println(Arrays.toString(A) + j + "  << Second Loop Interation");

           }
        }
        System.out.println((firstLoopCount+SecLoopCount));


    }

Here is the employee class. It has other getters and setters but I didn't include them.

package dataStructures;

 public class Employee {

     private int empNum;
     private String firstName;
     private String LastName;
     private String email;

     public Employee(int empNum) {
         this.empNum = empNum;
     }


     public String toString(){
         return " "+ empNum + ",";

     }
     public Employee() {

     }

     public int getEmpNum() {
        return empNum;
    }
    public void setEmpNum(int empNum) {
        this.empNum = empNum;
    }

Tip: solve one problem at a time. You have compilation errors: take first, deal with it (search for it, ask specific question, if necessary), fix it, go to the next. That's going to be much more productive than asking random people to fix all errors in your code. — default locale
– default locale, Commented Jan 5, 2015 at 6:03
Before you go about saying you want to sort an object, you have to establish its natural ordering. What makes some arbitrary Employee instance come before another arbitrary Employee instance? Seeing the Employee class may help determine this. — Makoto
– Makoto, Commented Jan 5, 2015 at 6:04
Okay, first thing: don't apologize. We can appreciate that not everyone knows everything about the language, that's why it's okay to ask. Second, observe the compilation errors. Look at the API documentation to ensure that what you're passing to those methods makes sense. — Makoto
– Makoto, Commented Jan 5, 2015 at 6:06
@BrettCunninghamII nothing to be sorry about :) Change your question to target specific compilation error. Make sure to include error message. And search for it beforehand maybe it was already asked before. — default locale
– default locale, Commented Jan 5, 2015 at 6:07

Makoto · Accepted Answer · 2015-01-05 06:27:16Z

Accessing an array is different from accessing an ArrayList. This is because these two objects are fundamentally different.

Let's focus on this line of code:

System.out.println(Arrays.toString(empList) + i + " << First Loop interation");

You're going to want to bookmark the Java 7 API so that you can reference what it is these methods actually take as arguments. Believe me, it will save you lots of time in the long run.

Specifically, the code is invalid because toString does not accept a parameter of type ArrayList. You can just straight-up print an ArrayList, as it has a reasonable toString method, whereas an array doesn't (which is why you use Arrays#toString):

System.out.println(empList.toString() + i + " << First Loop interation");

Let's look at this if block next:

if (empList.get(j) > empList.get(j + 1)) {    //I get errors here in Eclipse and
    temp = A[j];                           //up above when I use toString
    A[j] = A[j + 1];
    A[j + 1] = temp;
}

I'll be blunt, you're going to get errors in any reasonable IDE with that code. The reason: you index into arrays with brackets, but you use get for an ArrayList.

The first fix is that you can't compare those two instances with >. What you'd wind up doing instead is retrieving the field you want to compare it with instead.

if(empList.get(j).getEmpNum() > empList.get(j+1).getEmpNum()) {
    // more code
}

Here's the relevant Javadoc for ArrayList. You're going to need it.

Let's focus on the inner part of the if. The operation you're doing there is called a swap. You're taking an element from one location and overwriting it with another. Since arrays don't shift elements down, you have to capture the original value before you overwrite it.

To put it in English:

Take original value
Place new value in original value's original array location
Place original value in new value's original array location

You shouldn't have to do that with an ArrayList, as it can add the element in a specific spot.

In English, it should be as simple as:

Insert new value in original value's spot
Delete new value's occurrence in the list

In Java, it might read like this:

if(empList.get(j).getEmpNum() > empList.get(j + 1).getEmpNum()) {
    empList.add(j, empList.get(j + 1));
    empList.remove(j + 1);
}

Thank you very much Makoto! I'm going through you answer now and working on my program to make it better. I really appreciate the time you took to take a look at this mess :) lol
It works now thank you! I changed the rest of the program accordingly.

score 2 · Accepted Answer · 2015-01-05 06:14:59Z

2

One problem I noticed is in this line -

empList.get(j) > empList.get(j+1)

You are comparing 2 objects, i.e. 2 employee objects, this is usually not used other than for primitive types (e.g. Integer).

What you probably want to compare is the employee IDs which I assume is in your Employee.java file (please post this file so we can take a look). Here's an example of what you could do for this line -

empList.get(j).getEmployeeId() > empList.get(j+1).getEmployeeId()

Edit: sorry read the question wrong, not using Collections.sort()

edited Jan 5, 2015 at 6:14

answered Jan 5, 2015 at 6:08

user4416494

2 Comments

Sankofa Over a year ago

that empList.get(j).getEmpNum()... line worked. I have a long way to go but thanks for your help!

user4416494 Over a year ago

Good to hear :) Your algorithms look correct, good expressive names as well. One thing you can try to help with you learning is go back and simplify the algorithms, although we can read these ones pretty easily when you get to larger code bases simplification gets difficult, but is pretty important.

j_v_wow_d · Accepted Answer · 2015-01-05 06:09:18Z

Here is an example. In this case, your class has to provide a method that overrides the compareTo method in the Comparable interface. The specification is that it should return an integer greater than 0 if the calling object is greater, or an integer less than 0 if the caller is less, return 0 otherwise.

public class Employee implements Comparable {


    //Rest of your class code here

    public void getID() {
        //return some value associated with the ID
    }

    //override this method
    public int compareTo(Employee other) {
        //code to compare two Employees
        // Maybe something like the following
        if (this.getID() > other.getID()) {
            return 1;
        } else if (this.getID() < other.getID()) {
            return -1;
        } else {
            return 0;
        }
    }
}

Sankofa · Accepted Answer · 2015-01-05 08:50:24Z

This is the final answer with the help of @Makoto

public static void BubbleSort (ArrayList<Employee> empList) {
        for (int i=0; i<empList.size()-1; i++) {            
           for (int j=0; j<4; j++) {
               if (empList.get(j).getEmpNum() > empList.get(j+1).getEmpNum()) {
                        empList.add(j, empList.get(j + 1)); //This line inserts the smaller value
                        empList.remove(j+2);                //into the first index and pushes the       
                }                                           //indices down 1. So I need to remove
                                                            //j+2 not j+1.

            /*When I use the debugger to step into toString() it says source not found. 
            I don't get it but it works.*/

            System.out.println(empList.toString() + j + "  << Second Loop Interation"); 
           }
            System.out.println(empList.toString() + i + " << First Loop interation");

        }


    }

Collectives™ on Stack Overflow

Sorting objects in an ArrayList without using Collections.sort

4 Answers 4

2 Comments

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related