Searching and Sorting in C++

gaui3d0pnbz86o

Just a quick question, what is the most effective way to search through a linear list or array? there has to be a better way then simply comparing to the first then second then third ect, till found.
or is there?

fatherdougalmag

You have a couple of options open to you. But first, the structure of the data must reflect, to some degree at least, what you're going to be doing with it.

In other words, you should structure your data for searching. Look into binary trees, tries, etc.

But if you want to stick with a good old array I would recommend that when you are adding stuff to the array, you use insertion sorting. As you add items, look for the place where they should go so that they are kept in order. With arrays, this may mean that you have to shift lots of data around to make space for new items. If you're not restricted to an array, I'd suggest a linked list. If you can guarantee that your array is sorted, then you can use a simple binary search. With this method, you start in the middle and determine which half of the array your search item is in (upper or lower half). You then treat that as a new array, start in the middle and ask the question again. You'll eventually hit it. It's a bit like looking for a word in a dictionary (or a name in a telephone directory). You make a decision 'Is the word I'm looking for before or after the one that I'm looking at?'. Then you move backwards or forwards as appropriate.

Hope that helps

gaui3d0pnbz86o

given that it is a unsorted linked list
is there faster then binery search, since the binery search would mean the list has to be sorted?

thanks

hussey

is that not quicksort your taling about : Quicksort uses a divide and conquer approach, dividing the total array in half, then recursively dividing each half info halves, and those halves into halves and so on and so on. Eventually, it just has two values, and can swap them if needed. While this is not exactly how a Quicksort works, it is a general description. What to remember is that a Quicksort uses a divide and conquer approach utilizing recursion. This leads to a big O of N log N.

you can find java code for QS HERE

Insertion sort (link ) : One of the simplest methods to sort an array is an insertion sort. An example of an insertion sort occurs in everyday life while playing cards. To sort the cards in your hand you extract a card, shift the remaining cards, and then insert the extracted card in the correct place. This process is repeated until all the cards are in the correct sequence. Both average and worst-case time is O(n2).

I found a nice overview of sorting
HERE

fatherdougalmag

Sorry hussey if you missed the point but I was describing a method for searching when I was talking about dividing in half.

flameboy, I don't believe there's any short-cut you can take. If the list is unsorted, you'll just have to go through it one by one.

If you want to get really clever, you could make your list doubly-linked (it has forward and backward pointers) and then kick off 2 threads. One could search the array from start to end and the other could search from end to start.

Worse again, you could divide the list into two halves and create four threads with two threads working on each half.

hussey

Sorry Father .. you were describing searching, I thought you were talkin about sorting .. appoligies

instead of having an unsorted LL/array, can you convert this to a sorted array first then search?

gaui3d0pnbz86o

hmmm
i was thinking of searching from two ends, but wont that take the same amount as going from one too the other?

if it doesnt they why not get the half, work both ways in both halfs at the same time instead of fividing the list?

or am i making things too comlacated? im talking about 100,000+ elements to search through.



thanks again

gaui3d0pnbz86o

i suppose i could sort it, but would sorting such a large amount be benifical? i mean would time taken to sort then search, be quicker then searching unsorted?

hussey

Originally posted by flameboy
i suppose i could sort it, but would sorting such a large amount be benifical? i mean would time taken to sort then search, be quicker then searching unsorted?

sorry I didn't really make that clear, is it possible to sort them as they are added?
then you could do the searching method dougal was talkin bout?

or are you given an unsorted list?

if you are given an unsorted list, it would depend on how many searches you are to do, if it is low, then prob not worth your while sorting first, if it is high then maybe it is

gaui3d0pnbz86o

yup its given to me as unsorted,

its a nightmare of a project, so it'll probably never be used after next week.

sorting a list that will be fun!

fatherdougalmag

Go figger! You tell us how you get on. Try both methods: sorted and unsorted. You'd need to run your app a few times to get average values.

Regarding the searching from both ends approach. You're right if you just use a regular program. You can create two threads which run in parallel. This means that they'd be both working through the list at the same time (in parallel) and not in sequence. Although this isn't strictly true (if you're running on a uniprocessor machine) it's near enough to what the end result would be. Throw that in as option three in addition to the sorted and unsorted.

Feel free to experiment (if you have the time). It will be worth it in the end and you'll learn a lot.

hussey

Yeah it will be worth it, I remember i had a C++ project on binary trees, ie given a unsorted text file, with name+number, we had to sort it by name, I decided to do balanaced binary tree method, I gave me a great understanding of pointers. -something which I hadn't got a clue about

gaui3d0pnbz86o

of corse ill let ya all know how i get on,

there is nothing stopping me, from running the program on two machines. could one machine handle one end of the search and another the other,or splitting the list to smaller ones and distributing them to many machines?

i havent looked into too much paraell prog yet. could be an option.

fatherdougalmag

What OS/platform are you on? Threads are a doddle on Win32. They're no big deal. The thing to be careful of is writing to global data/variables. But since searching is a read operation, you'll come to no harm.

I'm sure there'll be brownie points for
a) multi-threading
b) providing results from experiementing different methods

gaui3d0pnbz86o

windows nt. i could use unix if its easier for things this.

well i want all the brownie points, there E50 for the best!
best is who evers is fastest and most efficent for memory useage, has to be in c++, besides that anything goes

Gavin

try the C++ standard template library.

http://www.codeproject.com/vcpp/stl/


prebuilt classes, designed to do this sort of thing.

Gav

gaui3d0pnbz86o

cheers verb.