Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: How to arrange some numbers

Reply
Thread Tools

Re: How to arrange some numbers

 
 
Tim Rentsch
Guest
Posts: n/a
 
      03-19-2013
Robert Wessel <(E-Mail Removed)> writes:

> On Sun, 17 Mar 2013 11:43:14 -0700, Tim Rentsch
> <(E-Mail Removed)> wrote:
>
>>pete <(E-Mail Removed)> writes:
>>
>>> [snip]
>>>
>>> There are certain data distributions
>>> for which the running time of insertion sort
>>> varies directly with N,
>>> where N is the number of elements in the array,
>>> the running time of binary insertion sort
>>> can never do better than to vary directly with N*log(N).

>>
>>I don't disagree exactly, but it's worth pointing
>>out that a kind of "binary search" can be written
>>which is O( log N ) in the worst case but will be
>>faster if the item being searched for is always
>>close to one end.

>
> You're thinking of an interpolation search. With a good
> distribution of keys, the search time is O(log log N).
>
> http://en.wikipedia.org/wiki/Interpolation_search


No, my comment was more general, intended for any
comparison-based sort routine. Interpolation sort
depends on the key space having some form of distance
metric that quantifies "how near" or "how far" two
keys are. That property is not present in general
sorting functions, eg, qsort(). The technique I
was alluding to depends only on comparison, not on
having a distance metric.
 
Reply With Quote
 
 
 
 
Tiib
Guest
Posts: n/a
 
      03-19-2013
On Wednesday, 20 March 2013 00:38:53 UTC+2, Tim Rentsch wrote:
> Robert Wessel <(E-Mail Removed)> writes:
> > but if you
> > actually wanted to sort the sequence for comparison, again
> > insertion sort is a better choice than bubble sort.

>
> Not if the routine you are unit testing uses insertion
> sort to do its sorting.


You guys are joking, yes? I thought that most would use well tested
implementation (like qsort()) to produce a sequence with what to
compare in test.
 
Reply With Quote
 
 
 
 
Edward A. Falk
Guest
Posts: n/a
 
      03-19-2013
In article <(E-Mail Removed)>,
Robert Wessel <(E-Mail Removed)> wrote:
>
>
>Again, this has become rather more complex than a Shell sort.


Went back and re-read my notes. I have to agree. Cute
little algorithm; I'll have to use it someday.
--
-Ed Falk, http://www.velocityreviews.com/forums/(E-Mail Removed)
http://thespamdiaries.blogspot.com/
 
Reply With Quote
 
blmblm@myrealbox.com
Guest
Posts: n/a
 
      03-20-2013
In article <(E-Mail Removed)>,
Rosario1903 <(E-Mail Removed)> wrote:
> On Sun, 17 Mar 2013 07:22:38 -0500, pete <(E-Mail Removed)>
> wrote:
>
>
> >I don't really know anything about parallel systems.

>
> qsort is parallelizable...
> divide the interval
> assign the 2 interval to 2 different cpu for doing ordering
> i think could be O(N) in one multi cpu sys
>


I'm skeptical (about O(N)), but maybe you can explain why you
say that -- unless you assume an unlimited number of processing
elements? (I'm using "processing elements" here as a generic term
for processors or cores or -- whatever.)

The thing about this way of parallelizing quicksort, though, is
that you don't get the maximum benefit until you've done enough
splits to generate a thread for each processing element, and the
more of those you have the smaller the fraction of the computation
that uses all of them. Also it becomes even more important to pick
pivots in such a way that the two intervals are roughly the same
size, since otherwise you don't get good load balance.

--
B. L. Massingill
ObDisclaimer: I don't speak for my employers; they return the favor.
 
Reply With Quote
 
blmblm@myrealbox.com
Guest
Posts: n/a
 
      03-20-2013
In article <(E-Mail Removed)>,
Robert Wessel <(E-Mail Removed)> wrote:
> On 20 Mar 2013 05:53:07 GMT, (E-Mail Removed)
> <(E-Mail Removed)> wrote:
>
> >In article <(E-Mail Removed)>,
> >Rosario1903 <(E-Mail Removed)> wrote:
> >> On Sun, 17 Mar 2013 07:22:38 -0500, pete <(E-Mail Removed)>
> >> wrote:
> >>
> >>
> >> >I don't really know anything about parallel systems.
> >>
> >> qsort is parallelizable...
> >> divide the interval
> >> assign the 2 interval to 2 different cpu for doing ordering
> >> i think could be O(N) in one multi cpu sys
> >>

> >
> >I'm skeptical (about O(N)), but maybe you can explain why you
> >say that -- unless you assume an unlimited number of processing
> >elements? (I'm using "processing elements" here as a generic term
> >for processors or cores or -- whatever.)

>
>
> With N processing elements, you can do the first partition in N time
> on one processor, the second partitioning (the two partitions from
> pass 1) in N/2 time on two processors, the third in N/4 time on four
> processors, or in about 2N, aka O(N) time. But you've wasted most of
> the 2(N**2) possible processor time available on those N processors.


Oh! Obvious when someone else thinks it through and explains it. ?
(Thanks.)

> >The thing about this way of parallelizing quicksort, though, is
> >that you don't get the maximum benefit until you've done enough
> >splits to generate a thread for each processing element, and the
> >more of those you have the smaller the fraction of the computation
> >that uses all of them. Also it becomes even more important to pick
> >pivots in such a way that the two intervals are roughly the same
> >size, since otherwise you don't get good load balance.

>
>
> Correct. There are better algorithms for parallel sorting.
>


--
B. L. Massingill
ObDisclaimer: I don't speak for my employers; they return the favor.
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      03-20-2013
On 3/20/2013 2:44 AM, Robert Wessel wrote:
> On Tue, 19 Mar 2013 15:38:53 -0700, Tim Rentsch
>[...]
>> Your comment is made with the benefit of already understanding
>> how both work, and made by someone who knows a lot about
>> programming. Try explaining each idea to a six-year old.
>> I would claim that more will get the idea behind bubble sort
>> than insertion sort (or get it faster, or more easily, etc).

>
> I think there is certainly some room for disagreement here. An
> insertion sort is a common method used to sort a hand of playing
> cards.


The very first sorting method I learned was selection:
Find the largest element and move it to the end of the array,
find the largest of the first N-1 and move it to the next-to-
last spot, and so on. I still think it's about the simplest
method I've ever seen: Both simple to implement and simple to
understand.

(Not very fast, though: It always makes N*(N-1)/2 comparisons
and N-1 swaps, even if the array is already sorted. I "invented"
what I later learned was bubble sort in an attempt to exploit
existing order if there was any, but at that age my mathematical
prowess was insufficient to analyze the algorithm.)

--
Eric Sosman
(E-Mail Removed)d
 
Reply With Quote
 
88888 Dihedral
Guest
Posts: n/a
 
      03-20-2013
Eric Sosman於 2013年3月20日星期三UTC+8下午8時00分01秒 寫道:
> On 3/20/2013 2:44 AM, Robert Wessel wrote:
>
> > On Tue, 19 Mar 2013 15:38:53 -0700, Tim Rentsch

>
> >[...]

>
> >> Your comment is made with the benefit of already understanding

>
> >> how both work, and made by someone who knows a lot about

>
> >> programming. Try explaining each idea to a six-year old.

>
> >> I would claim that more will get the idea behind bubble sort

>
> >> than insertion sort (or get it faster, or more easily, etc).

>
> >

>
> > I think there is certainly some room for disagreement here. An

>
> > insertion sort is a common method used to sort a hand of playing

>
> > cards.

>
>
>
> The very first sorting method I learned was selection:
>
> Find the largest element and move it to the end of the array,
>
> find the largest of the first N-1 and move it to the next-to-
>
> last spot, and so on. I still think it's about the simplest
>
> method I've ever seen: Both simple to implement and simple to
>
> understand.
>
>
>
> (Not very fast, though: It always makes N*(N-1)/2 comparisons
>
> and N-1 swaps, even if the array is already sorted. I "invented"
>
> what I later learned was bubble sort in an attempt to exploit
>
> existing order if there was any, but at that age my mathematical
>
> prowess was insufficient to analyze the algorithm.)
>
>
>
> --
>
> Eric Sosman
>
> (E-Mail Removed)d


I always prefer the radix sort after 20XX.

Just work out an order preserving key for the list
of items in 32, 64, 128 bits first.

I use 12 to 16 bit per digits in these days.

Of course, if the total number of items with the same key
is less than 25% of all items.

I can bound the O(n*p) of p which is the total number
of scanning the n items in the sorting process.

If the ram access is too slow, then this approach might
not save much time in applications.





 
Reply With Quote
 
osmium
Guest
Posts: n/a
 
      03-20-2013
88888 Dihedral wrote:

> Eric Sosman? 2013?3?20????UTC+8??8?00?01???:
>> On 3/20/2013 2:44 AM, Robert Wessel wrote:
>>
>>> On Tue, 19 Mar 2013 15:38:53 -0700, Tim Rentsch

>>
>>> [...]

>>
>>>> Your comment is made with the benefit of already understanding

>>
>>>> how both work, and made by someone who knows a lot about

>>
>>>> programming. Try explaining each idea to a six-year old.

>>
>>>> I would claim that more will get the idea behind bubble sort

>>
>>>> than insertion sort (or get it faster, or more easily, etc).

>>
>>>

>>
>>> I think there is certainly some room for disagreement here. An

>>
>>> insertion sort is a common method used to sort a hand of playing

>>
>>> cards.

>>
>>
>>
>> The very first sorting method I learned was selection:
>>
>> Find the largest element and move it to the end of the array,
>>
>> find the largest of the first N-1 and move it to the next-to-
>>
>> last spot, and so on. I still think it's about the simplest
>>
>> method I've ever seen: Both simple to implement and simple to
>>
>> understand.
>>
>>
>>
>> (Not very fast, though: It always makes N*(N-1)/2 comparisons
>>
>> and N-1 swaps, even if the array is already sorted. I "invented"
>>
>> what I later learned was bubble sort in an attempt to exploit
>>
>> existing order if there was any, but at that age my mathematical
>>
>> prowess was insufficient to analyze the algorithm.)
>>
>>
>>
>> --
>>
>> Eric Sosman
>>
>> (E-Mail Removed)d

>
> I always prefer the radix sort after 20XX.
>
> Just work out an order preserving key for the list
> of items in 32, 64, 128 bits first.
>
> I use 12 to 16 bit per digits in these days.
>
> Of course, if the total number of items with the same key
> is less than 25% of all items.
>
> I can bound the O(n*p) of p which is the total number
> of scanning the n items in the sorting process.
>
> If the ram access is too slow, then this approach might
> not save much time in applications.


Well, sure, now that you put it that way.


 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      03-21-2013
Tiib writes:

> On Wednesday, 20 March 2013 00:38:53 UTC+2, Tim Rentsch wrote:
>> Robert Wessel <(E-Mail Removed)> writes:
>> > but if you
>> > actually wanted to sort the sequence for comparison, again
>> > insertion sort is a better choice than bubble sort.

>>
>> Not if the routine you are unit testing uses insertion
>> sort to do its sorting.

>
> You guys are joking, yes? I thought that most would use well tested
> implementation (like qsort()) to produce a sequence with what to
> compare in test.


Sure, if one is available. But that may not be the case. Since
what we need to unit test is a sort routine, it may very well be
an implementation of qsort that we're testing.
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      03-21-2013
Robert Wessel <(E-Mail Removed)> writes:

> On Tue, 19 Mar 2013 15:38:53 -0700, Tim Rentsch
> <(E-Mail Removed)> wrote:
>
>>Robert Wessel <(E-Mail Removed)> writes:
>>
>>> On Sun, 17 Mar 2013 11:33:11 -0700, Tim Rentsch
>>> <(E-Mail Removed)> wrote:
>>>
>>>>Robert Wessel <(E-Mail Removed)> writes:
>>>>
>>>>> [snip] Bubble sort basically has nothing to recommend it.
>>>>
>>>>Sure it does. It's easier to explain than any other
>>>>sorting method, especially if the expected audience
>>>>is comparatively inexperienced in their programming
>>>>skills, which usually makes it easier for inexperienced
>>>>programmers to write correctly. If one were writing a
>>>>unit test to check a sorting routine, bubble sort is a
>>>>pretty candidate for doing that, for just those reasons.
>>>
>>> I would disagree. Insertion sort would seem to be easier to
>>> understand than a bubble sort, if for no other reason that the
>>> action it cycles through is much simpler.

>>
>>Your comment is made with the benefit of already understanding
>>how both work, and made by someone who knows a lot about
>>programming. Try explaining each idea to a six-year old.
>>I would claim that more will get the idea behind bubble sort
>>than insertion sort (or get it faster, or more easily, etc).

>
> I think there is certainly some room for disagreement here. An
> insertion sort is a common method used to sort a hand of playing
> cards.


IME it's more common for card players to use selection
sort to sort their hands. But in either case the transfer
to the programming domain isn't obvious to some people,
as programmatic sorting is done in arrays, whereas a hand
of cards is more like a linked list. Besides, I was talking
about explaining to an audience that hadn't already gone up
the associated skill curves (eg, six-year olds). Clearly
someone who has learned to readily sort a hand of cards has
already acquired some level of skill in sorting methods.

We might make an analogy with addition. I think most people
learned, at an early age, how to count on their fingers, and
used that method to do addition. Later on, we learn a different
method to do addition. After learning the more sophisticated
method the counting-on-fingers method is pretty much abandoned.
But it still was a useful step in the learning process.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Re: How to arrange some numbers Keith Thompson C Programming 4 03-16-2013 12:20 PM
Re: How to arrange some numbers Eric Sosman C Programming 2 03-15-2013 08:35 PM
Re: How to arrange some numbers Mark Bluemel C Programming 0 03-15-2013 04:14 PM
Re: How to arrange some numbers Mark Bluemel C Programming 0 03-15-2013 04:10 PM



Advertisments