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;
    }

Answer 1

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");

        }


    }

Answer 2

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);
}

Answer 3

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()

Answer 4

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;
        }
    }
}