«

"paskali" <> wrote in message
news:...
> Hi, a simple question:
> i want to arrange some int numbers; i want to store them
> in an array and then print them on the screen.
>
> Look below:
>
> int numbers[10], arranged[10], i;
> puts("Insert 10 int numbers");
> for(i = 0; i <= 9; i ++, scanf("%d", &numbers[i]));
> ?
> for(i = 0; i <= 9; i ++, printf("/n%d", arranged[i]));
>
> I insert: 10 7 45 678 0 34 6 1 4 3
> I should see on the screen: 0 1 3 4 6 7 10 34 45 678
> Simple. Help me to replace question mark.

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.

Also in this code:

o For testing, I've hard-coded the test data (otherwise each you'll have to
type in all the numbers for each run, or arrange to import them from a file)

o I've put in code to show the numbers both before and after the sort, so
that you'll know exactly what the input is.

o The sorting is done in-place, so only one array is needed (you will need
two to preserve the original data).

#include <stdio.h>
#include <stdlib.h>

int main (void) {
#define N 10
int numbers[N]={10,7,45,678,0,34,6,1,4,3};
int i,swapped,temp;

printf("Numbers before sorting:\n");
for (i=0; i<N; ++i) {
printf("%d ",numbers[i]);
}
printf("\n\n");

/* Sort routine */
do {
swapped=0;
for (i=0; i<N-1; ++i) {
if (numbers[i]>numbers[i+1]) {
swapped=1;
temp=numbers[i];
numbers[i]=numbers[i+1];
numbers[i+1]=temp;
}
}
}
while (swapped);
/***************/

printf("Numbers after sorting:\n");
for (i=0; i<N; ++i) {
printf("%d ",numbers[i]);
}
printf("\n");

}

BartC <> wrote:

(snip, and previously snipped discussion on bubblesort)

> 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.

It was the first sort algorithm I knew about, as it was a sample
program in the IBM Fortran manual that I used to learn Fortran.
(Summer after 8th grade.) Only one I knew for some years.

-- glen

On Saturday, March 16, 2013 10:29:27 AM UTC, David Brown wrote:
> On 15/03/13 23:55, BartC wrote:
>
> Bubblesort has a lot of real-world uses.
>
Bubblesort is also very fast when data is almost sorted.
An example would be a football league. Only one game can be played by each
team each day, and teams only get three points for a win. So it's unlikely
that any team will move more than a place or two after each game. The list
is almost sorted, and bubblesort will only take a few passes.

On Mar 15, 10:55*pm, "BartC" <b...@freeuk.com> wrote:
> "paskali" <2970inva...@webuse.net> wrote in message
>
> news:...
>
> > Hi, a simple question:
> > i want to arrange some int numbers; i want to store them
> > in an array and then print them on the screen.
>
> > Look below:
>
> > * *int numbers[10], arranged[10], i;
> > * *puts("Insert 10 int numbers");
> > * *for(i = 0; i <= 9; i ++, scanf("%d", &numbers[i]));
> > * *?
> > * *for(i = 0; i <= 9; i ++, printf("/n%d", arranged[i]));
>
> > I insert: 10 7 45 678 0 34 6 1 4 3
> > I should see on the screen: 0 1 3 4 6 7 10 34 45 678
> > Simple. Help me to replace question mark.
>
> 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.

Boggo Sort
1. randomly permutate the array
2. if its ordered halt otherwise repeat step 1

Quantum Boggo Sort
1. randomly permutate the array
2. if it isn't ordered destroy the universe
3. if your universe reaches this step halt
(this sorts in O(n))

Worst Sort (used on letters)
1. set n <- 0 set letter <- 'A'
2. search for letter
3. if found insert letter at position n and increment n
4. move to next letter
5. repeat step 2

Assuming no repeated letters this sorts in only 26 passes or less.
I've seen this implemented in a real system...

> Also in this code:
>
> o For testing, I've hard-coded the test data (otherwise each you'll have to
> type in all the numbers for each run, or arrange to import them from a file)
>
> o I've put in code to show the numbers both before and after the sort, so
> that you'll know exactly what the input is.
>
> o The sorting is done in-place, so only one array is needed (you will need
> two to preserve the original data).
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int main (void) {
> #define N 10
> int numbers[N]={10,7,45,678,0,34,6,1,4,3};
> int i,swapped,temp;
>
> printf("Numbers before sorting:\n");
> for (i=0; i<N; ++i) {
> *printf("%d ",numbers[i]);}
>
> printf("\n\n");
>
> /* Sort routine */
> do {
> *swapped=0;
> *for (i=0; i<N-1; ++i) {
> * if (numbers[i]>numbers[i+1]) {
> * *swapped=1;
> * *temp=numbers[i];
> * *numbers[i]=numbers[i+1];
> * *numbers[i+1]=temp;
> * }
> *}}
>
> while (swapped);
> /***************/
>
> printf("Numbers after sorting:\n");
> for (i=0; i<N; ++i) {
> *printf("%d ",numbers[i]);}
>
> printf("\n");
> }

On Mar 16, 10:29*am, David Brown <da...@westcontrol.removethisbit.com>
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

Nick Keighley <> wrote:

(snip)

> Worst Sort (used on letters)
> 1. set n <- 0 set letter <- 'A'
> 2. search for letter
> 3. if found insert letter at position n and increment n
> 4. move to next letter
> 5. repeat step 2

> Assuming no repeated letters this sorts in only 26 passes or less.
> I've seen this implemented in a real system...

Radix sort with Radix 1.

There is some discussion about Radix sort, and whether it is
really O(N). It is for fixed word size, but O() is supposed to
be for limit as N goes to infinity. Modify yours slightly:

Count 'A's, count 'B's, etc.

Write to the output file the appropriate number of 'A's, then
the 'B's, etc.

-- glen

On 3/16/2013 10:40 AM, David Brown wrote:
> [...]
> 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").

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.

--
Eric Sosman
d

On Mar 16, 3:16*pm, Eric Sosman <esos...@comcast-dot-net.invalid>
wrote:
> On 3/16/2013 10:40 AM, David Brown wrote:
>
> > [...]
> > 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").
>
> * * *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.

yeah. who's he anyway?

On 3/16/2013 2:39 PM, Robert Wessel wrote:
> On Sat, 16 Mar 2013 15:40:23 +0100, David Brown
> <> wrote:
>
>> On 16/03/13 14:10, Nick Keighley wrote:
>>> On Mar 16, 10:29 am, David Brown <da...@westcontrol.removethisbit.com>
>>> 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
d

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
>
> > <> wrote:
>
> >
>
> >> On 16/03/13 14:10, Nick Keighley wrote:
>
> >>> On Mar 16, 10:29 am, David Brown <da...@westcontrol.removethisbit.com>
>
> >>> 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
>
> d
I think the bubble sort is fast in sorting under 100 items.
The quadratic behavior will dominate when the length of the list
is large.