[SOLVED] Ordering a list

snack · 2010-02-02 14:28:11

Hi everybody, I have a little problem which should be common knowledge in the programmers' community, so I hope someone can help me.
I have to build an ordered list of floats, starting from an unordered one. I was wondering if, in principle, it should be faster to put all the numbers in an unordered list and then apply some ordering algorithm or to place directly the values in the new list in an ordered fashion. For this second approach, I was thinking about using STL's list.
Thanks everyone or the help.

Last edited by snack (2010-02-03 08:48:24)

shpelda · 2010-02-02 14:35:43

you're asking whether to use Insertion_sort or something else, maybe Quicksort.

Just read that links:).

If input is read sequentially from something slow(keyboard) then sorting would seem faster using insertion sort.

snack · 2010-02-02 14:39:00

shpelda wrote:

you're asking whether to use Insertion_sort or something else, maybe Quicksort.
Just read that links:).
If input is read sequentially from something slow(keyboard) then sorting would seem faster using insertion sort.

Thank you very much, I'll read the links. My input list is on disk, but in a hardly usable fashion (it's inside a ROOT tree, I hope you will never have to cope with it ). I was thinking about transfering every element in an STL list, and my doubt was the one in my first post.
Do you think that quicksorting would be faster?
Thanks again

shpelda · 2010-02-02 14:48:47

I think so.

Only possible problem i see there is that loading whole content of that disc structure into memory might end up with out of memory. But this is another problem.

grey · 2010-02-02 14:50:53

That depends on (a) the ordering algorithm and (b) how you insert the values into the new ordered list.

snack · 2010-02-02 14:57:36

shpelda wrote:

I think so.
Only possible problem i see there is that loading whole content of that disc structure into memory might end up with out of memory. But this is another problem.

It's a matter of about 1.5e7 floating point numbers, which would require (correct me if I'm wrong) 1.5e7 * 4 bytes = 6e7 bytes = 60 MB, plus some overhead introduced by using something like STL list. Nothing to take care of anyway, I think.

@grey: my idea was to use a quicksort algorithm to sort the list, or to insert the elements by searching the list starting from the last insertion point and going up or down abd then using list::insert.

the_isz · 2010-02-02 15:11:06

The STL already has sorting functionality, no need to re-invent the wheel:

http://www.cplusplus.com/reference/algorithm/

snack · 2010-02-02 15:12:37

the_isz wrote:

The STL already has sorting functionality, no need to re-invent the wheel:
http://www.cplusplus.com/reference/algorithm/

Thank you, I will surely use something like this if I decide to go the sorting way

grey · 2010-02-02 15:52:26

What I would do:
1. create stl::vector V that is large enough, using reserve ()
2. add the numbers using push_back
3. sort (V.begin(), V.end())

snack · 2010-02-02 15:58:36

grey wrote:

What I would do:
1. create stl::vector V that is large enough, using reserve ()
2. add the numbers using push_back
3. sort (V.begin(), V.end())

According to http://www.cplusplus.com/reference/stl/list/ lists should give better performance with sorting:

Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

The only drawback is that inserting elements may be faster with vectors than with lists...
I'm making some experiments with ordered insert and STL sort, I'll report as sson as I have results (for those who are interested).

grey · 2010-02-02 17:28:03

Both lists and vectors sort in n*log(n). I didn't know that about lists, but you can see for yourself: the implementation is in
/usr/include/c++/4.4.3/bits/forward_list.tcc , function _M_sort_after.
I doubt that you'll see a difference unless your lists are huge.
Also, insertion at the back of the container is O(1) for both lists and vectors if the vector has sufficient reserved space.
http://www.cplusplus.com/reference/stl/list/ is IMO wrong as far as the built-in sorting functions are concerned.

snack · 2010-02-03 08:48:05

According to my test, in my implementation there's not so much difference between insertion sort with lists, list::sort, STL sort with a vector or C's qsort. Ordered insert is the slowest, with a mean of 6.80 s in sorting a small sample, while ordering algorithms are all between 6.30 and 6.40 s. Maybe it's possible to improve something somewhere, but I'm happy with these timescales so I'll stop my experiments and go on with my work. I think I will go with list::sort, maybe it can be faster than STL sort for larger datasets and its implementation is less awkward than that of qsort.
Thanks everyone for the help!

Arch Linux

#1 2010-02-02 14:28:11

[SOLVED] Ordering a list

#2 2010-02-02 14:35:43

Re: [SOLVED] Ordering a list

#3 2010-02-02 14:39:00

Re: [SOLVED] Ordering a list

#4 2010-02-02 14:48:47

Re: [SOLVED] Ordering a list

#5 2010-02-02 14:50:53

Re: [SOLVED] Ordering a list

#6 2010-02-02 14:57:36

Re: [SOLVED] Ordering a list

#7 2010-02-02 15:11:06

Re: [SOLVED] Ordering a list

#8 2010-02-02 15:12:37

Re: [SOLVED] Ordering a list

#9 2010-02-02 15:52:26

Re: [SOLVED] Ordering a list

#10 2010-02-02 15:58:36

Re: [SOLVED] Ordering a list

#11 2010-02-02 17:28:03

Re: [SOLVED] Ordering a list

#12 2010-02-03 08:48:05

Re: [SOLVED] Ordering a list

Board footer