Insertion of strings into an ArrayList using a binary search in Java?

Question

So here is my problem: I am trying to do a form of insertion sort. Actually, I am trying to search through an ArrayList using a Binary Search algorithm and find where to insert a string. What I have so far sort of works. It is in partial order. I have been stumped on this for over a week! Below is my code:

EDIT: Sorry I think I confused people. My question is how can I edit this to work properly. It inserts my objects in partial order. I need it to be complete order! I do not know where this is happening. I have far too much data being parsed to debug this line for line too.

    private void insertOrdered(int frontParameter, int endParameter, TwitterData user) {
    int front = frontParameter;
    int end = endParameter;
    int mid = (front+end)/2;

    if (front > end) {
        if (user.getUsername().equalsIgnoreCase(users.get(mid).getUsername()))
            users.get(mid).addTweet(user.getTweets().get(0));
        else
            users.add(mid, user);
    }

    if (user.getUsername().toLowerCase().compareTo(users.get(mid).getUsername().toLowerCase()) < 0) {
        insertOrdered(front, mid - 1, user);
    }

    else if (user.getUsername().toLowerCase().compareTo(users.get(mid).getUsername().toLowerCase()) > 0) {
        insertOrdered(mid + 1, end, user);
    }

    else {    //will get to this case if the usernames being tested are equal
        users.get(mid).addTweet(user.getTweets().get(0)); //if the user is already in the list, just add the tweet. It is assumed that the user being passed in will only have one tweet tied to their information hence the get(0)
    }
}

Just for some background information, I am using this for an ArrayList of Twitter usernames and their associated tweets. The parameter passed, user, is a TwitterData object of a class I wrote. For all intensive purposes all you need to know if I can retrieve the username and a list of tweets that user may have tweeted. Below is a test output of the first 100 users of the list to show you what I mean by it partially working.

First 100 users output:

4colorrebellion
50BandBuckie
2996mymy
20120040
_littlethugg
_IndyaWithaWHY_
__PrettyMistake
__Mannyy24
_MikeFishh
_NikeDeshaun_
_TinaBeana
_PrincesaNessa
_LoveInPaaaris
_Victoria_Ortiz
adriannstacey21
ahansen718
action_packed_
Alicemegan93
alexgracehunter
AlishaaShaffer
arowsey_15
Amy_Vee
allycolucci
AmbiTious___xO
aguss__A
averybrownn
babbyyy_itsREAL
ando775
bburns1117
amberdorais
AshMarieMonica
Ashton_45
_SarahJustine
BlasianCocaine
belieber_pride
AyeeIts_DeeDee
BrianHodges
BritFranceNews
Big_Red911
BiteMy_SlimJim
BadGirlYon
Cemonee_Allisse
cathy_riveros
byby_35
CEOSIXX
busybeekatie
ChelsiKatherine
BOOBtifulJohnny
Coolie_Mackin
coralreefer420
CrashBandaCooch
codyalexander23
cubanrice
corrinea143
Cyndi_R82
danny728_
dbangin
ASNievera
DeAndre_Johnson
Deion_Hungry
DStudmuffin
cowellEmma
expired_data
Dr_drew_V93
feather_hinn
DominiqueQ2
getbackamistake
Da_Dirty_Dern
dudeimisaac
elennatalbert
evillurking
fANNcy_
covolm4
HimOverHere
DameLush
erinnnroach
freaky_fahfah
freesugardaddy
elhotpocket
FollowMandy
HaileyySorenson
DomoNinjaSwagg
IamSalinaScott
fredthemarauder
IAmTHATguy_1
facucuellar
iDream_Mindless
hirschy_kiss94
freshmoney5
HannahMcC_x
GarrieBrocato
AyeeeCali
iSexTattedDudes
Illumi_Lani
itsyunk
jahzzi
Jamie_Hill101
iHeartAudiooooX
jaymethornley
JasonMyers18

One more thing, the last else case does work properly. I have eliminated any kind of dual users being submitted to the ArrayList. Any ideas?

If its not homework you can simply use Collection.sort() with appropriate comparator. — Ashwinee K Jha
– Ashwinee K Jha, Commented Feb 25, 2012 at 17:57
AKJ, I am curious as to the time required for sort(). It is not hommework, so I will certainly try that but just off of the top of your head do you know the big O of Collection.sort()? This insertion I worked to be n*log(n) I believe. Deporter, I am trying to fix the code. It does not insert properly. — takisback
– takisback, Commented Feb 25, 2012 at 18:00
I'm sorry, Nrj, my problem is the insertion ends up with a partially sorted list, I need a completely sorted list. For some reason things are not added properly. It is an abstract question yes, but I was hoping to get some insight at least. — takisback
– takisback, Commented Feb 25, 2012 at 18:05
If front is greater than end, then you haven't found what you are looking for, so I am not sure that inserting at index mid in the list is the right choice at that point. — Hunter McMillen
– Hunter McMillen, Commented Feb 25, 2012 at 18:08

Hunter McMillen · Accepted Answer · 2012-02-25 18:19:24Z

1

This would be a lot simpler if you just inserted elements anywhere in the list and called Collections.sort() it would take the same amount of work as you already calculated for your insertion O(n*logn)

answered Feb 25, 2012 at 18:19

Hunter McMillen

61.8k25 gold badges124 silver badges176 bronze badges

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

1 Comment

takisback Over a year ago

Hmm, yes, I came to that realization in the comments. Thank you though!

Collectives™ on Stack Overflow

Insertion of strings into an ArrayList using a binary search in Java?

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related