473,320 Members | 2,117 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,320 software developers and data experts.

Sorting a list of integers in C

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.
Nov 14 '05 #1
16 3343
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.
Nov 14 '05 #2
ar********@yahoo.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: +61 8 6488 2533, FAX: +61 8 6488 1089
Nov 14 '05 #3
On 2004-04-24, James McIninch <ja************@comcast.net.spam> wrote:
[Top posting fixed by "AutoTopPostIncinerator 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(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
Nov 14 '05 #4
Chris McDonald <ch***@csse.uwa.edu.au> writes:
ar********@yahoo.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_Keith) 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"
Nov 14 '05 #5
On 24 Apr 2004 07:45:01 -0700, ar********@yahoo.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>>
Nov 14 '05 #6
Keith Thompson posted the following:
Chris McDonald <ch***@csse.uwa.edu.au> writes:
ar********@yahoo.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.
Nov 14 '05 #7
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;
}
Nov 14 '05 #8
ar********@yahoo.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
Nov 14 '05 #9
ar********@yahoo.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: (+49)-8142-4596-87 Fax: (+49)-8142-4596-88 Web: www.denx.de
"Send lawyers, guns and money..." - Lyrics from a Warren Zevon song
Nov 14 '05 #10

"aruna" <ar********@yahoo.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.
Nov 14 '05 #11
kal
ar********@yahoo.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.
Nov 14 '05 #12
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********@yahoo.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.
Nov 14 '05 #13
On 24 Apr 2004 07:45:01 -0700, ar********@yahoo.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.
Nov 14 '05 #14

In article <a5**************************@posting.google.com >, k_*****@yahoo.com (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
Nov 14 '05 #15


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.

Nov 14 '05 #16
Neil Kurzman <ns*@mail.asb.com> 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
Nov 14 '05 #17

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

13
by: Paul | last post by:
Hi all I have a sorting problem, but my experience with Python is rather limited (3 days), so I am running this by the list first. I have a large database of 15GB, consisting of 10^8 entries...
22
by: mike | last post by:
If I had a date in the format "01-Jan-05" it does not sort properly with my sort routine: function compareDate(a,b) { var date_a = new Date(a); var date_b = new Date(b); if (date_a < date_b)...
6
by: Michel | last post by:
Hi All, I need to loop through a sorted datatable. Looping is not a problem, but sorting is. The datacolumns on which I want to sort, exists of numbers, which causes the 10 to appear before...
25
by: Dan Stromberg | last post by:
Hi folks. Python appears to have a good sort method, but when sorting array elements that are very large, and hence have very expensive compares, is there some sort of already-available sort...
16
by: Kittyhawk | last post by:
I would like to sort an Arraylist of objects on multiple properties. For instance, I have a Sort Index property and an ID property (both integers). So, the results of my sort would look like this:...
9
by: robin9876 | last post by:
I have a list of integers (example sub set of data below), what is the best method of sorting these in code? 1, 872 5, 1283 8, 343 9, 123
3
by: Harry Haller | last post by:
Hello, I want to implement a generic list which will be used to display 7 columns in a GridView. One should be able to sort, filter and page each of the 7 columns. Ideally the filter should be...
5
by: lemlimlee | last post by:
hello, this is the task i need to do: For this task, you are to develop a Java program that allows a user to search or sort an array of numbers using an algorithm that the user chooses. The...
4
by: slapsh0t11 | last post by:
Hello! I need help with a program that I believe I am nearly done with. However, there seems to be a few details that preclude me from success. Here is my assignment: Here is my class file...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
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: 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
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

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.