By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,561 Members | 3,010 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,561 IT Pros & Developers. It's quick & easy.

VERY URGENT C PROGRAM

P: n/a
Hey Frnds can anyone help me in this

i need a program in 'c'

PROGRAM to print NxN Matrix
9 1 8 1 2 3
2 7 3 as 4 5 6
6 4 5 7 8 9

in sorted form

please send me as soon as u can very very very urgent....
plz send me
Thanks in Advance...

Apr 9 '06 #1
Share this Question
Share on Google+
33 Replies


P: n/a
On 9 Apr 2006 03:49:20 -0700, "dembla" <an**********@gmail.com> wrote:
Hey Frnds can anyone help me in this

i need a program in 'c'

PROGRAM to print NxN Matrix
9 1 8 1 2 3
2 7 3 as 4 5 6
6 4 5 7 8 9

in sorted form

please send me as soon as u can very very very urgent....
plz send me
Thanks in Advance...


#include <stdio.h>

int main()
{
printf("1 2 3\n4 5 6\n7 8 9\n");

return 0;
}
Apr 9 '06 #2

P: n/a
"dembla" writes:
i need a program in 'c'

PROGRAM to print NxN Matrix
9 1 8 1 2 3
2 7 3 as 4 5 6
6 4 5 7 8 9

in sorted form


The fact that the data appears to be a matrix is ignored when it is sorted,
isn't it? The rule seems to be "ignore the origin, sort the data, and print
it as thought it were in an NxN matrix". Note that it is not unheard of for
C functions to lie when calling other functions, that may be helpful, it may
not. Look up bubble sort. If you are stressed it might be best to sort a
single array first, to build up your confidence. The throw that code away
and do the actual assignment.
Apr 9 '06 #3

P: n/a
W Marsh wrote:
"dembla" <an**********@gmail.com> wrote:
i need a program in 'c'

PROGRAM to print NxN Matrix
9 1 8 1 2 3
2 7 3 as 4 5 6
6 4 5 7 8 9

in sorted form

please send me as soon as u can very very very urgent....
plz send me


#include <stdio.h>

int main()
{
printf("1 2 3\n4 5 6\n7 8 9\n");

return 0;
}


Better is:

#include <stdio.h>
int main(void) {
puts("1 2 3\n4 5 6\n7 8 9");
return 0;
}

:-)

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

Apr 9 '06 #4

P: n/a
"dembla" <an**********@gmail.com> writes:
Hey Frnds can anyone help me in this

i need a program in 'c'

PROGRAM to print NxN Matrix
9 1 8 1 2 3
2 7 3 as 4 5 6
6 4 5 7 8 9

in sorted form

please send me as soon as u can very very very urgent....
plz send me


Sorting an NxN matrix as if it were a one-dimensional array is "very
very very urgent"?

Perhaps it wouldn't be so urgent if you had done your own homework, or
at least started it sooner.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Apr 9 '06 #5

P: n/a
dembla wrote:
PROGRAM to print NxN Matrix
9 1 8 1 2 3
2 7 3 as 4 5 6
6 4 5 7 8 9

in sorted form


the simplest way is:
put the values of the first matrix into an array,
sort it with a sorting algorithm (like bubble sort or quick sort or
whatever)
put the values of the vector into the result matrix.

Apr 9 '06 #6

P: n/a
major wrote:
dembla wrote:
PROGRAM to print NxN Matrix
9 1 8 1 2 3
2 7 3 as 4 5 6
6 4 5 7 8 9

in sorted form


the simplest way is:
put the values of the first matrix into an array,
sort it with a sorting algorithm (like bubble sort or quick sort or
whatever)
put the values of the vector into the result matrix.


No way, I think the simplest way is to beg for someone on c.l.c to do
it. Seriously, the OP really needs to do his/her own homework. That is
what homework is for - it is assigned to help you learn what it is you
are attempting to learn and by not doing it yourself you're doomed for
failure unless you are going to stake your whole career on members of
c.l.c solving your tasks at work all the time. On any given day I work
with a kid fresh out of college with an Associate degree in CS that
doesn't know the difference between static and dynamic allocation - in c
that is very bad.

Bubble sort or quick sort is a good idea, however for only 9 members it
might be a little overkill code wise. I would recommend sorting while
storing each element. This would be the simplest method in at least this
example.

Joe
Apr 9 '06 #7

P: n/a
On Sun, 09 Apr 2006 23:39:17 GMT, Joe Estock
<je*****@NOSPANnutextonline.com> wrote:
major wrote:
dembla wrote:
PROGRAM to print NxN Matrix
9 1 8 1 2 3
2 7 3 as 4 5 6
6 4 5 7 8 9

in sorted form


the simplest way is:
put the values of the first matrix into an array,
sort it with a sorting algorithm (like bubble sort or quick sort or
whatever)
put the values of the vector into the result matrix.

Bubble sort or quick sort is a good idea, however for only 9 members it
might be a little overkill code wise. I would recommend sorting while
storing each element. This would be the simplest method in at least this
example.


Others have pointed out that there is a direct row-by-row translation.
However, if the values in each row change, the input range appears to
be limited to 1-9, which reduces a storage sort to a direct array
element assignment with index derived from input value.

--
Dan Henry
Apr 10 '06 #8

P: n/a
Joe Estock wrote:
major wrote:
dembla wrote:
PROGRAM to print NxN Matrix
9 1 8 1 2 3
2 7 3 as 4 5 6
6 4 5 7 8 9

in sorted form
the simplest way is:
put the values of the first matrix into an array,
sort it with a sorting algorithm (like bubble sort or quick sort or
whatever)
put the values of the vector into the result matrix.


[snip]
Bubble sort or quick sort is a good idea,


Bubble sort is never a good idea.

Robert Gamble

Apr 10 '06 #9

P: n/a
On 2006-04-10, Dan Henry <us****@danlhenry.com> wrote:
Others have pointed out that there is a direct row-by-row translation.
the input range appears to
be limited to 1-9, which reduces a storage sort to a direct array
element assignment with index derived from input value.


If that's the case then there is no sorting to do :) Just "write
direct" the result.

But in the absence of a proper input data spec, one can only guess.
Apr 10 '06 #10

P: n/a
Hai friend,
This is matrix multiplication programs.
click following link

http://www.hitechskill.com/source/di...pe=for&page=42

or
site home page
www.hitechskill.com

with regards
s.chandrasekaran

Apr 10 '06 #11

P: n/a
Robert Gamble wrote:
Joe Estock wrote:
major wrote:
dembla wrote:

PROGRAM to print NxN Matrix
9 1 8 1 2 3
2 7 3 as 4 5 6
6 4 5 7 8 9

in sorted form
the simplest way is:
put the values of the first matrix into an array,
sort it with a sorting algorithm (like bubble sort or quick sort or
whatever)
put the values of the vector into the result matrix.


[snip]
Bubble sort or quick sort is a good idea,


Bubble sort is never a good idea.

It's a bit curious that people continue to teach bubble sort as a basic
algorithm when insertion sort is hardly more complicated and better in
practice (for the small input sets bubble sort might proficiently be applied
to).

S.
Apr 10 '06 #12

P: n/a
Skarmander wrote:

Robert Gamble wrote:
Joe Estock wrote:
major wrote:
dembla wrote:

> PROGRAM to print NxN Matrix
> 9 1 8 1 2 3
> 2 7 3 as 4 5 6
> 6 4 5 7 8 9
>
> in sorted form
the simplest way is:
put the values of the first matrix into an array,
sort it with a sorting algorithm (like bubble sort or quick sort or
whatever)
put the values of the vector into the result matrix.


[snip]
Bubble sort or quick sort is a good idea,


Bubble sort is never a good idea.

It's a bit curious that people continue to teach bubble sort as a basic
algorithm when insertion sort is hardly more complicated and better in
practice (for the small input sets bubble sort might proficiently be applied
to).


Use "The Howie Sort", which was "invented" by my friend Howie when he was
taking a JCL course many years ago.

1 - Toss the deck of cards[1] in the air.
2 - Pick them up.
3 - If they're not sorted, go back to step 1.
4 - Exit.

While it can be inefficient, it does have the ability to be the most
efficient sort around, being able to sort N items in N+1 steps in the
best-case scenario.

:-)

[1] I told you it was a long time ago.

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:Th*************@gmail.com>

Apr 10 '06 #13

P: n/a
Kenneth Brody <ke******@spamcop.net> writes:
Skarmander wrote:

[...]
It's a bit curious that people continue to teach bubble sort as a basic
algorithm when insertion sort is hardly more complicated and better in
practice (for the small input sets bubble sort might proficiently be applied
to).


Use "The Howie Sort", which was "invented" by my friend Howie when he was
taking a JCL course many years ago.

1 - Toss the deck of cards[1] in the air.
2 - Pick them up.
3 - If they're not sorted, go back to step 1.
4 - Exit.

While it can be inefficient, it does have the ability to be the most
efficient sort around, being able to sort N items in N+1 steps in the
best-case scenario.

:-)

[1] I told you it was a long time ago.


Strictly speaking, that's not an algorithm, since it's not guaranteed
to terminate.

Pemutation Sort is guaranteed to terminate eventually. It
systematically generates all possible permutations of the input list,
checking each one for sortedness. (Optimized Permutation Sort allows
you to stop generating permutations when you find one that's sorted.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Apr 10 '06 #14

P: n/a
REH

Kenneth Brody wrote:
Use "The Howie Sort", which was "invented" by my friend Howie when he was
taking a JCL course many years ago.

1 - Toss the deck of cards[1] in the air.
2 - Pick them up.
3 - If they're not sorted, go back to step 1.
4 - Exit.

While it can be inefficient, it does have the ability to be the most
efficient sort around, being able to sort N items in N+1 steps in the
best-case scenario.

:-)

[1] I told you it was a long time ago.


That's called a Bogo Sort. It has an average complexity of O(n n!).
In it's worse case, it is unbounded.

REH

Apr 10 '06 #15

P: n/a
Kenneth Brody wrote:
Skarmander wrote:

Robert Gamble wrote:
Joe Estock wrote:
> major wrote:
>> dembla wrote:
>>
>>> PROGRAM to print NxN Matrix
>>> 9 1 8 1 2 3
>>> 2 7 3 as 4 5 6
>>> 6 4 5 7 8 9
>>>
>>> in sorted form
>> the simplest way is:
>> put the values of the first matrix into an array,
>> sort it with a sorting algorithm (like bubble sort or quick sort or
>> whatever)
>> put the values of the vector into the result matrix.
>>

[snip]

> Bubble sort or quick sort is a good idea,

Bubble sort is never a good idea.

It's a bit curious that people continue to teach bubble sort as a basic
algorithm when insertion sort is hardly more complicated and better in
practice (for the small input sets bubble sort might proficiently be applied
to).


Use "The Howie Sort", which was "invented" by my friend Howie when he was
taking a JCL course many years ago.

1 - Toss the deck of cards[1] in the air.
2 - Pick them up.
3 - If they're not sorted, go back to step 1.
4 - Exit.

While it can be inefficient, it does have the ability to be the most
efficient sort around, being able to sort N items in N+1 steps in the
best-case scenario.

:-)


What you have described is known as bogosort and the best case scenerio
would sort the deck in 1 step. Possibly the only more inefficient sort
would be bozosort which picks 2 items at random, swaps their position,
checks for proper sort order and repeats.

Robert Gamble

Apr 11 '06 #16

P: n/a
Keith Thompson wrote:
Kenneth Brody <ke******@spamcop.net> writes:
Skarmander wrote:

[...]
It's a bit curious that people continue to teach bubble sort as a basic
algorithm when insertion sort is hardly more complicated and better in
practice (for the small input sets bubble sort might proficiently be applied
to).


Use "The Howie Sort", which was "invented" by my friend Howie when he was
taking a JCL course many years ago.

1 - Toss the deck of cards[1] in the air.
2 - Pick them up.
3 - If they're not sorted, go back to step 1.
4 - Exit.

While it can be inefficient, it does have the ability to be the most
efficient sort around, being able to sort N items in N+1 steps in the
best-case scenario.

:-)

[1] I told you it was a long time ago.


Strictly speaking, that's not an algorithm, since it's not guaranteed
to terminate.


He didn't call it an algorithm.

Robert Gamble

Apr 11 '06 #17

P: n/a
Robert Gamble wrote:
[...]
Use "The Howie Sort", which was "invented" by my friend Howie when he was
taking a JCL course many years ago.

1 - Toss the deck of cards[1] in the air.
2 - Pick them up.
3 - If they're not sorted, go back to step 1.
4 - Exit.

While it can be inefficient, it does have the ability to be the most
efficient sort around, being able to sort N items in N+1 steps in the
best-case scenario.

:-)


What you have described is known as bogosort and the best case scenerio
would sort the deck in 1 step. Possibly the only more inefficient sort
would be bozosort which picks 2 items at random, swaps their position,
checks for proper sort order and repeats.


Well, I did put "invented" in quotes. :-)

(It is possible to independently "invent" something that has already been
"invented". For all I know, Howie "invented" this before the "bogosort"
name was penned.)

Actually, an improvement in both these sorts would be to add a step zero:

0 - Check if the list is already sorted.

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:Th*************@gmail.com>

Apr 11 '06 #18

P: n/a
"Robert Gamble" <rg*******@gmail.com> writes:
Kenneth Brody wrote:

[...]
Use "The Howie Sort", which was "invented" by my friend Howie when he was
taking a JCL course many years ago.

1 - Toss the deck of cards[1] in the air.
2 - Pick them up.
3 - If they're not sorted, go back to step 1.
4 - Exit.

While it can be inefficient, it does have the ability to be the most
efficient sort around, being able to sort N items in N+1 steps in the
best-case scenario.

:-)


What you have described is known as bogosort and the best case scenerio
would sort the deck in 1 step. Possibly the only more inefficient sort
would be bozosort which picks 2 items at random, swaps their position,
checks for proper sort order and repeats.


My own Miracle Sort is even slower.

1. Start with an arbitrary array.
2. Check whether it's sorted. If so, we're done.
3. Wait a while; pray for alpha particles if you're so inclined.
4. Jump to step 2.

It could be made more reliable by checking whether the sorted array
(if we ever get one) matches the original array, but in my opinion
that makes the technique too complex.

(... checking Newsgroups: header ...)

Oh yeah, it's easy to implement in C.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Apr 11 '06 #19

P: n/a
In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:
My own Miracle Sort is even slower. 1. Start with an arbitrary array.
2. Check whether it's sorted. If so, we're done.
3. Wait a while; pray for alpha particles if you're so inclined.
4. Jump to step 2. Oh yeah, it's easy to implement in C.


How do you do step 3 automatically? sleep() is not standard C
(unistd.h) and you didn't specify anything about (e.g.,) waiting for
user input. If you use a null loop then the compiler might
optimize it out.

Say... if we use volatile on a loop variable, then do the requirements
to handle the volatile variable in the same way as the abstract machine
imply that the compiler would not be able to optimize out the idle loop?
--
If you lie to the compiler, it will get its revenge. -- Henry Spencer
Apr 11 '06 #20

P: n/a
"Kenneth Brody" <ke******@spamcop.net> wrote in message
news:44***************@spamcop.net...
Use "The Howie Sort", which was "invented" by my friend Howie when he was
taking a JCL course many years ago.

1 - Toss the deck of cards[1] in the air.
2 - Pick them up.
3 - If they're not sorted, go back to step 1.
4 - Exit.

While it can be inefficient, it does have the ability to be the most
efficient sort around, being able to sort N items in N+1 steps in the
best-case scenario.


I implemented this thing for a deck of cards in C (almost on topic!) some years
ago. Well, a lot of years ago now that I think of is, since I ran it on a VAX.
I had it run in the background (UNIX) and keep count of how many times it had
to "toss" before getting a result. Over a couple of weeks it ran anywhere from
ten passes to many many thousands. One run didn't terminate after several
days. I had to kill it.

- Bill
Apr 11 '06 #21

P: n/a
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes:
In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:
My own Miracle Sort is even slower.

1. Start with an arbitrary array.
2. Check whether it's sorted. If so, we're done.
3. Wait a while; pray for alpha particles if you're so inclined.
4. Jump to step 2.

Oh yeah, it's easy to implement in C.


How do you do step 3 automatically? sleep() is not standard C
(unistd.h) and you didn't specify anything about (e.g.,) waiting for
user input. If you use a null loop then the compiler might
optimize it out.

Say... if we use volatile on a loop variable, then do the requirements
to handle the volatile variable in the same way as the abstract machine
imply that the compiler would not be able to optimize out the idle loop?


I didn't specify how long to wait. This:

while (0);

meets the specification. In fact, it reduces the likelihood that the
array will be accidentally sorted and then unsorted between checks.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Apr 11 '06 #22

P: n/a
"William J. Leary Jr." <Bi********@msn.com> writes:
"Kenneth Brody" <ke******@spamcop.net> wrote in message
news:44***************@spamcop.net...
Use "The Howie Sort", which was "invented" by my friend Howie when he was
taking a JCL course many years ago.

1 - Toss the deck of cards[1] in the air.
2 - Pick them up.
3 - If they're not sorted, go back to step 1.
4 - Exit.

While it can be inefficient, it does have the ability to be the most
efficient sort around, being able to sort N items in N+1 steps in the
best-case scenario.


I implemented this thing for a deck of cards in C (almost on topic!)
some years ago. Well, a lot of years ago now that I think of is,
since I ran it on a VAX. I had it run in the background (UNIX) and
keep count of how many times it had to "toss" before getting a
result. Over a couple of weeks it ran anywhere from ten passes to
many many thousands. One run didn't terminate after several days.
I had to kill it.


How big was the deck? If it was a standard 52-card deck, I'd be
astonished if it *ever* sorted; there are 52!, or about 8e67,
permutations. (That's 8 * 10**67, not 0x8E67.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Apr 11 '06 #23

P: n/a
Keith Thompson wrote:
Kenneth Brody <ke******@spamcop.net> writes:
Skarmander wrote:

[...]
It's a bit curious that people continue to teach bubble sort as a basic
algorithm when insertion sort is hardly more complicated and better in
practice (for the small input sets bubble sort might proficiently be applied
to).

Use "The Howie Sort", which was "invented" by my friend Howie when he was
taking a JCL course many years ago.

1 - Toss the deck of cards[1] in the air.
2 - Pick them up.
3 - If they're not sorted, go back to step 1.
4 - Exit.

While it can be inefficient, it does have the ability to be the most
efficient sort around, being able to sort N items in N+1 steps in the
best-case scenario.

:-)

[1] I told you it was a long time ago.


Strictly speaking, that's not an algorithm, since it's not guaranteed
to terminate.

As described it's not an algorithm, but this is only because of the
vagueness of "tossing the deck" in step 1. If we take a truly random shuffle
of cards instead (that is, bogo-sort) the resulting algorithm will terminate
with probability 1. Then it depends on whether you want to call that an
"algorithm"...

S.
Apr 11 '06 #24

P: n/a
Skarmander <in*****@dontmailme.com> writes:
Keith Thompson wrote:

[...]
Strictly speaking, that's not an algorithm, since it's not guaranteed
to terminate.

As described it's not an algorithm, but this is only because of the
vagueness of "tossing the deck" in step 1. If we take a truly random
shuffle of cards instead (that is, bogo-sort) the resulting algorithm
will terminate with probability 1. Then it depends on whether you want
to call that an "algorithm"...


Just because it terminates with probability 1, that doesn't mean it's
guaranteed to terminate. Or something like that.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Apr 11 '06 #25

P: n/a
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org...
"William J. Leary Jr." <Bi********@msn.com> writes:
I implemented this thing for a deck of cards in C (almost on topic!)
some years ago. Well, a lot of years ago now that I think of is,
since I ran it on a VAX. I had it run in the background (UNIX) and
keep count of how many times it had to "toss" before getting a
result. Over a couple of weeks it ran anywhere from ten passes to
many many thousands. One run didn't terminate after several days.
I had to kill it.


How big was the deck? If it was a standard 52-card deck, I'd be
astonished if it *ever* sorted; there are 52!, or about 8e67,
permutations. (That's 8 * 10**67, not 0x8E67.)


Yep, 52 cards. I suppose if I'd thought about it ahead of time I wouldn't have
bothered, figuring it would never (or rarely) get a hit. But it sounded
interesting, and it was easy to set it to low priority and let it chew in the
background. In fact, it wasn't until just now that you mentioned it that I'm
really seeing that I should have been surprised it worked at all, never mind
succeeded dozens of times, sometimes with attempts into the hundreds of
thousands of "tosses."

- Bill
Apr 11 '06 #26

P: n/a
Skarmander wrote:

Robert Gamble wrote:
Joe Estock wrote:
major wrote:
dembla wrote:

> PROGRAM to print NxN Matrix
> 9 1 8 1 2 3
> 2 7 3 as 4 5 6
> 6 4 5 7 8 9
>
> in sorted form
the simplest way is:
put the values of the first matrix into an array,
sort it with a sorting algorithm (like bubble sort or quick sort or
whatever)
put the values of the vector into the result matrix.


[snip]
Bubble sort or quick sort is a good idea,


Bubble sort is never a good idea.

It's a bit curious that people continue to teach bubble sort as a basic
algorithm when insertion sort is hardly more complicated and better in
practice (for the small input sets bubble sort might proficiently be applied
to).

There are some cases where bubble sort is appropriate. If the input is
*almost* sorted already, then bubble sort is *more* efficient than
insertion sort.
--
+----------------------------------------------------------------+
| Charles and Francis Richmond richmond at plano dot net |
+----------------------------------------------------------------+
Apr 11 '06 #27

P: n/a
Charles Richmond wrote:
Skarmander wrote:
Robert Gamble wrote:
Joe Estock wrote: <snip> Bubble sort or quick sort is a good idea,
Bubble sort is never a good idea.

It's a bit curious that people continue to teach bubble sort as a basic
algorithm when insertion sort is hardly more complicated and better in
practice (for the small input sets bubble sort might proficiently be applied
to).

There are some cases where bubble sort is appropriate. If the input is
*almost* sorted already, then bubble sort is *more* efficient than
insertion sort.

I'd test that first. Insertion sort is usually still faster even on almost
sorted lists. When you get down to that level only benchmarking could tell
you what's better for specific implementations and platforms.

Bubble sort *may* be better under special circumstances, but it should only
be used after verifying that those circumstances apply. Hence my remark that
as a first approach to sorting, teaching insertion sort is likely to do less
damage and be more useful overall. Bubble sort is like goto: sometimes it's
the right tool for the job, but sometimes is rarely.

S.
Apr 11 '06 #28

P: n/a
Keith Thompson wrote:
"William J. Leary Jr." <Bi********@msn.com> writes:

.... snip ...

I implemented this thing for a deck of cards in C (almost on topic!)
some years ago. Well, a lot of years ago now that I think of is,
since I ran it on a VAX. I had it run in the background (UNIX) and
keep count of how many times it had to "toss" before getting a
result. Over a couple of weeks it ran anywhere from ten passes to
many many thousands. One run didn't terminate after several days.
I had to kill it.


How big was the deck? If it was a standard 52-card deck, I'd be
astonished if it *ever* sorted; there are 52!, or about 8e67,
permutations. (That's 8 * 10**67, not 0x8E67.)


The quality of the PRNG has something to do with the results. I
don't believe there is any such that can guarantee a sort in this
case. So you need an external truly random mechanism.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
Apr 11 '06 #29

P: n/a
Skarmander wrote:
Hence my remark that
as a first approach to sorting,
teaching insertion sort is likely to do less
damage and be more useful overall.
Bubble sort is like goto: sometimes it's
the right tool for the job, but sometimes is rarely.


I think that most programmers have picked up and sorted
a hand of playing cards one by one,
at some point in their lives,
and would not find insertion sort complicated.

I think bubblesort is only taught for academic reasons,
just because it is another simple algorithm.

--
pete
Apr 12 '06 #30

P: n/a
In article <44***********@mindspring.com>,
pete <pf*****@mindspring.com> wrote:
I think bubblesort is only taught for academic reasons,
just because it is another simple algorithm.


bubblesort does not require moving a lot of data around
(if one is inserting into an array), and does not require
dynamic memory allocation (if one does the insertions via
linked lists.) It is thus useful as a pratical example of
how arrays can be useful (and to emphasize that what is stored at
an array offset need not be a constant) at a point in learning
where students are not ready for more complex programs. Sorting
is generally recognized by students as being "useful", so students
can related to it.

When one is teaching, one must tailor what is being taught to
what the student is ready for, rather than immediately jumping
to a "very good" or "best possible" way of implementing something.

A well designed course would later on show other sorts and
provide an example to make it clear that efficiency in sorting
can be important. One must, however, keep in mind that if a
particular program is not going to be run very often, or if the sorts
are not going to be an important portion of the execution time,
then the time to understand and write and debug a better sort
simply might not be worth. Recall the maxims about the proper
role of optimization that go through here regularly: better sorts
are a form of optimization, and their use should be justified.
--
There are some ideas so wrong that only a very intelligent person
could believe in them. -- George Orwell
Apr 12 '06 #31

P: n/a
>In article <44***********@mindspring.com>,
pete <pf*****@mindspring.com> wrote:
I think bubblesort is only taught for academic reasons,
just because it is another simple algorithm.

In article <e1**********@canopus.cc.umanitoba.ca>
Walter Roberson <ro******@ibd.nrc-cnrc.gc.ca> wrote:bubblesort does not require moving a lot of data around
(if one is inserting into an array), and does not require
dynamic memory allocation (if one does the insertions via
linked lists.)
The first point is true of bubble sort and (at least to some extent)
less true of insertion sort (because we have to make room for the
insertion in the array). The second point is true of bubble sort
but also true of insertion sort (because list insertion of
already-existing elements is straightforward, especially if one
uses list macros in C, or containers in C++, or the built-in
facilities in Lisp, etc).

[snippage]
When one is teaching, one must tailor what is being taught to
what the student is ready for, rather than immediately jumping
to a "very good" or "best possible" way of implementing something.


True; and I would not introduce students to Shell sort as their
first-ever sort. But insertion sort -- well, if you have a shuffled
deck of cards handy, pick out two cards and hold them in one hand.
Then sort them (this is easy). Then pick up more cards, one at
a time, and "sort them in" until you have an appropriate-size hand,
e.g., 5 cards. How do you do it? Most people grab an "unsorted"
card and wedge it into its "properly sorted position", then grab
the next "unsorted card" and wedge *it* into *its* "properly
sorted position", and so on.

This *is* insertion sort, and doing the demonstration should make
the procedure obvious: "Take next unsorted card, find correct
position, insert." (And, in my experience, it is actually easier
to write a correct insertion sort than to write a correct bubble
sort.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
Apr 12 '06 #32

P: n/a
Chris Torek wrote:
In article <44***********@mindspring.com>,
pete <pf*****@mindspring.com> wrote:
I think bubblesort is only taught for academic reasons,
just because it is another simple algorithm.
In article <e1**********@canopus.cc.umanitoba.ca>
Walter Roberson <ro******@ibd.nrc-cnrc.gc.ca> wrote:
bubblesort does not require moving a lot of data around
(if one is inserting into an array),


For disordered arrays of more than 15 elements,
bubblesort moves more data, than heapsort does.
and does not require
dynamic memory allocation (if one does the insertions via
linked lists.)


The first point is true of bubble sort and (at least to some extent)
less true of insertion sort (because we have to make room for the
insertion in the array).


I disagree about "less true of insertion sort" to any extent.
The slowest least efficient way to implement insertion sort,
is as a swapping algorithm.
As a swapping algorithm, insertion sort does exactly
the same amount of data movement as bubblesort.
And assuming that you count a simple assignment as being
less data movement than a data swap:
then
when insertion sort is implemented with a temp data variable,
then insertion sort does less data movement than bubble sort.

Using q_sort.c
http://www.mindspring.com/~pfilandr/C/q_sort/

/************************************************** *****************
0: b_sort 19682 Cmp 10138 Swp, i_sort 10333 Cmp 10138 Swp,
1: b_sort 19673 Cmp 9862 Swp, i_sort 10058 Cmp 9862 Swp,
2: b_sort 19674 Cmp 9597 Swp, i_sort 9788 Cmp 9597 Swp,
3: b_sort 19726 Cmp 9289 Swp, i_sort 9482 Cmp 9289 Swp,
4: b_sort 19822 Cmp 10213 Swp, i_sort 10409 Cmp 10213 Swp,
5: b_sort 19007 Cmp 9787 Swp, i_sort 9981 Cmp 9787 Swp,
6: b_sort 19583 Cmp 10661 Swp, i_sort 10854 Cmp 10661 Swp,
7: b_sort 19817 Cmp 10124 Swp, i_sort 10320 Cmp 10124 Swp,
8: b_sort 19615 Cmp 9885 Swp, i_sort 10078 Cmp 9885 Swp,
9: b_sort 19607 Cmp 10554 Swp, i_sort 10748 Cmp 10554 Swp,

10 Trials, 200 keys, 4294967295 possible key values
The array elements are of type long unsigned.

total b_sort comparrisons: 196206
total i_sort comparrisons: 102051

total b_sort swaps: 100110
total i_sort swaps: 100110

SEQUENCE is RANDOM
/************************************************** ********/

void b_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *last, *next, *middle;
unsigned char *p1, *p2, *end, swap;

if (nmemb-- > 1) {
last = base;
last += nmemb * size;
do {
middle = next = base;
do {
if (compar(middle, middle + size) > 0) {
BYTE_SWAP(middle, middle + size);
next = middle;
}
middle += size;
} while (middle != last);
last = next;
} while (last != base);
}
}

void i_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *array, *high, *low;
unsigned char *p1, *p2, *end, swap;

if (nmemb-- > 1) {
array = base;
do {
low = array;
array += size;
high = array;
while (compar(low, high) > 0) {
BYTE_SWAP(low, high);
if (low == base) {
break;
}
high = low;
low -= size;
}
} while (--nmemb != 0);
}
}

#define BYTE_SWAP(A, B) \
{ \
p1 = (A); \
p2 = (B); \
end = p2 + size; \
do { \
swap = *p1; \
*p1++ = *p2; \
*p2++ = swap; \
} while (p2 != end); \
}

--
pete
Apr 12 '06 #33

P: n/a
pete wrote:

Chris Torek wrote:
In article <44***********@mindspring.com>,
pete <pf*****@mindspring.com> wrote:bubblesort
insertion sort
The slowest least efficient way to implement insertion sort,
is as a swapping algorithm.
As a swapping algorithm, insertion sort does exactly
the same amount of data movement as bubblesort.
And assuming that you count a simple assignment as being
less data movement than a data swap:
then
when insertion sort is implemented with a temp data variable,
then insertion sort does less data movement than bubble sort.


And there's also the bubblesort insertionsort hybrid,
which is also stable
and has very tight inner loops on the insertionsort part:
void sisor2(e_type *array, size_t nmemb)
{
e_type *low, *high, temp;

if (nmemb-- > 1) {
low = array + nmemb;
do {
high = low--;
if (GT(low, high)) {
temp = *high;
*high = *low;
*low = temp;
}
} while (low != array);
if (nmemb-- > 1) {
++array;
do {
low = array++;
if (GT(low, array)) {
high = array;
temp = *high;
do {
*high-- = *low--;
} while (GT(low, &temp));
*high = temp;
}
} while (--nmemb != 0);
}
}
}

--
pete
Apr 22 '06 #34

This discussion thread is closed

Replies have been disabled for this discussion.