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.

[James McIninch]

Use qsort()

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.

--
remove .spam from address to reply by e-mail.

[Chris McDonald]

ar********@yaho o.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?

_______________ _______________ _______________ _______________ _______________ ____
Dr Chris McDonald EMAIL: ch***@csse.uwa. edu.au
School of Computer Science & Software Engineering
The University of Western Australia WWW: http://www.csse.uwa.edu.au/~chris
Crawley, Western Australia, 6009 PH: [phone], FAX: [phone]

[James Hu]

On 2004-04-24, James McIninch <ja************ @comcast.net.sp am> wrote:
[Top posting fixed by "AutoTopPostInc inerator X++ Professional Edition" ]

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.

Use qsort()

Right, but the other piece of the puzzle is how to absorb the input
without using a loop?

I suppose I could cheat with recursion like this:

#include <stdio.h>

int read_one_int(FI LE *fp, int *i)
{
int v = fscanf(fp, "%d", i);
return (v != 0 && v != EOF);
}

int read_all_ints(F ILE *fp, int *v, unsigned num)
{
return num && read_one_int(fp , v) && read_all_ints(f p, v+1, num-1);
}

-- James

[Keith Thompson]

Chris McDonald <ch***@csse.uwa .edu.au> writes:

ar********@yaho o.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?

The point of such an exercise is to let the students learn about some
advanced construct. The best way to learn how to use something is to
try it out. A problem for which the construct is the natural solution
may be too complex for the students at their current level; applying
the construct to a simpler problem is actually sensible, even if
there's a simpler solution to the same problem.

When a student writes a sorting routine, it's not because he really
needs to sort a list of integers. Sorting a simple array of integers
isn't a realistic problem (in real life, it's more common to want to
sort a list of records using one field of each record as the key), but
it's a good way to teach sorting without bringing in too many other
concepts.

Having said that, I'm not sure what the problem description is aiming
for. The no-arrays restriction seems to imply linked lists, but the
restriction on if-then, switch-case, and loops is odd. (Recursion and
the "?:" operator, maybe?)

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"

[Barry Schwarz]

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.

If this is an accurate statement of the problem issued by the
instructor and if you had the option, I think many of us would
recommend you change instructors.

From a pedagogical point of view, others have already pointed out how
completely unrealistic it is. We never hear of structural engineering
students being asked to rebuild stonehenge or the pyramids without the
use of ramps and pulleys. The fact that someone was able to solve the
problem umpteen thousand years ago does not mean there is any
educational benefit in redoing it.

From a technical point of view:

Someone should tell your instructor that if and switch are not
functions but statements.

Since pointers must point somewhere to be valid and useful, the
program must contain some variables of a type other than pointer
unless every pointer points to a dynamically allocated area.

Since you are writing a complete program and not just a function,
you must have a main. Since you will be given the values to be sorted
they must be passed to main from the command line. In order for main
to receive these values it must have two parameters, the first of
which must be an int. You now have something other than a pointer
variable.

There are no standard integer comparison functions. There are
comparison operators that accept integers and at least three
non-integer comparison functions. Which are you forbidden to use, the
operators or the functions? Does your instructor consider the ?:
operator to be one of the forbidden ones?

Since you cannot use do, for, while, if, or switch, I do not see how
you can handle an unknown quantity (determined at run time) of
integers. If the quantity of integers is known at coding time, some
approaches come to mind:

Dynamically allocate an area of memory capable of holding the
quantity of integers. Transfer the values to this area, possibly by
using memcpy(), strtod(), one of the functions in the scanf family,
fread, etc, depending on how they are given to you. Finally call
qsort to sort the values in what looks like an array but was never
declared as one. For the comparison function, simply subtract one
value from the other. qsort requires only that the sign of the return
value indicate the relative ordering.

Convert each integer value to a dynamically allocated "array" of
strings (remember to include leading zeros). Call qsort. For the
compare function, simply adjust the pointer types and call strcmp.

Use a nested sequence of ?: operators. This is definitely not
good style but for values a, b, and c
a > b?
(a > c ?
(b > c ?
(x = a, y = b, z = c) :
(x = a, y = c, z = b)) :
(x = c, y = a, z = b)) :
(b > c ?
(a > c ?
(x = b, y = a, z = c) :
(x = b, y = c, z = a)) :
(x = c, y = b, z = a))
produces x, y, and z in order.

Questions like these come up rather frequently. If you google the
archives with a sufficiently clever search parameter you may come up
with some better previous suggestions.
<<Remove the del for email>>

[kevin collins]

Keith Thompson posted the following:

Chris McDonald <ch***@csse.uwa .edu.au> writes:

ar********@yaho o.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?

The point of such an exercise is to let the students learn about some
advanced construct. The best way to learn how to use something is to
try it out. A problem for which the construct is the natural solution
may be too complex for the students at their current level; applying
the construct to a simpler problem is actually sensible, even if
there's a simpler solution to the same problem.

When a student writes a sorting routine, it's not because he really
needs to sort a list of integers. Sorting a simple array of integers
isn't a realistic problem (in real life, it's more common to want to
sort a list of records using one field of each record as the key), but
it's a good way to teach sorting without bringing in too many other
concepts.

Having said that, I'm not sure what the problem description is aiming
for. The no-arrays restriction seems to imply linked lists, but the
restriction on if-then, switch-case, and loops is odd. (Recursion and
the "?:" operator, maybe?)

I think it's a stupid, stupid assignment.

If I were to attack it I would think of a tree, recursion and conditional
expressions. After all there isn't much left of the C "repertoire " after
all those savage removals. And even this is dependant on the instructor's
personal cherished meaning of "like" in clause b. Like is a sufficiently
nebulous word that this might pass muster.

This kind of thing belongs in a bar where programmers hang out after work,
not in a school.

[Martin Ambuhl]

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.

#include <stdlib.h>

int main(void) {
/* you might write code to create the argument for following line
with the appropriate substitutions for the file names and the
name of the sorting program */
system("sort <unsorted_file_ of_ints >sorted_file_of _ints");
return 0;
}

[Ben Pfaff]

ar********@yaho o.co.in (aruna) writes:

b. Do not use any comparison function like if/then
or switch-case

You're in luck: `if', `switch', and `case' are statements, not
functions, and C doesn't even have `then'. This is obviously a
trick designed to let those who know proper C write a reasonable
program, but force others to deal with stupid restrictions.
--
"To get the best out of this book, I strongly recommend that you read it."
--Richard Heathfield

[Wolfgang Denk]

ar********@yaho o.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.

e. do not cheat with your homework
Wolfgang Denk

--
Software Engineering: Embedded and Realtime Systems, Embedded Linux
Phone: [phone] Fax: [phone] Web: www.denx.de
"Send lawyers, guns and money..." - Lyrics from a Warren Zevon song