Insertion Sort Strings

Question

I read a file with cities and its population and I am trying to sort the cities alphabetically using an insertion sort. The issue is that it sorts all of the elements except the first one. The first value in the unsorted list remains in index [0] in the sorted list. This is the code:

    int i, j;
    String v;
    for (i = 1; i < cities.size()-1; i++)
    {
        v = cities.get(i);
        j = i;
        while (cities.get(j-1).compareToIgnoreCase(v) > 0 && j >=2)
        {
            cities.set(j, cities.get(j-1));
            j--;
        }
        cities.set(j, v);
    }

Any idea what's wrong?

Thank you.

for (i = 1; i < cities.size()-1; i++)?? Java arrays are zero indexed...Any reason why you're not using Collections.sort? — MadProgrammer
– MadProgrammer, Commented Mar 3, 2015 at 0:57

RogueBaneling · Accepted Answer · 2015-03-03 00:57:24Z

3

You probably want for (i = 0; i < cities.size(); i++).

Accessing arrays and lists starts counting from 0, but the actual size of the list/array starts counting from 1.

Example: To access the first (and only) element of an array a of size 1, you would use a[0].

answered Mar 3, 2015 at 0:57

RogueBaneling

4,4794 gold badges25 silver badges33 bronze badges

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

1 Comment

A.J Over a year ago

I can't start with i = 0 because j = 0 and I compare an element that is in index [j-1].

MadProgrammer · Accepted Answer · 2015-03-03 02:25:29Z

2

First, this...

for (i = 1; i < cities.size()-1; i++)

should probably be...

for (i = 1; i < cities.size(); i++)

Second, this...

j = i;

should probably be...

int j = i - 1;

Third, this...

while (cities.get(j - 1).compareToIgnoreCase(v) > 0 && j >= 2) {

is a mess. You try and access the value from the List BEFORE you ascertain if the value is actually accessible (ie if j is within the range of the List) and probably should be something more like...

while ((j > -1) && (cities.get(j).compareToIgnoreCase(key) > 0)) {

Having said all that, this will mean that cities.set(j, cities.get(j - 1)); will need to become cities.set(j + 1, cities.get(j)); and cities.set(j, v); will need to become cities.set(j + 1, key);

Something like...

    List<String> cities = new ArrayList<>(25);
    cities.add("D");
    cities.add("C");
    cities.add("B");
    cities.add("A");

    for (int i = 1; i < cities.size(); i++) {
        String key = cities.get(i);
        int j = i - 1;
        while ((j > -1) && (cities.get(j).compareToIgnoreCase(key) > 0)) {
            cities.set(j + 1, cities.get(j));
            j--;
        }
        cities.set(j + 1, key);
    }

for example...

answered Mar 3, 2015 at 2:25

MadProgrammer

348k22 gold badges243 silver badges379 bronze badges

2 Comments

A.J Over a year ago

Thank you for the detailed answer, but the issue was in the condition. It should be in reverse order like this: j > 0 && cities.get(j-1).compareToIgnoreCase(v) > 0

MadProgrammer Over a year ago

I tried that originally, but it didn't seem to work, some I reworked the entire code

Collectives™ on Stack Overflow

Insertion Sort Strings

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related