Best sort algo?

[WildHeart]

Hello. I have a vector of objects. I can't use arrays for this project. In an old topic, a member asked for sorting algorithms and graham suggested bubble sort HOWEVER the condition was that he use it on an array of size 30 or less. What if I had more items? say 100 or more? I stated in previous topics that i put the rms data in vectors in the form of objects so that i don't give my mobile processor and memory any grief. instead of constantly performing operations on my rms, i just do so on the vector and then the rms when needed (example delete method). So I can't use comparator. I can't implement it. It'd have been easier for me to use comparator but im trying to avoid the grief part. So what's the best algo out there for sorting vectors?
Thanx

[njzk2]

depends on the entropy of your data.
there are, imho, 3 sorts that are useful in general case :
merge sort, because it is beautifully simple and fast
slow sort if you need the first or the n firsts elements only (don't use it otherwise)
bubble sort, if you have elements close to their correct position. (and actually the cocktail sort is a good upgrade)

then some other sort are specific to the kind of data you are considering like known-range integer are sorted with bucket sort ...

if you want to maintain a vector sorted, work only on the elements that change (inserted or modified elements) : find their new place when needed using a binary search.

[petrib]

http://en.wikipedia.org/wiki/Quicksort

[WildHeart]

thanx a lot. im familiar with most of these algos. please give me ur opinion one last time after you read the details regarding my vectors.
vector1: contains objects. each object contains 11 strings
vector2: contains objects. each object contains 1 string 1 image

vector1 and vector2 have one common string in common. index. so if i choose index 3 of vector 1, then index 3 of vector 2 will be teh right related element.

Sorting:
1- sort vector1. select second element in vector1. get the string index of tht element. say the index is 3. do a forloop on vector 2 where u take each element of vector2, get it's index and compare with index from vector1. keep doing it until the indexes match. then display the image of that element in vector 2

2- sort vector1 and 2. w/e index u get from vector1 will match the vector2 index. no need for a for loop

im going with the first method because sorting 1 vector + 1 for loop beats sorting 2 vectors i put the images in ad fiferent store anda different vector because i was told that storing everything together is really heavy. basically it's not a good idea.


bubble sort: wht did u mean when u said if i had elements close to their correct position? i dont understand sorry.
cocktail sort: no idea what that is butim sure i'll get it if u answered the above question

as for your last paragraph regarding mainting a sorted vector at all times, i considered it. but im completely sure about it.
when i log in, the vectors get their data from the rms. so when accessing an image or a string or searching or sorting, it'll be applied to the vectors only. so when i get the data i'll sort them based on criteria1. and by default if i delete an element off a vector, the rest of the elements will shift. so if it was size 3 with elements 1 2 3 and i deleted 2 then it'll b size 2 elements 1 3. so when i delete an element from a vector, the elements will shift and i'll maintain sort order by criteria1.
i can change the sort criteria. if i delete an element after the sort isp erformed then the same concept applies. if the vector is sorted and i delete an element, sort order will remain intact.
the only issue is when i update x elements. this is exactly the issue tht im having now. when i update the elements, i'll need to sort them again. HOW? bubble? quick? merge? other?

petrib ill compare quick and merge to decide the best. it doeslook like it'll come down to these two ty

[njzk2]

i'm not really sure having 2 vectors is such a great idea. may be you should consider only one vector.
As for your first method, it seems that only one vector is sorted in the end ? if you don't sort you second vector, you can use a Hashtable using your index string as key.

[WildHeart]

ty for the quick reply. i have strings and images. if i dont store them in seperate vectors then that means ill have to store them in the same vector. so which is better? T-T
yes only one vector is sorted. a for loop is used to access the related element in vector 2 after getting the index from vector1. basically sorting two vectors will take it's toll rather than one sort and one for loop. the first method is like saying u want to pick a number from the list then go to a new list and find out what that number has. or in a game show LETS SEE WHATS BEHIND DOOR NUMBER 2!

[njzk2]

so, if i sum this up, correct me if i am wrong :

you have a vector of data, each data is composed of 11 strings. you pick one of those strings as a base for your sort, then find the Nth element index and use this index to find the corresponding image.

you can totally use only one vector and sort everything in it.
it will be much easier.

[WildHeart]

EDIT: nothing. ignore this pointless msg. the next one is better

[WildHeart]

I made a mistake so plz read this:
vector1 is composed of x elements (objects). each object has 11 strings. the important strings are the first and second strings called INDEX and NAME.

vector2 is composed of x*2 elements. first element is the INDEX which is the same valuewise as the one in vector1. second element is the image. so element 0 is INDEX element 1 is image element 2 is INDEX element 3 is image and so on. vector2 is twice the size of vector1.

Example
Vector1: size = 3
1 wild str3...str11
2 alex str3...str11
3 troy str3...str11

Vector2
1 wildimage
2 aleximage
3 troyimage

main screen displays the names of vector1 so
wild
alex
troy

to display the image of alex, i'll select alex from mainscreen. this will return the index (this.getselectedindex()). then i just open the image in vector2 at the selected index.
so in this case, the selectedindex is 1 so i display element 1 in vector2.

First question: Plz tell me why it's better to use one vector instead of 2? I download and process my records from an online source. Records are downloaded then I insert/delete/update the rms with these records. then i create vector1 and 2 to hold the data and images so that i dont have to access the rms again to sort/search/viewimage. assume each there are 100 records downloaded.
What do you think? two vectors or one?

Second question: i read several sites. performance and memory wise, i should use quick sort. faster, less overhead, and it's inplace unlike mergesort which requires additional storage. there have been discussions about variants of either algos but i dont no anything about that. im just going to download the 'normal' implementation of sort. I'd like your opinion as to whether I should use this algo or another.

Third and final question: correct me if im wrong but 1- better version of quick sort is median of 3 2- despite median of 3 being better, it's O(n) so thts bad 3- i still need median of 3 because randomizing the pivot will make things worse.

[traud]

WildHeart, we do not know all your constraints. I do not think, you can discuss this, the way you are doing, except we get the full source code or a complete optimisation analysis. In the latter case, you do not need us anymore. Reading your text, I ask my self: Why isn’t WildHeart using HashTable(s). Please, get a specialist in your vicinity and show him your code.

[WildHeart]

Hello. Unfortunately there are no specialists in my vacinity. I live in Dubai in the UAE. I've contacted Nokia and they said they have no developers here. They're all living abroad. I wish I had someone to avoid confusing posts like the previosu ones
I'm here to do it one more time. I'm not changing the topic. To decide on the best sort algo, you need to know how it works.

online database has a table of 4 fields: username, name, age, country. the images of every user are stored there as well. the imagename = name of user. so my name is leo therefore my image is leo.jpg

mobile app:
first class is USERS class. in it are 5 declared strings. 4 resemeble the 4 fields in teh online table. the 5th is the recordID string

first vector is USERS vector
second vector is IMAGES vector
third vector is NAMES vector

first rms is USERS rms
second rms is IMAGES rms

there are other classes of course but this is what you need to no for the project. at least regarding my problem.

now for my process:
1- i download the data online. first record is wildheart25c, leo, 19, US
2- i save these 4 strings in a record in USERS rms
3- i create an object of type USERS and save this info in it along with the recordID which i get fromt he previous step
4- i insert this object in USERS vector
5- i insert the name string in the NAMES vector
6- repeat processes 1-5 until all the records have been downloaded
7- i download the images using a for loop. the following steps are what happen inside the for loop
8- save the image in a record in the IMAGES rms
9- insert the image in IMAGES vector
10- repeat until i > NAMES.size();

example just to b sure you're with me so far
online db:
wildheart leo 19 US
maximus tim 19 US

mobile app:
NAMES vector has leo and tim
IMAGES vector has leo.jpg and tim.jpg
USERS vector has obj1 and obj2 where each obj has info about each user and their recordID

Searching:
i access each object in the USERS vector looking for a certain field value like age=19. if i found it in index0 of USERS vector, then i load the image in index0 in the IMAGES vector

Deleting:
access each obj until you find the name you want to delete. when you find it, the obj contains the recordID. use that ID to access the USERS and IMAGES rms and delete that record

Insert:
this means downloading new records. the processes have already been explained

Update:
this means downloading updated records. exiting records with new information. i access each obj until i find the username, change the info in that object, then use the recordID to access the record in the USERS rms to change the info. same goes for the image if there's a new image.

This is what i did and iv tested it on 4 records. no problems. BUT i asked myself if having 2 vectors is a good idea. i have 4 records only. What if i was downloading 100 new records and 20 updated records? would two vectors be a good idea performance and storage wise? and w/e else factor that affects a mobile
So i turned to hashtables. There are two ways to do this using hashtables.
1) 4 fields therefore 4 hashtables. the key is the recordID and the value is each of the 4 strings. So i'll have a hashtable for username, another for name, anther for age and another for country. then a 5th hashtable for the image where the key is the recordID and the value is the image itself.
2) One hashtable. the key is the users object. the value is the image. or the key is one string ("wildheart-leo-19-US") and the value is the image. Either way when searching and updating i'll have to access each obj/string to find what i want. Ths cancels the idea of using a hashtable because im going through every key until i find the one i want which is pretty much the same as going through a vector

Of course I can just use one vector such that i wont have to use any other temp vector to copy the data from one to the other. Still I don't know if one vector is good.

So this is my prb/s. I can't decide on an algo because I can't decide which storage structure/method to use. I apologize for the long post and for the frustrated members. I hope this post will make up for it :P

[grahamhughes]

It's not clear to me why you have so many separate objects. Why not put the image, name, all the details, in a single "User" object? This is much better than trying to maintain multiple, parallel Vectors.

With 100 to 200 items... sorting is really so trivial on most mobile phones (because they have so much processing power) that it doesn't much matter what sorting algorithm you use. Difference in performance is not likely to be noticeable to the user. You can speed up almost any sorting algorithm by sorting in an array rather than a Vector.

As for the correct structure... I'm not clear how you want to access a specific User. If you want to display a list, use getSelectedIndex() and find the matching object, then simply add the objects to a Vector as you add them to the List, so that the List entries and the objects in the Vector will be in the same order.

Remember: if you want to access the objects in more than one way, you can store them in more than one Vector/array/Hashtable/etc. This is not expensive... when you store the object, you are storing only a reference to it, not a copy of it. If you add the object to two Vectors and a Hashtable, there is still only one object, just with three references to it.

Does that help?

Graham.

[WildHeart]

i must say that today is full of surprises. I've approached 2 colleagues regarding this matter. One suggested I use jsr75 because it's faster and better performance than rms. i thought ppl avoided that api because of it's security hassle, certs, and so on. The other said rms should be fine. no vectors no tables nothing. you can access the rms all you like for w/e purpose and your app wont hang. which is also surprising because the reason why i started using vectors was because i saw that rms alone being constantly accessed was bad.

ur reply is made up of 4 'points' or 'paragraphs'
1- ur right. i should have done that. i will fix it
2- im surprised. when i start mobile programming, the impression i got of mobiles even the new ones is that they're limited. Especially the rms itself.
3- the project started with an rms. nothing else. then i was told that accessing the rms all the time is bad so i when i download new data i should save it in he vector and rms and then work on the vector only. rms onl accessed when i delete or update. so to answer ur question, im adding step 11 to the list of steps in my previous post.
11-after having saved teh data in the rms and vector (well a ref to it according to you) i move from my controller file to my mainscreen file with the ref of a vector (dispaly.setCurrentScreen(new MainScreen(vector))). in mainscreen class, we're in the constructor where the commands forms etc are initialized. and i call the populate method where it opens every object in the vector and prints the name in the form then the form is displayed.
4- for sort and search and viewing the image, i access the vector only. for insert, delete, and update, i access both the vector and rms


ok so in conclusion, ur telling me that 200 records each in image and userdata rms is fine. sorting is fine. and when i create a vector and type vector.addElement(obj1) im only storing the reference not the actual thing o.o this is such a relief :O YES U DID HELP.

but if i had more than 200, should i create extra record stores or consider doing something totally different? basically, how far can i go with the number of records per rms?

noobi question: classA calls methodB in classB passing a vector to it. MethodB has this line: this.vector = vector. What happened here is that i passed a reference to classB right? not the whole thing ya?

[grahamhughes]

One suggested I use jsr75 because it's faster and better performance than rms.

I am aware of no evidence of this. RMS tends to be fast for small numbers of large records, slow for large numbers of small records.

i thought ppl avoided that api because of it's security hassle, certs, and so on.

That's why I avoid it.

The other said rms should be fine. no vectors no tables nothing. you can access the rms all you like for w/e purpose and your app wont hang.

This depends very much on the device. Some devices have, shall we say, less than bug-free implementations of the RMS API.

2- im surprised. when i start mobile programming, the impression i got of mobiles even the new ones is that they're limited. Especially the rms itself.

Again, this depends on the devces you're targetting. Remember that some mobile phones now have 1GHz processors and GBytes of memory.

ok so in conclusion, ur telling me that 200 records each in image and userdata rms is fine. sorting is fine.

Sorting, yes. So far as RMS is concerned... 200 records of simple text, no problem. 200 images... depends on the size of the images, and on the device.

but if i had more than 200, should i create extra record stores or consider doing something totally different? basically, how far can i go with the number of records per rms?

RMS is less about the number of records, and more about the quantity of data (in bytes).

noobi question: classA calls methodB in classB passing a vector to it. MethodB has this line: this.vector = vector. What happened here is that i passed a reference to classB right? not the whole thing ya?

Yes. It is rare that you actually copy an object. The "=" operator only copies references to objects, it never makes copies of objects.

How big are your images?

What device(s) do you want to target?

Graham.

[WildHeart]

in my case it's more like a large number of small size records. 200? 300? mayb 400 too. who knows. my images are 10 to 20kb each. i just checked its property on my server. i recall even putting in some code for my online webiste making sure it doesnt exceed a certain size. my target is shall we say most mobiles that have JVM. so bb, nokia, sony ericcson. Hopefully the mobiles that came out in the last 1 year will b good enough. i just want to be able to move around with as little hassle as possible which is why, like i mentioned, i was surprised at the suggestion i got today (jsr). even if moving the app from nokia to sony for example while using rms can be a prb, it's still a whole lot better than using jsr.