Sorting a list of integers in C

[aruna]

Given a set of integers, how to write a program in C
to sort these set of integers using C, given the following conditions
a. Do not use arrays
b. Do not use any comparison function like if/then
or switch-case
c. you can use pointers only
d. you cannot use any of the loops either.

[Malcolm]

"aruna" <ar********@yah oo.co.in> wrote in message

Given a set of integers, how to write a program in C
to sort these set of integers using C, given the following conditions
a. Do not use arrays
b. Do not use any comparison function like if/then
or switch-case
c. you can use pointers only
d. you cannot use any of the loops either.

You need to find out what your instructor is driving at. For instance is a
pointer to malloced memory allowed instead of an array? In a real program
you would only rarely have a fixed-length array to sort.

The second question is, is qsort() allowed? In a hosted, ie standard,
environment this is how a C programmer would naturally tackle the problem.
Of course if the problem is to implement qsort() itself, then this is
cheating.
qsort takes a function pointer which returns less than zero, zero, or
greater than zero. Integers thus have the quirk that no conditional jump is
needed in the comparison function.
I don't understand the loop restriction, since the obvious way to test that
the sort has worked is to loop through it printing out values. It is also
hard to write a sane sort routine that doesn't use loops at some stage,
though it is probably possible to do so.

[kal]

ar********@yaho o.co.in (aruna) wrote

Given a set of integers, how to write a program in C
to sort these set of integers using C, given the following conditions
a. Do not use arrays
b. Do not use any comparison function like if/then
or switch-case
c. you can use pointers only
d. you cannot use any of the loops either.

WARNING: NO WARRANTY OF ANY KIND IS IMPLIED OR PROVIDED.
CODE GIVEN HEREIN HAS NOT BEEN TESTED IN ANY WAY WHATSOEVER.

Seems to be a reasonable problem but I am not sure if you have
stated the problem as given to you. The mischief seems to be
in two places.

(1) "Given a set of integers" is ok for math but HOW are these
integers _given_ to the program? One assumes that it is a finite
set. If so is the code to be written for one particular cardinality?

It is dangerous to use big words like "set." It is often the case
that _interesting_ programs that one thinks of are often very
difficult to state precisely.

(2) Does condition (b) aplly to all parts of the code or for
comparing the integers only.

The task seems to involve pointers, linked lists, recursion and
one mathematical trivia. The trivia is: given two integers,
a and b, how does one find which is lesser and which is greater,
if any. The following code stores the lesser (or equal) integer
in 'a' and the greater (or equal) in 'b'.

int a, b;
long x, y;

x = a + b;
y = abs(a - b);
a = (x - y) / 2;
b = (x + y) / 2;

Now, to sort a finite set of integers whose cardinality is known
apriori (another big word for you) all one has to do is implement
the bubble sort alogorithm but unroll the loops.

May be someone else with a better knowledge of C will post as to
how to do this without unrolling the loops.

Hope this helps.

P.S. If one is using C++ then one can make use of the try - catch
mechanism to detect end conditions, such as end of file, and thus
avoid having to unroll the read loop or the bubble sort loop.

[Vic Dura]

On Sat, 24 Apr 2004 15:30:17 +0000 (UTC), RE: Re: Sorting a list of
integers in C Chris McDonald <ch***@csse.uwa .edu.au> wrote:

ar********@yah oo.co.in (aruna) writes:

Given a set of integers, how to write a program in C
to sort these set of integers using C, given the following conditions
a. Do not use arrays
b. Do not use any comparison function like if/then
or switch-case
c. you can use pointers only
d. you cannot use any of the loops either.

Why do some College professors continue to set such unrealistic homework
questions!? Why don't students question the unrealistic nature of these
questions?

An exercise in pointlessness?

"...We don't learn that much subject matter in school anyway in
proportion to the huge part of our lives that we spend there. But what
we do learn very well, thanks to the method, is to accept choices that
have been made for us. Which rule they make you follow is less
important than the fact that there are rules. I hear about English
teachers who won't allow their students to begin a sentence with
"and." Or about high schools where the male students are not permitted
to wear a T- shirt unless it has a pocket. I no longer dismiss such
rules as merely pointless. The very point to such rules is their
pointlessness.. ." Jerry Farber, 1969
--
To reply to me directly, remove the XXX characters from my email address.

[RoSsIaCrIiLoIA]

On 24 Apr 2004 07:45:01 -0700, ar********@yaho o.co.in (aruna) wrote:

Given a set of integers, how to write a program in C
to sort these set of integers using C, given the following conditions
a. Do not use arrays
b. Do not use any comparison function like if/then
or switch-case
c. you can use pointers only
d. you cannot use any of the loops either.

the only way that I see without cheat (array of struct or array of
pointers) is save the numbers in the input args of a recursive
functions.

[Michael Wojcik]

In article <a5************ **************@ posting.google. com>, k_*****@yahoo.c om (kal) writes:

May be someone else with a better knowledge of C will post as to
how to do this without unrolling the loops.

An iterative algorithm can always be transformed into a recursive
algorithm and vice versa.

It's easy to see how to implement a selection sort, for example, on a
linked list using recursion. Set a "current-smallest" variable to
the value of the first node in the list. Recurse on the remainder of
the list, passing a pointer to the current-smallest. On entry to the
recursion function check that the value of the head of the list is
not smaller than the value pointed to by current- smallest; if it is,
set current-smallest to the new value.

When the first recursive pass ends, emit current-smallest. Then
recurse through the list again and remove the first node you
encounter that has the value you just emitted.

Now the top-level function calls itself again on the modified list.
The entire process will continue recursively until the list is empty
(the top-level function checks this as its end condition).

--
Michael Wojcik mi************@ microfocus.com

Painful lark, labouring to rise!
The solemn mallet says:
In the grave's slot
he lies. We rot. -- Basil Bunting

[Neil Kurzman]

The Question no one asked is what are you learning?
The limitations given must be to force the use of some classroom topic.
If the topic is linked lists handing in qsort() teaches nothing.

[Ben Pfaff]

Neil Kurzman <ns*@mail.asb.c om> writes:

The Question no one asked is what are you learning?
The limitations given must be to force the use of some classroom topic.
If the topic is linked lists handing in qsort() teaches nothing.

I'd say that the restrictions given would also cause learning
just about nothing, except how to get around unreasonable
restrictions.
--
"What is appropriate for the master is not appropriate for the novice.
You must understand the Tao before transcending structure."
--The Tao of Programming