Java- Manually sort a string array using compareTo() method

Question

Let me first say that I know that there a better ways to sort where you might use something other than an array. This an assignment for class where the user can store strings in an array, delete, display, and sort them. I am completely lost to where to go from here. I am trying to use a bubble sort and everything works except whatever is the first entry in my array won't sort. I avoid null pointer exceptions through filtering out null values which is why my if statement is so long.

private void sortItems(String[] cargohold) {
    String temp;
    for (int i = 0; i < cargohold.length - 1; i++) {
        for (int j = 1; j < cargohold.length; j++) {
            if (cargohold[i] != null && cargohold[j] != null && (cargohold[i].compareTo(cargohold[j]) < 0)) {
                temp = cargohold[j];
                cargohold[j] = cargohold[i];
                cargohold[i] = temp;
            }   
        }
    }
}

I have tried a bunch of different ways of doing this and I can't find any good reason why this shouldn't work. I have looked through anything I could find on Stack Overflow as far as examples and no one is having the same issue I am.

To recap, I may have 5 strings, "Derp", "Herp", "Sam", "Alfred", "Bill" and this sort will give me: "Derp", "Alfred", "Bill", "Herp", "Sam". Thanks in advance for the guidance.

First of all this is not a bubble sort there's the first issue — WIR3D
– WIR3D, Commented Sep 6, 2017 at 17:44
@WIR3D you should explain why it is not. The inner loop of a bubble sort normally starts at i + 1, not at 1. As an aside: please wirte the array-brackets after the type, not the variable (String[] cargohold instead of String cargohold[]). — Turing85
– Turing85, Commented Sep 6, 2017 at 17:47

Sumeet · Accepted Answer · 2017-09-06 17:58:16Z

3

The line

if(cargohold[i] != null && cargohold[j] != null && (cargohold[i].compareTo(cargohold[j]) < 0))

should be

if(cargohold[j] != null && cargohold[j-1] != null && (cargohold[j].compareTo(cargohold[j-1]) < 0))

and the swapping should be done as:

temp = cargohold[j];
cargohold[j] = cargohold[j-1];
cargohold[j-1] = temp;

Remember that in bubblesort you compare adjacent elements, where as your code does not do that.

Flaw

There will be cases when i > j and i < j, but the swapping logic remains the same, and that is completely wrong.

edited Sep 6, 2017 at 17:58

answered Sep 6, 2017 at 17:45

Sumeet

8,3645 gold badges27 silver badges51 bronze badges

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

5 Comments

WIR3D Over a year ago

You also need to keep track of whether or not an element has been changed allowing you to know when the sort is complete

Sumeet Over a year ago

@WIR3D, That is one of the discrete optimization , which you can do, but thats not the point here.

user8570492 Over a year ago

@SumeetSingh can you explain to me why this works as opposed to my code?

Sumeet Over a year ago

@user8570492 Because you have not compared the adjacent elements, which is what you do in bubbe sort.

Sumeet Over a year ago

@user8570492 If you carefully observe, there will be cases when i>j and i<j, but the swap logic remains the same, and that is the main flaw.

Ervin Szilagyi · Accepted Answer · 2017-09-06 18:15:04Z

2

Bubblesort algorithm with some optimizations:

private static void sortItems(String cargohold[]) {
    String temp;
    boolean wasSwap = true;
    for (int index1 = 0; index1 < cargohold.length - 1 && wasSwap; ++index1) {
        wasSwap = false;
        for (int index2 = 0; index2 < cargohold.length - index1 - 1; ++index2) {
            if (cargohold[index2].compareToIgnoreCase(cargohold[index2+1]) > 0) {
                temp = cargohold[index2];
                cargohold[index2] = cargohold[index2+1];
                cargohold[index2+1] = temp;
                wasSwap = true;
            }
        }
    }
}

Average complexity being O(n^2) with the best case of O(n).

edited Sep 6, 2017 at 18:15

answered Sep 6, 2017 at 18:09

Ervin Szilagyi

16.9k2 gold badges39 silver badges59 bronze badges

Comments

DwB · Accepted Answer · 2017-09-06 18:01:39Z

0

Your implementation is wrong.

Here is bubble sort (in a java-like shorthand):

for (index1 = 0; index1 < array.length - 1; ++index1)
    for (index2 = index1 + 1; index2 < array.length; ++index2)
        if (array[index1] < array[index1])
            swap(array[index1], array[index2]);

note the index2 = index1 + 1 of the inner loop.

answered Sep 6, 2017 at 18:01

DwB

38.6k11 gold badges62 silver badges86 bronze badges

Comments

Gowtham · Accepted Answer · 2019-03-08 07:22:47Z

0

String[] str = { "red", "blue", "green" };
int n = str.length;
String temp;
System.out.println("Original String Array = " + Arrays.toString(str));
for(int a=0;a<n;a++) {
    for(int b=a+1;b<n;b++) {
        if( str[a].compareTo(str[b]) > 0 ) {
            temp = str[a];
            str[a] = str[b];
            str[b] = temp;
        }
    }
}
System.out.println("Sorted String Array = " + Arrays.toString(str));

edited Mar 8, 2019 at 7:22

answered Mar 8, 2019 at 7:17

Gowtham

11 bronze badge

1 Comment

c-an Over a year ago

If you add explanation, it'd be better.

Collectives™ on Stack Overflow

Java- Manually sort a string array using compareTo() method

4 Answers 4

5 Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related