Compare function in recursive mode

Posted on 2012-08-30
Last Modified: 2012-09-29
I have wrote complete program. But, stuck in compare function in recursive mode.
Not getting how to maintain flags and return.

Need help.

Problem statement is as :
Write a program that finds the kth smallest Number from a list of any base-n numbers (for
any n up to a fixed maximum value, maxN). The definition of the ADT called Number is
the same as that defined in Lab-1. For ease of implementation, assume that each digit is
represented by a character. A separate lookup table needs to be created for storing the
symbols (character) corresponding to the various digit values.
The program must take two command-line parameters:
the first parameter is the name of a file containing the sequence of characters to
be used for the digit values from 0 to maxN-1, and
the second parameter is the name of a file containing N Numbers.
The sequence of characters corresponding to digit values 0 to maxN-1 is given in the first
line of the first input file, separated by spaces. Note that maxN to be used in the particular
instance of execution is calculated by the number of entries in the first line. Only
alphanumeric characters can be used for representing digits in the number system. (Note
that the total number of alphanumeric characters is limited to 62.)
Consider this sample file:
b i g s o u n d
By reading this you should infer that maxN is 8 and the value of symbol o is 4 and that of
symbol n is 6 and so on.
The second input file contains a list of N Numbers, with one Number in each line.
Consider the following sample (second) file: containing the numbers 59 in base-6, 36 in
base-8, 10 in base-2, 7 in base-3, 576 in base-4, 9 in base-2. Representation of the first
number in File2 is shown below.
F ile2:

6 isu
8 go
2 ibib
3 gi
4 gibbs
2 ibbi
Type definitions:
The definition for lookup table named Base, containing a list of symbols indexed by
digit values. Note that since the base is immutable (i.e. won’t change), the list can
be allocated at time of definition.
The type definition for a Number, containing the fields: the base of the number, a
linked list of digits each of which is a character, and other field that may be useful.
The type definition for an enumerated type called Order, that can have either
Design of Base ADT with the following operations
(a) int initializeBase(FILE *basefile) : reads the file containing the
characters corresponding to each digit, populates the lookup table and returns the
maximum base supported in the current execution. Note that to use the number
system; this function has to be called first, before any other function.
(b) int lookup(char c) : looks-up the character in the Base lookup table and
returns the value associated with the character.
Design of Number ADT with the following operations:
(a) Number createNumber(char *number_format): takes the number
format as a string containing the base of the number, followed by a space, followed
by the number using the custom characters(Most Significant Digit first). This
function then creates a Number using the values corresponding to the digits and
returns it.
(b) void printNumber(Number n): prints the Number in the base stored in
the system.
(c) Number convert(Number n, int to_base): converts the number n to a
number of base to_base, and returns it.
(d) Order compare(Number n1, Number n2): This function is used to
compare two Numbers of any valid base. This function returns GREATER if n1 >
n2; LESSER if n1 < n2; or EQUAL if n1 = n2. This function must be written using
(e) int partition(Number list[], int start, int end): This
function partitions the list[start...end] into 2 sublists, such that all
Numbers in left sublist is less than a chosen pivot and all the Numbers in the right
sublist are greater than the chosen pivot. Here, the pivot element is chosen as
median of the five elements list[start], list[(start+end)/4],
list[(start+end)/4*3], list[(start+end)/2], and list[end].
This function uses compare described above for comparison.
(f) Number quickSelect(Number list[], int size, int k): This
functions returns the kth smallest Number in the list, using an iterative version of
quickselect. This function uses partition described above for partitioning about
a pivot element,
Question by:prabhatia
    LVL 37

    Accepted Solution

    Well, since they are different bases you need to carry the difference so far around with you. Something like this (C-like syntax)

    bool compare(Number n1, Number n2) //returns boolean
      return compareH(Number n1, Number n2, 0);
    bool compareH(Number n1, Number n2, int leftGreater) //int for decimal integer
      int difference = valueOfFirstDigit(n1) - valueOfFirstDigit(n2);
      leftGreater = leftGreater + difference; //So you always maintain the total difference
      if (n1 and n2 are 0) //If they have both hit 0, then leftGreater now contains the difference
        return leftGreater;
        return compareH( stripFirstDigit(n1), stripFirstDigit(n2), leftGreater);
        //Note, if one has run out of digits, stripFirstDigit should leave it at 0.

    Open in new window

    There are probably ways to improve this, but this gives a general idea.
    LVL 37

    Expert Comment

    Giving a C grade without explaining why is generally considered impolite on Experts Exchange. Also, you never said what you didn't like about the solution or gave a chance for the experts to improve the answer to give you what you wanted. If the solution gave you what you needed, then give an A grade; if it didn't, comment and the experts will generally get you what you need.


    Featured Post

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Join & Write a Comment

    Article by: Nadia
    Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
    The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
    Sending a Secure fax is easy with eFax Corporate ( First, Just open a new email message.  In the To field, type your recipient's fax number You can even send a secure international fax — just include t…
    This video gives you a great overview about bandwidth monitoring with SNMP and WMI with our network monitoring solution PRTG Network Monitor ( If you're looking for how to monitor bandwidth using netflow or packet s…

    745 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    16 Experts available now in Live!

    Get 1:1 Help Now