473,322 Members | 1,714 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

VERY URGENT C PROGRAM

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
33 3341
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
"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
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
"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
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
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
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
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
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
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
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
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
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
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
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
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
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
"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
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
"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
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
"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
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
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
"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
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
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
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
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
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
>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 (40°39.22'N, 111°50.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
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: newbie | last post by:
Hi I am using a toolkit written in c++ that consists of three parts 1) video captur 2) image processin 3) OpenGL wrappe The video capture program only works with local hardware (for...
1
by: alok sengar | last post by:
hi, I have already tried this URL's code "http://www.java2s.com/Code/CSharp/Network/SimpleSNMP.htm" but I am getting error when i am creating a UDP type Socket and recieving packet from this...
3
by: N. Spiker | last post by:
I am attempting to receive a single TCP packet with some text ending with carriage return and line feed characters. When the text is send and the packet has the urgent flag set, the text read from...
1
by: dasilva109 | last post by:
Hi guys I am new to C++ and need urgent help with this part of my code for a uni coursework I have to submit by Thursday //ClientData.h #ifndef CLIENTDATA_H #define CLIENTDATA_H #include...
1
by: palani12kumar | last post by:
can any one please tell what will be the output of the following program. its very urgent.......... main() { extern int fun(float); int a; a=fun(3.14); printf(“%d”,a); } int fun(float aa)
1
by: rajesh.us.it.recruiter | last post by:
Hi Guys/Partners, We have a URGENT Requirement for Perl Programmer with H1 visa in India/US for one of our prestigious Client. Location : New Jersey Requirements : Should be very strong in...
0
by: nobin01 | last post by:
Dear sir; I want ur Help in serialization.I know serialization.I Know binary,soap and xmlserialization also.But i want ur help in following topics.pls help me as soon as possible.I have search in...
9
by: uppili4chi | last post by:
Good morning my dear friends, I am uppili from India. i am working in one mnc. I need a help very urgent. "My problem i need to write a program for search a file just like search option at...
5
by: madman228 | last post by:
Hi guys I'm new to java and have no idea how what to do with this problem. If someone can help me get started with this program it'll be really appriciated. The problem is: Design and implement...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.