Qsort-ing structures

Discussion in 'C Programming' started by Albert, Feb 19, 2009.

  1. Albert

    Albert Guest

    Hi:

    I did a 4-hour programming contest this morning-early afternoon and I
    had the following problem which I'll put in a nutshell, hopefully
    that's enough to get even the vaguest idea as to what my code (when I
    post it) was to intentionally do

    --
    You love playing Space Invaders. It's where ONE row of enemy bots are
    on the top of the screen. You're on the bottom and may move only
    horizontally. When you fire, you fire straight up till the bullet
    destroys an enemy. You love the game so much that you stay all night
    playing it. Therefore, you eventually get to the last and hardest
    level. In this level, some of the screen is covered with polygons. If
    the polygon happens to cover a particular column, firing at that
    column won't do anything. So if the input tells you how wide and how
    tall the screen is (I believe it was from 3 -> 10^7 for both
    dimensions) and you assume that the whole top row is covered with
    enemies, and in the input you're given the number of polygons and the
    points of the corners of them, work out how many enemies you can
    destroy on this static screen save your maneuvering of your bot.
    --

    What I ended up doing was creating a struct representing a polygon. It
    stored the number of points needed to describe the polygon (which was
    part of the input data), it had an array of all the x coordinate
    values inputted for this particular polygon and stored also the
    smallest and largest x value in the array. The reason I didn't store
    the y coordinate is because it's not needed in my algorithm (which I
    believe is correct, would have been fast enough had I managed to code
    it properly...).

    Once you've stored all the input into an array of ships (I declared my
    type as struct ship {...} ships [10^5 + 2];) you sort the ships[] from
    ship with the lowest x coordinate to the highest (ie by the ship's sx
    [smallest x] increasing).

    Then, essentially you sweep from the leftmost ship to the rightmost
    ship. You find the difference of each ship's smallest and largest x
    coordinate and subtract it from the variable, nfire (the number of
    enemies you can destroy which starts off as the width inputted) and at
    the end of the algorithm you output nfire.

    The catch is when one ship is in front of another. Or, one ship's x
    coordinate is in between another ship's smallest and largest x
    coordinate. In this case, subtracting differences of smallest and
    largest values from nfire wouldn't work because there will surely be
    test cases where the ships 'overlap'. So - that's why I wantED to sort
    my ships array. Continually searching through each ship for similar x
    coordinates would timeout. A maximum of 10^5 ships can be described
    and such an algorithm would take O(nships^2) which is unusable,
    considering the assumption that a computer can process approximately
    10^8 (but really it should be 3 * 10^8 but we like powers of ten)
    instructions per second (and the time limit in most problems in this
    olympiad are 1 second). So I thought the inbuilt qsort() would work
    but I couldn't get it to work.

    Let's simplify the problem before I get the full problem statement
    again (can't access it outside the competition times anymore until
    sometime) and my code which I left saved on the school network.

    struct ship {
    int sx;
    } ships[10^5];

    fscanf()....//into ships.sx

    qsort(ships, 10^5, //comparison function//);

    How do I get qsort to sort the array of structures accordign to sx?

    Thanks
    Albert
     
    Albert, Feb 19, 2009
    #1
    1. Advertising

  2. Albert

    CBFalconer Guest

    Gordon Burditt wrote:
    >
    >> Once you've stored all the input into an array of ships (I
    >> declared my type as struct ship {...} ships [10^5 + 2];) you
    >> sort the ships[] from ship with the lowest x coordinate to the
    >> highest (ie by the ship's sx [smallest x] increasing).

    >
    > You do realize, don't you, that 10^5 as a C expression is not
    > 10000 but a much smaller number? ^ is not an exponentiation
    > operator in C. If you declared your array as somestruct[10^5],
    > you're going to have a massive array overflow if you read in
    > 10000 data points.


    Who, may I ask, is 'you'?

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.
     
    CBFalconer, Feb 21, 2009
    #2
    1. Advertising

  3. Albert

    Albert Guest

    I wrote:
    > Let's simplify the problem before I get the full problem statement
    > again...[M]y code [was] saved on the school network*
    > [snip]


    The 'full problem statement' and the code which I have since typed up
    from scratch is at http://albert.xtheunknown0.googlepages.com/spaceinvaders

    Note that the code currently deals with the input only. I've been
    trying to divide this program into several functions and I'm trying to
    get the design right for now.
    I've been fiddling around with header files and #include's; I can't
    get the files to all compile because I don't really understand how all
    these declartions work across multiple files. Could you please suggest
    as to how to split the current source code into files and how to
    #include them in each of the files?

    @Richard: Thanks for the code; I got three out of 20 test cases
    correct without a sort (and that O(n) algorithm has been putting me
    off lately) since I had the correct algorithm, but strictly given non-
    overlapping polygons. I was expecting to have a problem in coming up
    with slow algorithms but instead I couldn't get a sort to work for a
    correct AND a O(nlog(n)) algorithm!

    @Burditt: Actually I didn't realise that during the contest. I think
    that's why my results said (for around the first 10 cases) my program
    generated either the incorrect answer or that it crashed...

    @CBFalconer: Is that a rhetorical question?

    *I saved my source files along with a temp copy of Dev-cpp portable in
    the C:\ during the contest; logging off automatically wiped (and
    wipes) any changes made on a school computer. I forgot to keep a copy
    of my original source file on my USB :|

    Thanks a lot,
    Albert
     
    Albert, Feb 28, 2009
    #3
  4. Albert

    Albert Guest

    Albert, Mar 1, 2009
    #4
  5. Albert <> writes:

    > When I try to compile each of the .c files at
    > http://albert.xtheunknown0.googlepages.com/spaceinvaders, I get errors
    > - why?


    main.c should #include "setup.h". The other files compile fine for me.

    What errors do you get, what compiler are you using, and how are you
    running it? There might be something wrong in that process.
     
    Nate Eldredge, Mar 1, 2009
    #5
  6. Albert

    Ike Naar Guest

    Ike Naar, Mar 1, 2009
    #6
  7. Albert

    Albert Guest

    Nate Eldredge <> wrote:
    > main.c should #include "setup.h".  The other files compile fine for me.


    Added
    #include "setup.h"
    to main.c

    > What errors do you get what compiler are you using, and how are you

    running it? There might be something wrong in that process.
    gcc errchk.c
    /mingw/lib/libmingw32.a(main.o):main.c:(.text+0x104): undefined
    reference to `WinMain@16'
    collect2: ld returned 1 exit status

    gcc main.c
    C:\WINDOWS\TEMP/cceqbaaa.o:main.c:(.text+0x3a): undefined reference to
    `open_file'
    C:\WINDOWS\TEMP/cceqbaaa.o:main.c:(.text+0x48): undefined reference to
    `setup'
    collect2: ld returned 1 exit status

    gcc setup.c
    C:\WINDOWS\TEMP/ccuibaaa.o:setup.c:(.text+0x5b): undefined reference
    to `read_num'
    C:\WINDOWS\TEMP/ccuibaaa.o:setup.c:(.text+0xa2): undefined reference
    to `read_num'
    C:\WINDOWS\TEMP/ccuibaaa.o:setup.c:(.text+0xb4): undefined reference
    to `read_num'
    /mingw/lib/libmingw32.a(main.o):main.c:(.text+0x104): undefined
    reference to `WinMain@16'
    collect2: ld returned 1 exit status
     
    Albert, Mar 1, 2009
    #7
  8. Albert <> writes:

    > Nate Eldredge <> wrote:
    >> main.c should #include "setup.h".  The other files compile fine for me.

    >
    > Added
    > #include "setup.h"
    > to main.c
    >
    >> What errors do you get what compiler are you using, and how are you

    > running it? There might be something wrong in that process.
    > gcc errchk.c
    > /mingw/lib/libmingw32.a(main.o):main.c:(.text+0x104): undefined
    > reference to `WinMain@16'
    > collect2: ld returned 1 exit status


    Running `gcc' on a file without other arguments tries to compile that
    file into its own program. None of those files constitutes a complete
    program by itself, which is why this doesn't work.

    Try

    gcc -o myprog.exe errchk.c main.c setup.c
     
    Nate Eldredge, Mar 1, 2009
    #8
  9. Albert

    Ike Naar Guest

    In article <>,
    Albert <> wrote:
    >gcc errchk.c
    >/mingw/lib/libmingw32.a(main.o):main.c:(.text+0x104): undefined
    >reference to `WinMain@16'
    >collect2: ld returned 1 exit status
    >
    >gcc main.c
    >C:\WINDOWS\TEMP/cceqbaaa.o:main.c:(.text+0x3a): undefined reference to
    >`open_file'
    >C:\WINDOWS\TEMP/cceqbaaa.o:main.c:(.text+0x48): undefined reference to
    >`setup'
    >collect2: ld returned 1 exit status
    >
    >gcc setup.c
    >C:\WINDOWS\TEMP/ccuibaaa.o:setup.c:(.text+0x5b): undefined reference
    >to `read_num'
    >C:\WINDOWS\TEMP/ccuibaaa.o:setup.c:(.text+0xa2): undefined reference
    >to `read_num'
    >C:\WINDOWS\TEMP/ccuibaaa.o:setup.c:(.text+0xb4): undefined reference
    >to `read_num'
    >/mingw/lib/libmingw32.a(main.o):main.c:(.text+0x104): undefined
    >reference to `WinMain@16'
    >collect2: ld returned 1 exit status


    Try this:
    gcc main.c errchk.c setup.c
     
    Ike Naar, Mar 1, 2009
    #9
  10. Albert

    Albert Guest

    Nate Eldredge wrote:
    > Try
    >
    > gcc -o myprog.exe errchk.c main.c setup.c


    I just did. Your suggestion worked. Thank you. :)
     
    Albert, Mar 1, 2009
    #10
  11. Albert

    Albert Guest

    Now I need a
    struct mship ms[MAXMSHIPS+1] that setup() and main() can access
    instead of a local array that only setup() manipulates. How do I get
    the external declarations and definitions right?
     
    Albert, Mar 1, 2009
    #11
  12. On Sun, 1 Mar 2009 12:47:53 -0800 (PST), Albert
    <> wrote:

    >Now I need a
    >struct mship ms[MAXMSHIPS+1] that setup() and main() can access
    >instead of a local array that only setup() manipulates. How do I get
    >the external declarations and definitions right?


    No external declarations needed. Define ms in main and pass it as an
    argument to setup. If main and setup are in different translation
    units, define struct mship in a header and #include that header in
    both source files.

    --
    Remove del for email
     
    Barry Schwarz, Mar 2, 2009
    #12
  13. Albert

    Albert Guest

    Barry Schwarz wrote:
    > Define ms in main and pass it as an argument to setup.


    I've now done that.
    In the first for loop in setup.c, will ms.left = INT_MAX;
    become (ms+i)->left = INT_MAX?

    Thanks
    Albert
     
    Albert, Mar 3, 2009
    #13
  14. Albert <> writes:

    > Barry Schwarz wrote:
    >> Define ms in main and pass it as an argument to setup.

    >
    > I've now done that.
    > In the first for loop in setup.c, will ms.left = INT_MAX;
    > become (ms+i)->left = INT_MAX?


    No need. I'd use the first form always.

    --
    Ben.
     
    Ben Bacarisse, Mar 3, 2009
    #14
  15. Albert

    Albert Guest

    Ben Bacarisse wrote:
    > Albert <> writes:
    > > In the first for loop in setup.c, will ms.left = INT_MAX;
    > > become (ms+i)->left = INT_MAX?

    >
    > No need.  I'd use the first form always.


    Is it the same???
     
    Albert, Mar 4, 2009
    #15
  16. On Mon, 2 Mar 2009 23:21:23 -0800 (PST), Albert
    <> wrote:

    >Barry Schwarz wrote:
    >> Define ms in main and pass it as an argument to setup.

    >
    >I've now done that.
    >In the first for loop in setup.c, will ms.left = INT_MAX;
    >become (ms+i)->left = INT_MAX?


    Without any context (most of aren't going to bother remembering the
    details of your post from days ago), the answer is who knows.

    ms is defined to be *(ms+i) but simply substituting one for the
    other runs afoul of precedence and associativity. The compiler is
    smart to figure it out so that the expression ms.left will be
    evaluated as (*(ms+i)).left. I think this is equivalent to your
    expression (ms+i)->left. Whether the generated code tries to do it
    this way is an implementation detail.

    --
    Remove del for email
     
    Barry Schwarz, Mar 4, 2009
    #16
  17. Albert <> writes:

    > Ben Bacarisse wrote:
    >> Albert <> writes:
    >> > In the first for loop in setup.c, will ms.left = INT_MAX;
    >> > become (ms+i)->left = INT_MAX?

    >>
    >> No need.  I'd use the first form always.

    >
    > Is it the same???


    Why don't you tell me what you think each one means. I find a diagram
    helps, but drawing in Usenet posts is a pain.

    --
    Ben.
     
    Ben Bacarisse, Mar 4, 2009
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. richard

    Re: qsort and structs and ptrs

    richard, Aug 14, 2003, in forum: C Programming
    Replies:
    0
    Views:
    390
    richard
    Aug 14, 2003
  2. richard

    crashing qsort

    richard, Aug 14, 2003, in forum: C Programming
    Replies:
    34
    Views:
    1,344
  3. tweak
    Replies:
    14
    Views:
    2,788
    Eric Sosman
    Jun 11, 2004
  4. Alfonso Morra
    Replies:
    11
    Views:
    721
    Emmanuel Delahaye
    Sep 24, 2005
  5. Replies:
    6
    Views:
    741
Loading...

Share This Page