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

 
 
88888 Dihedral
Guest
Posts: n/a
 
      03-17-2013
(E-Mail Removed)於 2013年3月17日星期日UTC+8下午2時38分35秒 寫道:
> On Sat, 16 Mar 2013 15:09:42 -0700 (PDT), Öö Tiib <(E-Mail Removed)>
>
> wrote:
>
>
>
> >On Saturday, 16 March 2013 16:40:23 UTC+2, David Brown wrote:

>
> >> Insert sort is not "as simple /and/ better" than bubblesort.

>
> >

>
> >Nonsense, insertion sort *is* bubble sort with pointless sequential

>
> >swaps replaced with insert that is both cheaper and shorter.

>
>
>
>
>
> No it's not. Bubble sort repeatedly sweeps the array allowing all out
>
> of place items to move one step closer to their final destination.
>
>
>
> Insertion sort works by repeatedly updating a sorted list by placing
>
> one new element into the correct location in that list.


I remember there was an article in the Byte magazine in 199X
which published an improved bubble sort with the gap between compared
elements to be decreasing in passes and initially the gap is set to n-k
where k in the range 1 to 20 and n is the number of total elements.

If the gap is set to 1, then one obtains the degenerated bubble sort.

Anyway for a list of elements which is almost in order,
the insertion sort is very good.



 
Reply With Quote
 
 
 
 
Nick Keighley
Guest
Posts: n/a
 
      03-17-2013
On Mar 16, 9:47*pm, pete <(E-Mail Removed)> wrote:
> Eric Sosman wrote:
>
> > On 3/16/2013 10:40 AM, David Brown wrote:
> > > [...]
> > > Insert sort is not "as simple /and/ better" than bubblesort. *To doan
> > > efficient insertion sort (and it has to be efficient, or it is not
> > > "better"), you need to use a binary search to find the insertion point
> > > for each element, and you need to hold your elements in a linked list
> > > rather than a static array (otherwise you need to move half your data
> > > for every insertion, which is not "better").

>
> > * * *I guess the guy who wrote

>
> > * * * * "It took a good deal of work to analyze the bubble sort;
> > * * * * and although the techniques used in the calculations are
> > * * * * instructive, the results are disappointing since they tell
> > * * * * us that the bubble sort isn't really very good at all.
> > * * * * Compared to straight insertion (Algorithm 5.2.1S), bubble
> > * * * * sorting requires a more complicated program and takes more
> > * * * * than twice as long!"
> > * * * * -- D.E. Knuth, "The Art of Computer Programming"

>
> > ... didn't know what he was talking about.

>
> As long as you realise that you were wrong,
> that's what's important.
>
> Insertion sort is not "as simple /and/ better" than bubble sort.
>
> Insertion sort is *"both simpler *and* better" than bubble sort!
>
> --
> pete


I thought of saying that but wasn't certain. And I was thinking of
Knuth's quote.
 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      03-17-2013
On 3/17/2013 2:45 AM, Robert Wessel wrote:
> On Sat, 16 Mar 2013 23:35:12 +0000 (UTC), glen herrmannsfeldt
> <(E-Mail Removed)> wrote:
>> Consider a highly parallel system with N (very simple)
>> processors that can, on each clock cycle compare two
>> elements, store one, and move one. I believe that you
>> will find that the compare and swap pattern of bubblesort
>> lends itself to highly parallel sorting better than
>> insertion sort.

>
>
> But that needs O(N) hardware and O(N) time. There are much better
> parallel sorting algorithms, that can provide various combinations of
> less time and/or hardware. Several of the methods originally
> described by Batchner, for example.


ITYM Kenneth Edward Batcher (no N).

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d
 
Reply With Quote
 
Tiib
Guest
Posts: n/a
 
      03-17-2013
On Sunday, 17 March 2013 08:38:35 UTC+2, (E-Mail Removed) wrote:
> On Sat, 16 Mar 2013 15:09:42 -0700 (PDT), Tiib <(E-Mail Removed)>
> wrote:
> >On Saturday, 16 March 2013 16:40:23 UTC+2, David Brown wrote:
> >> Insert sort is not "as simple /and/ better" than bubblesort.

> >
> >Nonsense, insertion sort *is* bubble sort with pointless sequential
> >swaps replaced with insert that is both cheaper and shorter.

>
> No it's not. Bubble sort repeatedly sweeps the array allowing all out
> of place items to move one step closer to their final destination.


So ... after such a sweep one out of place item has to arrive at its final
destination. It would be cheaper to just move it there instead of swapping
all the elements OTW I trust.

> Insertion sort works by repeatedly updating a sorted list by placing
> one new element into the correct location in that list.


OK, so I apparently thought of different algorithm, my bad. Reason
is that I do not use the inferior sorting algorithms much when there are
heap sort, quick sort and merge sort available and mix the worse ones
up all the time.

 
Reply With Quote
 
88888 Dihedral
Guest
Posts: n/a
 
      03-17-2013
(E-Mail Removed)於 2013年3月17日星期日UTC+8下午4時42分18秒 寫道:
> On Sun, 17 Mar 2013 00:57:05 -0700 (PDT), 88888 Dihedral
>
> <(E-Mail Removed)> wrote:
>
>
>
> >(E-Mail Removed)? 2013?3?17????UTC+8??2?38?35????

>
> >> On Sat, 16 Mar 2013 15:09:42 -0700 (PDT), Öö Tiib <(E-Mail Removed)>

>
> >>

>
> >> wrote:

>
> >>

>
> >>

>
> >>

>
> >> >On Saturday, 16 March 2013 16:40:23 UTC+2, David Brown wrote:

>
> >>

>
> >> >> Insert sort is not "as simple /and/ better" than bubblesort.

>
> >>

>
> >> >

>
> >>

>
> >> >Nonsense, insertion sort *is* bubble sort with pointless sequential

>
> >>

>
> >> >swaps replaced with insert that is both cheaper and shorter.

>
> >>

>
> >>

>
> >>

>
> >>

>
> >>

>
> >> No it's not. Bubble sort repeatedly sweeps the array allowing all out

>
> >>

>
> >> of place items to move one step closer to their final destination.

>
> >>

>
> >>

>
> >>

>
> >> Insertion sort works by repeatedly updating a sorted list by placing

>
> >>

>
> >> one new element into the correct location in that list.

>
> >

>
> >I remember there was an article in the Byte magazine in 199X

>
> >which published an improved bubble sort with the gap between compared

>
> >elements to be decreasing in passes and initially the gap is set to n-k

>
> >where k in the range 1 to 20 and n is the number of total elements.

>
> >

>
> >If the gap is set to 1, then one obtains the degenerated bubble sort.

>
>
>
>
>
> Why not just use a Shell sort?
>
>
>

// code example
// input a[i], i=0..n-1>, n>0
int i,j,gap; //local variables
gap=n-20; // other values instead of 20 in different HWs in tests

while(gap>20) // if gap==1 will work like the bubble sort
{
for(i=0, j=i+gap;j<n;i++,j++)
if (a[j]>a[i]) {swap(a[j], a[i])};

gap-=gap>>2; //.75 decreasing
};

// use the insertion sort here

//....



>
>
> >Anyway for a list of elements which is almost in order,

>
> >the insertion sort is very good.

>
>
>
>
>
> Whereas for some almost sorted lists, bubble sort is very bad.
>
> Consider just having the first and last elements swapped.


 
Reply With Quote
 
glen herrmannsfeldt
Guest
Posts: n/a
 
      03-17-2013
88888 Dihedral <(E-Mail Removed)> wrote:

(snip on bubblesort)

>> Insertion sort works by repeatedly updating a sorted list by placing
>> one new element into the correct location in that list.


> I remember there was an article in the Byte magazine in 199X
> which published an improved bubble sort with the gap between compared
> elements to be decreasing in passes and initially the gap is set to n-k
> where k in the range 1 to 20 and n is the number of total elements.


Shellsort is a diminishing increment sort usually implemented
as insertion sort, but could be done with bubblesort. The optimal
gqp sequence is an open question, but some are known to be not so
far from optimal. Wikipedia has a good explanation of it.

> If the gap is set to 1, then one obtains the degenerated bubble sort.


> Anyway for a list of elements which is almost in order,
> the insertion sort is very good.


-- glen
 
Reply With Quote
 
Stephen Sprunk
Guest
Posts: n/a
 
      03-17-2013
On 17-Mar-13 03:42, Robert Wessel wrote:
> On Sun, 17 Mar 2013 00:57:05 -0700 (PDT), 88888 Dihedral
> <(E-Mail Removed)> wrote:
>> I remember there was an article in the Byte magazine in 199X which
>> published an improved bubble sort with the gap between compared
>> elements to be decreasing in passes and initially the gap is set
>> to n-k where k in the range 1 to 20 and n is the number of total
>> elements.
>>
>> If the gap is set to 1, then one obtains the degenerated bubble
>> sort.

>
> Why not just use a Shell sort?


Because it's fairly complicated for a newbie?

Insertion (or selection) sort should be easy for anyone who has learned
iteration. Likewise, merge sort should be easy to understand for anyone
who has learned recursion. There's little reason to teach anything less
efficient.

>> Anyway for a list of elements which is almost in order, the
>> insertion sort is very good.

>
> Whereas for some almost sorted lists, bubble sort is very bad.
> Consider just having the first and last elements swapped.


The cocktail sort and gnome sort variations handle such cases in only
two passes (plus the obligatory extra pass to verify, common to the
entire bubble sort family).

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      03-17-2013
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.

 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      03-17-2013
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. So one could write an insertion
sort with a worst case behavior of O( N * log N )
compares, but uses only O( N ) compares in "good"
cases.
 
Reply With Quote
 
88888 Dihedral
Guest
Posts: n/a
 
      03-17-2013
Eric Sosman於 2013年3月17日星期日UTC+8上午3時41分20秒 寫道:
> On 3/16/2013 2:39 PM, Robert Wessel wrote:
>
> > On Sat, 16 Mar 2013 15:40:23 +0100, David Brown

>
> > <(E-Mail Removed)> wrote:

>
> >

>
> >> On 16/03/13 14:10, Nick Keighley wrote:

>
> >>> On Mar 16, 10:29 am, David Brown <(E-Mail Removed)>

>
> >>> wrote:

>
> >>>> On 15/03/13 23:55, BartC wrote:

>
> >>>>

>
> >>>>> I've provided some code below. Note that this uses the world's worst sort

>
> >>>>> method, so won't get you many marks. But it's also my favourite sort.

>
> >>>>

>
> >>>> Bubblesort has a lot of real-world uses. It has a worse complexity

>
> >>>> scaling than the "big" sorting algorthims (mergesort, heapsort,

>
> >>>> quicksort, etc.), but run speed is not always the most important issue.

>
> >>>> /Correctness/ is far more important - and it is much easier to write a

>
> >>>> correct bubblesort than a correct heapsort. For small samples,

>
> >>>> especially on more limited systems (such as embedded systems),

>
> >>>> bubblesort will often be significantly faster than using a generic

>
> >>>> library "qsort" function - and very much smaller in code space.

>
> >>>>

>
> >>>> Anyway, I thought the world's worst sort method was this:

>
> >>>>

>
> >>>> <http://en.wikipedia.org/wiki/Bogosort>

>
> >>>

>
> >>> but insert sort is as simple *and* better

>
> >>>

>
> >>

>
> >> Insert sort is not "as simple /and/ better" than bubblesort. To do an

>
> >> efficient insertion sort (and it has to be efficient, or it is not

>
> >> "better"), you need to use a binary search to find the insertion point

>
> >> for each element, and you need to hold your elements in a linked list

>
> >> rather than a static array (otherwise you need to move half your data

>
> >> for every insertion, which is not "better").

>
> >>

>
> >> Of course, this is for a general sort - for some kinds of applications,

>
> >> insertion sort is very well suited.

>
> >>

>
> >> Unless you meant that insert sort is as simple and better than bogosort...

>
> >

>
> >

>
> > No, ordinary insertion sort requires neither of those, and can sort an

>
> > array with no additional storage, just like bubble sort. The basic

>
> > idea is that you take each element and then move it back one spot at a

>
> > time in the array (by swapping with the prior element) until it's in

>
> > the correct spot. It's still O(n**2), but usually runs about twice as

>
> > fast as bubble sort, and the code is usually shorter too.

>
> >

>
> > for(i=1; i<N; i++)

>
> > for(j=i; j>0; j--)

>
> > {

>
> > if (a[j-1] > a[j])

>
> > swap(a[j-1], a[j]);

>
> > else

>
> > break;

>
> > }

>
>
>
> A simple change will speed this up significantly on most
>
> machines. The problem is with the swap() operation: It will
>
> exchange (for example) items [10] and [9], then [9] and [8],
>
> then [8] and [7] -- six memory writes to slide the original
>
> [10] element three places to the left. By holding the "moving"
>
> element in a temporary throughout, you can avoid almost half
>
> the writes:
>
>
>
> for (i = 1; i < N; ++i) {
>
> int temp = a[i];
>
> for (j = i; --j >= 0; ) {
>
> if (a[j] > temp)
>
> a[j+1] = a[j];
>
> else
>
> break;
>
> }
>
> a[j+1] = temp;
>
> }
>
>
>
> For the same rearrangement, this code loads temp from [10],
>
> then copies [9] to [10], [8] to [9], [7] to [8] and finally
>
> stores temp in [7] -- four writes instead of six. (Assuming
>
> that temp winds up in a register; if it doesn't, there'll
>
> be five writes instead of nine because swap() will need an
>
> additional internal write, too.)
>
>
>
> --
>
> Eric Sosman
>
> (E-Mail Removed)d

This is the classical insertion sort of inserting the last one
into the sorted list before the current inserting element.

Of course, it is possible to insert 2 elements at a time
to speed up slightly for reducing the loop overheads.

 
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