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()

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.

 

[Chris McDonald]

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: (e-mail address removed)
School of Computer Science & Software Engineering
The University of Western Australia WWW: http://www.csse.uwa.edu.au/~chris
Crawley, Western Australia, 6009 PH: +61 8 6488 2533, FAX: +61 8 6488 1089

 

[James Hu]

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()[/QUOTE]

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(FILE *fp, int *i)
{
int v = fscanf(fp, "%d", i);
return (v != 0 && v != EOF);
}

int read_all_ints(FILE *fp, int *v, unsigned num)
{
return num && read_one_int(fp, v) && read_all_ints(fp, v+1, num-1);
}

-- James

 

[Keith Thompson]

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?)

 

[Barry Schwarz]

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:

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]

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]

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.

 

[Wolfgang Denk]

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

 

[Malcolm]

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]

(e-mail address removed) (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]

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

 

[RoSsIaCrIiLoIA]

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]

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 (e-mail address removed)

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]

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.