Binary-algorithm -> Insert String to sorted String-ArrayList

[Muskar]

Hey all.

As far as I know this algorithm isn't there by default and I need it for my new project - because it will contain ArrayLists with a very large amount of Strings in them.
Therefore I thought that instead of sorting after every String is inserted, I'd rather come up with an algorithm that inserts the String to it's right place.

The idea is to simply used the binary search algorithm that halves the amount of options every time.
Unfortunately I have no idea how the "natural order"-sorting works, so I'm only doing the basic one (unless you guys have some easy optimization?) with .compareTo().

Now, I've tested this algorithm in all the ways I could think of:

• The list is empty
• The list has only identical Strings
• The list has only Strings with lower value than the String to insert
• The list has only Strings with higher value than the String to insert
• The list has many identical Strings

Now I know I may be asking a lot here:
Do any of you have advice of optimization? Perhaps obvious flaws? Or maybe even just things that I should test?
(Note: I know that a few if-sentences could contain less arguments - however, I want to be able to read it again later).

Additional Questions:
When this method is fully optimized, I'm considering making it take a String[] instead - and return a new one - since it gives a quicker performance (am I right about this?).
I recall that I could use the parameters (Comparable[] arr, Comparable x) - and it would work for other things than Strings as well. Is this correct?

[color="#3F5FBF"]/**
 * <b>Requires</b>: List is sorted from A-Z-a-z <i>OR</i> z-a-Z-A<br \>
 * <br \>
 * Automatically determines whether your list is ascending or descending.<br \>
 * <b>Note</b>: If all items in the arrayList are identical, the list order
 * is assumed ascending.
 * 
 * [color="#7F9FBF"]@[B]param[/B][/color] sortedList
 *            the String-ArrayList to insert to.
 * [color="#7F9FBF"]@[B]param[/B][/color] toBeInserted
 *            the String to insert.
 * [color="#7F9FBF"]@[B]author[/B][/color] Muskar
 */[/color]
[b][color="#7F0055"]public static void[/color][/b] insertToSorted(ArrayList<String> sortedList,
        String toBeInserted) {
    [b][color="#7F0055"]boolean[/color][/b] inserted = [b][color="#7F0055"]false[/color][/b];
    [b][color="#7F0055"]if[/color][/b] (sortedList.size() == 0) {
        sortedList.add(toBeInserted);
        inserted = [b][color="#7F0055"]true[/color][/b];
    }
    [b][color="#7F0055"]int[/color][/b] left = 0;
    [b][color="#7F0055"]int[/color][/b] right = sortedList.size() - 1;
    [b][color="#7F0055"]int[/color][/b] middle = -1;
    [b][color="#7F0055"]int[/color][/b] k;
    [b][color="#7F0055"]boolean[/color][/b] ascending = [b][color="#7F0055"]true[/color][/b];
    [b][color="#7F0055"]if[/color][/b] (sortedList.get(left).compareTo(sortedList.get(right)) > 0) {
        ascending = [b][color="#7F0055"]false[/color][/b];
    }
        System.[color="#2A00FF"]out[/color].print([color="#2A00FF"]"The list is "[/color]);
    [b][color="#7F0055"]if[/color][/b] (ascending) {
        System.[color="#2A00FF"]out[/color].println([color="#2A00FF"]"ascending."[/color]);
    } [b][color="#7F0055"]else[/color][/b] {
        System.[color="#2A00FF"]out[/color].println([color="#2A00FF"]"descending."[/color]);
    }
        [b][color="#7F0055"]if[/color][/b] (ascending && !inserted) {
            [color="#3F7F5F"]/*
         * If the first String in the list has a greater value than
         * toBeInserted then no search is required - and toBeInserted is
         * then inserted to the first index.
         */[/color]
        [b][color="#7F0055"]if[/color][/b] (sortedList.get(left).compareTo(toBeInserted) > 0) {
            sortedList.add(left, toBeInserted);
            inserted = [b][color="#7F0055"]true[/color][/b];
        }
            [color="#3F7F5F"]/*
         * If the last String in the list has a lower/the same value than/as
         * toBeInserted then no search is required - and toBeInserted is
         * then inserted after the last index.
         */[/color]
        [b][color="#7F0055"]else if[/color][/b] (sortedList.get(right).compareTo(toBeInserted) <= 0) {
            sortedList.add(toBeInserted);
            inserted = [b][color="#7F0055"]true[/color][/b];
        }
            [b][color="#7F0055"]while[/color][/b] (!inserted && left <= right) {
            middle = (left + right) / 2;
            k = sortedList.get(middle).compareTo(toBeInserted);
            [b][color="#7F0055"]if[/color][/b] (left == right || left == right - 1) {
                    [b][color="#7F0055"]int[/color][/b] kNext = sortedList.get(middle + 1).compareTo(
                        toBeInserted);
                [color="#3F7F5F"]// If there's only 1 option left in the end:[/color]
                [b][color="#7F0055"]if[/color][/b] (left == right) {
                    [b][color="#7F0055"]if[/color][/b] (k < 0) {
                        sortedList.add(middle + 1, toBeInserted);
                    } [b][color="#7F0055"]else[/color][/b] if (k > 0) {
                        sortedList.add(middle, toBeInserted);
                    }
                }
                [color="#3F7F5F"]// If there's 2 options left in the end:[/color]
                [b][color="#7F0055"]else if[/color][/b] (k <= 0 && kNext > 0) {
                    sortedList.add(middle + 1, toBeInserted);
                } [b][color="#7F0055"]else if[/color][/b] (k < 0 && kNext <= 0) {
                    sortedList.add(middle + 2, toBeInserted);
                } [b][color="#7F0055"]else if [/color][/b] (k > 0 && kNext > 0) {
                    sortedList.add(middle, toBeInserted);
                }
                inserted = [b][color="#7F0055"]true[/color][/b];
            } [b][color="#7F0055"]else[/color][/b] {
                [b][color="#7F0055"]if[/color][/b] (k == 0) {
                    [color="#3F7F5F"]/*
                     * This only happens if 'middle', during the search,
                     * finds a String in the list with the exact same value
                     * as toBeInserted.
                     */[/color]
                    sortedList.add(middle, toBeInserted);
                    inserted = [b][color="#7F0055"]true[/color][/b];
                } [b][color="#7F0055"]else[/color][/b] if (k > 0) {
                    right = middle - 1;
                } [b][color="#7F0055"]else[/color][/b] if (k < 0) {
                    left = middle;
                }
            }
        }
    }
        [b][color="#7F0055"]else if[/color][/b] (!ascending && !inserted) {
        [color="#3F7F5F"]/*
         * If the first String in the list has a lower/the same value
         * than/as toBeInserted then no search is required - and
         * toBeInserted is then inserted to the first index.
         */[/color]
        [b][color="#7F0055"]if[/color][/b] (sortedList.get(left).compareTo(toBeInserted) <= 0) {
            sortedList.add(left, toBeInserted);
            inserted = [b][color="#7F0055"]true[/color][/b];
        }
        [color="#3F7F5F"]/*
         * If the last String in the list has a greater value than
         * toBeInserted then no search is required - and toBeInserted is
         * then inserted after the last index.
         */[/color]
        [b][color="#7F0055"]else if[/color][/b] (sortedList.get(right).compareTo(toBeInserted) > 0) {
            sortedList.add(toBeInserted);
            inserted = [b][color="#7F0055"]true[/color][/b];
        }
            [b][color="#7F0055"]while[/color][/b] (!inserted && left <= right) {
            middle = (left + right) / 2;
            k = sortedList.get(middle).compareTo(toBeInserted);
            [b][color="#7F0055"]if[/color][/b] (left == right || left == right - 1) {
                    [b][color="#7F0055"]int[/color][/b] kNext = sortedList.get(middle + 1).compareTo(
                        toBeInserted);
                [color="#3F7F5F"]// If there's only 1 option left in the end:[/color]
                [b][color="#7F0055"]if[/color][/b] (left == right) {
                    [b][color="#7F0055"]if[/color][/b] (k > 0) {
                        sortedList.add(middle + 1, toBeInserted);
                    } [b][color="#7F0055"]else if[/color][/b] (k < 0) {
                        sortedList.add(middle, toBeInserted);
                    }
                }
                [color="#3F7F5F"]// If there's 2 options left in the end:[/color]
                [b][color="#7F0055"]else if[/color][/b] (k > 0 && kNext <= 0) {
                    sortedList.add(middle + 1, toBeInserted);
                } [b][color="#7F0055"]else if[/color][/b] (k <= 0 && kNext <= 0) {
                    sortedList.add(middle + 2, toBeInserted);
                } [b][color="#7F0055"]else if[/color][/b] (k > 0 && kNext > 0) {
                    sortedList.add(middle + 2, toBeInserted);
                }
                inserted = [b][color="#7F0055"]true[/color][/b];
            } [b][color="#7F0055"]else[/color][/b] {
                [b][color="#7F0055"]if[/color][/b] (k == 0) {
                    [color="#3F7F5F"]/*
                     * This only happens if 'middle', during the search,
                     * finds a String in the list with the exact same value
                     * as toBeInserted.
                     */[/color]
                    sortedList.add(middle, toBeInserted);
                    inserted = [b][color="#7F0055"]true[/color][/b];
                } [b][color="#7F0055"]else if[/color][/b] (k < 0) {
                    right = middle - 1;
                } [b][color="#7F0055"]else[/color][/b] {
                    left = middle;
                }
            }
        }
    }
}

[Muskar]

Bumped for moderator request (I'm not sure if it's allowed to do this but I'm giving it a shot):

Can I ask a moderator to kindly add the following tags to this topic:

binary search, algorithm, arraylist string, insertion sort, insert to sorted

Since this topic seems to be falling dramatically into the pile of unreplied topics, I think I'd like to request to get the topic moved to Advanced Java instead, if I may.

[Fubarable]

I have added tags and have moved the thread per your request. Perhaps the reason for lack of a response is that most of your question is less a pure Java question and more of an algorithms question. Much luck!

[Muskar]

I have added tags and have moved the thread per your request. Perhaps the reason for lack of a response is that most of your question is less a pure Java question and more of an algorithms question. Much luck!

You're probably right, ah well, I'll just leave it be and hope for any contributions at all... even just an answer to one of the additional questions.

And thanks, Fubarable, for the mod actions :)

[couling]

I don't see anything wrong with you're idea in principle (I havn't run your code).

I'll assume you had good there a reason not to extend the ArrayList class and override the add method. And I assume you want the index access and therefore the TreeSet would be inappropriate.

Your code identifies which order the list is sorted by interrigating the elements. This seems dangerous, what happens if the list contains 1 element, is the function really allowed to arbitarily pick an order? It's more common to pass the order as a seperate arguement.

That said:

boolean ascending = true;
if (sortedList.get(left).compareTo(sortedList.get(right)) > 0) {
    ascending = false;
}

Could read:

ascending = (sortedList.get(left).compareTo(sortedList.get(right)) <= 0)

When this method is fully optimized, I'm considering making it take a String[] instead - and return a new one - since it gives a quicker performance (am I right about this?).

Copying the list will come with an overhead so be warned that this could be situation dependant. You would have to look into algorythms to handle adding an arry. But If you are adding an array to a sorted array considder sorting the array to add then merging the two.

If you are adding a lot of elements at once, then this may be quicker but you'd have to test.

Hope this helps

[JosAH]

I see one detail I would've done differently: your code basically looks like this:

if (ascending)
   // do a whole lot of stuff
else
   // do a whole lot of similar stuff

I'd add a little helper method:

int compare(String a, String b, boolean ascending) {
   int c= a.compareTo(b);
   return ascending?c:-c;
}

The compare method returns 'the other thing' if it is descending, otherwise it returns whatever a.compareTo(b) returns. So the rest of your code boils down to:

// do a whole lot of things in terms of the compare( ... ) method

This way you avoid a whole lot of code duplication ...

kind regards,

Jos

[Muskar]

I don't see anything wrong with you're idea in principle (I havn't run your code).

I'll assume you had good there a reason not to extend the ArrayList class and override the add method. And I assume you want the index access and therefore the TreeSet would be inappropriate.

First of all, when it comes to more off-road questions like this one, it's hard to get contributions, so thanks a lot for replying, I really appreciate it!

It's not extended from ArrayList because I was keeping the possibilities open (changing the method to handle arrays instead).

To be honest, this topic is only here in Advanced Java because there were nobody answering in New Java (I'm guessing people there are used to easy questions) - and with that said: I'm not that experienced in Java.
Now as far as I my quick Google-research tells me, this TreeSet does exactly what I want my entire method to do. So, even though it just seems like you're trying to imply suggestions by kindly "assuming" that I already thought of using them (and thanks by the way), I'm still wondering what exactly do I need the index access for? (I assume "index access" has to do with knowing what indexes you're using.)
If TreeSet does exactly what I want my method to do, and it does it with an optimized speed, then I see no reason to not use it.

Could you perhaps tell me a few disadvantages vs. ArrayList?

Your code identifies which order the list is sorted by interrigating the elements. This seems dangerous, what happens if the list contains 1 element, is the function really allowed to arbitarily pick an order? It's more common to pass the order as a seperate arguement.

Yeah I know - and you're right - because what if we, in a use-case, have 2 descending-ordered elements, and we delete one of them - and then add a new one (among all other cases where we get by having only identical elements in the list). Then the order would be set to ascending, even if we didn't request it. And I see no way to automatically detect the order when there's only 1 element.

So I'll change it back to being a parameter again then.

Copying the list will come with an overhead so be warned that this could be situation dependant. You would have to look into algorythms to handle adding an arry. But If you are adding an array to a sorted array considder sorting the array to add then merging the two.

If you are adding a lot of elements at once, then this may be quicker but you'd have to test.

Hope this helps

I was thinking about writing the method:

public static Comparable[] insertToSortedArray (Comparable[] a, Comparable c) {...}

It shouldn't be inserting an array to an array - it should just be inserting an element and creating a new array with all the elements in, and obviously returning it returning returning it. I'm thinking I'll make a separate helper method that adds a Comparable Object into an array at a certain index - just to keep it from being messy:

public static Comparable[] addToArrayAt (Comparable[] a, Comparable c, int i) {...}

*
*.*
˜*•.˜*•.•*˜.•*˜
˜*•.˜”*°•.˜”*°•.•°*”˜.•°*”˜.•*˜
~° JosAH °~
.•*˜.•°*”˜.•°*”˜”*°•.˜”*°•.˜*•.
.•*˜.•*˜*•.˜*•.
.•˜•.
*

I see one detail I would've done differently: your code basically looks like this:

if (ascending)
   // do a whole lot of stuff
else
   // do a whole lot of similar stuff

I'd add a little helper method:

int compare(String a, String b, boolean ascending) {
   int c= a.compareTo(b);
   return ascending?c:-c;
}

The compare method returns 'the other thing' if it is descending, otherwise it returns whatever a.compareTo(b) returns. So the rest of your code boils down to:

// do a whole lot of things in terms of the compare( ... ) method

This way you avoid a whole lot of code duplication ...

kind regards,

Jos

If I'm understanding you correctly, then I also considered the same option - although I ran into a few snags.

What I couldn't figure out is how one would do the following example (just to take one of the "similar stuff" parts):

Ascending

// If there's 2 options left in the end:
else if (k [B][color="#0066CC"]<=[/color][/B] 0 && kNext [B][color="#0066CC"]>[/color][/B] 0) {
    sortedList.add(middle + 1, toBeInserted);
} else if (k [B][color="#0066CC"]<[/color][/B] 0 && kNext <= 0) {
    sortedList.add(middle + 2, toBeInserted);
} else if  (k > 0 && kNext > 0) {
    sortedList.add([B][color="#0066CC"]middle[/color][/B], toBeInserted);
}
inserted = true;

----Versus----

Descending

// If there's 2 options left in the end:
else if (k [b][color="#CC0000"]>[/color][/B] 0 && kNext [b][color="#CC0000"]<=[/color][/B] 0) {               [color="#3F7F5F"]//Opposite[/color]
    sortedList.add(middle + 1, toBeInserted); [color="#3F7F5F"]//Identical[/color]
} else if (k [b][color="#CC0000"]<=[/color][/B] 0 && kNext <= 0) {            [color="#3F7F5F"]//Different but not opposite[/color]
    sortedList.add(middle + 2, toBeInserted); [color="#3F7F5F"]//Identical[/color]
} else if (k > 0 && kNext > 0) {              [color="#3F7F5F"]//Identical[/color]
    sortedList.add([b][color="#CC0000"]middle + 2[/color][/B], toBeInserted); [color="#3F7F5F"]//Different but not opposite[/color]
}
inserted = true;

They are similar indeed, but they are not identical - nor do they oppose each other.
Now of course it's possible to boil them together - but is it possible, in a short, and readable way?
By the first thoughts I'm thinking (ascending && (args1) || !ascending && (args2)) and having extra lines for the cases where they do "non-opposable-stuff".
Although I predict it's going to be (!pretty).

So any help on that complex would be very much appreciated!

[couling]

I'm still wondering what exactly do I need the index access for?

"Index" was possibly a bad word. I can't think of a good reason off the top of my head. An ArrayList is effectively an array which you can re-size on demand. So they're good if you wanted to do myArray[67] or myArray[x] but still want the flexibility of resizing on demand. The basic disadvantage of an ArrayList (as with arrays) is that they don't keep themselves sorted.

A TreeSet lets you add elements and keeps them sorted in a tree structure. If you want to used the the elements in order then use the iterator() function. If you want the TreeSet sorted in decending order then create the set with a Comparitor.


As for your code (just to continue the discussion)....

I agree with JosAH. Rather than passing in a boolean flag for ascending or decending, I'd go the whole hog as suggest using a Comparator.
So your function signature would be:

public static void insertToSorted(ArrayList<String> sortedList, 
        String toBeInserted, Comparator <String> comparator) {
    // when you want to compare String a with String b
    int result = comparator.compare(a,b);
}

//...

class StringComparatorAscending extends Comparator <String> {
    public int compare(String a, String b) {
        return a.compareTo(b);
    }
}

class StringComparatorDecending extends Comparator <String> {
    public int compare(String a, String b) {
        return b.compareTo(a);
    }
}

This effectively lets you flip the sign (> to <) to sort the list in the opposit order simply by wether you pass in a StringComparatorAscending or StringComparatorDecending object.

You could even write a comparitor that ignored words such as "The" and the start of a string for sorting books / films etc.

Hope this helps

[Muskar]

"Index" was possibly a bad word. I can't think of a good reason off the top of my head. An ArrayList is effectively an array which you can re-size on demand. So they're good if you wanted to do myArray[67] or myArray[x] but still want the flexibility of resizing on demand. The basic disadvantage of an ArrayList (as with arrays) is that they don't keep themselves sorted.

A TreeSet lets you add elements and keeps them sorted in a tree structure. If you want to used the the elements in order then use the iterator() function. If you want the TreeSet sorted in decending order then create the set with a Comparitor.


As for your code (just to continue the discussion)....

I agree with JosAH. Rather than passing in a boolean flag for ascending or decending, I'd go the whole hog as suggest using a Comparator.
So your function signature would be:

public static void insertToSorted(ArrayList<String> sortedList, 
        String toBeInserted, Comparator <String> comparator) {
    // when you want to compare String a with String b
    int result = comparator.compare(a,b);
}

//...

class StringComparatorAscending extends Comparator <String> {
    public int compare(String a, String b) {
        return a.compareTo(b);
    }
}

class StringComparatorDecending extends Comparator <String> {
    public int compare(String a, String b) {
        return b.compareTo(a);
    }
}

This effectively lets you flip the sign (> to <) to sort the list in the opposit order simply by wether you pass in a StringComparatorAscending or StringComparatorDecending object.

You could even write a comparitor that ignored words such as "The" and the start of a string for sorting books / films etc.

Hope this helps

Thanks, I really appreciate these effective suggestions.
Although, I must be misunderstanding this, since I cannot seem to see Comparators solved my above issue (with the Ascending vs Descending case).
Despite my lack of understanding exactly how you're suggesting that I can successfully remove the boolean flags, I'd still say it'd cut down all those "if ((...).compareTo(...))"-sequences

[JosAH]

Thanks, I really appreciate these effective suggestions.
Although, I must be misunderstanding this, since I cannot seem to see Comparators solved my above issue (with the Ascending vs Descending case).
Despite my lack of understanding exactly how you're suggesting that I can successfully remove the boolean flags, I'd still say it'd cut down all those "if ((...).compareTo(...))"-sequences

Think a bit more abstract: if I consider 10 < 9 and you consider 9 < 10 we're both right given our own algebraic rules. If I sort a sequence in (my) ascending order it will be sorted in (your) descending order and vice versa. One Comparator just returns the opposite of what the other returns and there is nothing wrong with any of them.

kind regards,

Jos

[Muskar]

Think a bit more abstract: if I consider 10 < 9 and you consider 9 < 10 we're both right given our own algebraic rules. If I sort a sequence in (my) ascending order it will be sorted in (your) descending order and vice versa. One Comparator just returns the opposite of what the other returns and there is nothing wrong with any of them.

kind regards,

Jos

Well I know it gives me the option of doing both one thing and the opposite of that - but what for all the other cases - like described in the aforementioned example.

I mean, I may be using a boolean flag - but as far as I understand, we're not dealing with doing exactly the opposite; it's a "some are the same, some are the opposite, some are different"-case.

With the way you guys keep explaining basically the same thing, I feel like I'm missing something right in front of me - but I must honestly say I have absolutely no clue what it is.

[JosAH]

Well I know it gives me the option of doing both one thing and the opposite of that - but what for all the other cases - like described in the aforementioned example.

I mean, I may be using a boolean flag - but as far as I understand, we're not dealing with doing exactly the opposite; it's a "some are the same, some are the opposite, some are different"-case.

With the way you guys keep explaining basically the same thing, I feel like I'm missing something right in front of me - but I must honestly say I have absolutely no clue what it is.

You're drawing your conclusion on the proposition that your code is correct. Why not start from scratch using the Comparators and assuming those Comparators deliver the correct result for the < predicate? If you can do it for an ascending list you have done it for a descending list. That's how the relations < and > are defined.

kind regards,

Jos

[Muskar]

You're drawing your conclusion on the proposition that your code is correct. Why not start from scratch using the Comparators and assuming those Comparators deliver the correct result for the < predicate? If you can do it for an ascending list you have done it for a descending list. That's how the relations < and > are defined.

kind regards,

Jos

You're right, thanks for the tunnel vision cure ;)