Sorting Integer array using Comparable

Question

I am working on a project in which I have to sort an array of Integer objects by using Comparable.

My add method takes an item of type E. If my size variable (which tracks the elements in my array theData[]) is = 0 (which it is initialized to), I simply put the item in theData[0].

If it is not, I use item.compareTo to compare the item against each item already in the array. If the result of compareTo is < 0 for a number in the array, I shift everything at that number and after to the right, and insert the item before it.

If compareTo returns a 0, meaning the item is equal to the number in the array, I do nothing as I don't want duplicates in the array.

If none of the compareTo statements in the loop return a -1 or a 0, I put the item in theData[size], the end of the array, as it must be larger than all the other numbers.

However, this doesn't work. Any time I make a new Set and add a few numbers to it, then try to print out the contents of my set using a for loop,I keep getting a java.lang.ArrayIndexOutOfBoundsException: 10 error for this line:

theData[j + 1] = theData[j];

I've tried starting from scratch and re-writing my loop with different logic, and each time I keep hitting this wall. I know I must either be shifting incorrectly or not increasing the size of the array correctly with my reallocate method, but I can't wrap my head around it.

import java.util.*;

public class Set<E extends Comparable<E>> {

String s;
String name;
private static final int INITIAL_CAPACITY = 10;
private E[] theData;
private int size = 0;
private int capacity = INITIAL_CAPACITY;

@SuppressWarnings("unchecked")
public Set() {
    theData = (E[]) new Comparable[capacity];
}

public Set(String name) {
    this.name = name;
}

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

public void add(E item) {

    if (size == capacity) {
        reallocate();
    }

    if (size == 0) {                        // If size is 0, add item to theData[0]
        theData[size] = item;
        size++;
        return;
    }

    else {                                  // Else compare the item to every item in loop.
        for (int i = 0; i < size; i++) {

            int result = item.compareTo(theData[i]);

            if (result < 0) {       

                for (int j = 0; j < size; j++) {        //If item is less than a number, shift everything
                    theData[j + 1] = theData[j];        //after that index to the right, and add item
                    theData[j] = item;

                }
            }

            if (result == 0) {
                return;
            }

            else {                                      //If item is not less than or equal to any
                theData[size] = item;                   //numbers in the array, add it to the end
                size++;

            }

        }

    }

}

/*
 * if (size>=1){ int result = item.compareTo(theData[size-1]); if(result<0){
 * E temp = theData[size-1]; theData[size-1] = item; theData[size] = temp; }
 * if(result>1){ return; } }
 */

public E get(int index) {
    if (index < 0 || index >= size) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    return theData[index];
}

public int size() {
    return size;
}

private void reallocate() {
    capacity = 2 * capacity;
    theData = Arrays.copyOf(theData, capacity);
}

}

Edit: The driver method I'm using to test it -

public class Driver {

String one = "two";

public static void main(String[] args){

Set<Integer> one = new Set<Integer>();

one.add(63);
one.add(20);
one.add(127);
one.add(10);
one.add(26);
one.add(15);

for(int i = 0; i < one.size(); i++){
System.out.println(one.get(i));
}

}
}

Makoto · Accepted Answer · 2015-10-30 02:56:26Z

2

When j == size - 1, theData[j+1] will take you out of the array.

You want to loop to one before the end instead.

 for (int j = 0; j < size - 1; j++) {        //If item is less than a number, shift everything
     theData[j + 1] = theData[j];        //after that index to the right, and add item
     theData[j] = item;
}

So I've also taken a look at the logic you've got for the insertion, and it doesn't make a lick of sense. Why do you delay the insertion at all? If you've got the room, just add it!

Next, the double loops are essentially implementing bubble sort, but there's a fatal flaw with it: you don't ever complete the swap; you only overwrite your values repeatedly. You're also not comparing in the right direction; you want to swap if the value on the left is larger than the value on the right, since you're starting from the beginning of the array.

So, with that...this is what an implementation would have the form of...

public void add(E item) {

    if (size == capacity) {
        reallocate();
    }

    theData[size++] = item;
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - 1; j++) {
            if (theData[j].compareTo(theData[j + 1]) > 0) {
                // perform the swap (you need an extra variable!
            }
        }
    }
}

I leave implementing the swap as an exercise for the reader.

edited Oct 30, 2015 at 2:56

answered Oct 30, 2015 at 2:23

Makoto

107k29 gold badges199 silver badges236 bronze badges

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

4 Comments

sam Over a year ago

I made that change, and now I oddly get nothing but 15 for the output, which is the last number I added to the list (I will add my main method above)

Makoto Over a year ago

@sam: I've revised my answer. I still feel sound in that I've addressed your original issue; the rest of the issue may be you hashing it out with a tutor or your professor.

sam Over a year ago

I do greatly appreciate your help. I just don't want to check off an answer yet in case others were going to add something.

sam Over a year ago

I performed the swap and got it working. Thank you so much, you're right, my logic was a mess and yours is so much cleaner.

Cleivson Arruda · Accepted Answer · 2015-10-30 02:54:38Z

1

First, in your shift loop, you are inserting the new item in every position instead of shifting then inserting in [i] because you copy theData[j] to the next position, but always assign item to theData[j], is that right? Second, you are starting from the beginning of array since j starts with 0. J should start with i. Third and main bug, you verify if result < 0 then you verify IF result == 0, change for a ELSE IF so the else don't get executed even when result < 0

edited Oct 30, 2015 at 2:54

answered Oct 30, 2015 at 2:38

Cleivson Arruda

1064 bronze badges

2 Comments

sam Over a year ago

I see what you mean with j starting at i, but I'm not sure why the item would be inserted at every position. I am trying to make it so if the compareTo returns -1, everything from theData[j] onward is shifted right, and the item becomes the new theData[j].

Cleivson Arruda Over a year ago

@Sam, You were assigning item to theData[j] every iteration when in fact you wanted to assign item to theData[i] after the shift loop

Hooting · Accepted Answer · 2015-10-30 02:57:40Z

0

shift elements to right can be done from right to left, like:

for (int j = size; j > i; j--) { // If item is less than a
                                // number, shift
                                // everything
    theData[j] = theData[j - 1]; // after that index to the
                                // right, and add item

}
size++;
theData[i] = item;
break;// after insert the number, we can just break the for loop

once the new number is inserted, break the for loop, else, the size variable will not be correct

else {                    // If item is not less than or equal to any
    theData[size] = item; // numbers in the array, add it to the end
    size++;
    break;
}

answered Oct 30, 2015 at 2:57

Hooting

1,72111 silver badges20 bronze badges

Collectives™ on Stack Overflow

Sorting Integer array using Comparable

3 Answers 3

4 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related