Zip Code Sorting

This is a discussion on Zip Code Sorting within the C++ Programming forums, part of the General Programming Boards category; Say you're in a warehouse, one like FedEX Ground, I guess it's a warehouse, anyways, your task is to sort ...

  1. #1
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964

    Zip Code Sorting

    Say you're in a warehouse, one like FedEX Ground, I guess it's a warehouse, anyways, your task is to sort boxes into one of three belts depending on what the zip code is. Say you are kind of slow to learn how to do this in your head without looking at a sorting chart. You would need a program, or flash cards if you were stuck in the 50's.

    I'm thinking I could start with a linked list, and maybe a little fstream magic and binary code and whatnot save the sorting chart to a file, that my little program could read, and then create a linked lisk subsequently and of course rearrange it and such. I could have the zips pop up and you could enter 1, 2, or 3 depending on which belt they go onto. This way you could learn how to be a better sorter at work.

    I'm kindof just getting back into C++ after a bit of time with no computer/internet. Should I bother making a linked list or should I just use some kind of standard container?

    How would you connect the zip code variable with said belt variable?
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  2. #2
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    I would recommend a STL container for many reasons. Specifically, for your implementation, you could just make a single function call to find your zip code. You also get other neat stuff like the use of 'iterators.'

    Here is a good description of STL containers. I tells you which type is the best to use for certain situations. STL Containers - C++ Reference

    I just did some reasearch whilst at the aforementioned URL, and in my opinion would recomend the vector class:

    Vector
    Vectors are a kind of sequence containers. As such, their elements are ordered following a strict linear sequence.

    Vector containers are implemented as dynamic arrays; Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.

    But unlike regular arrays, storage in vectors is handled automatically, allowing it to be expanded and contracted as needed.

    Vectors are good at:

    * Accessing individual elements by their position index (constant time).
    * Iterating over the elements in any order (linear time).
    * Add and remove elements from its end (constant amortized time).


    Compared to the other base standard sequence containers (deques and lists), vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  3. #3
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    "but also using offsets on regular pointers to elements."

    This sounds easy, seeming like I could have a "vector" full of "Zip Code" data structures, and all the zip codes would know their proper belt location.

    Sounds like I'm cramming too much data into a "Zip Code" structure. I think, why should a zip code know what belt it needs to be sorted onto? Something should tell the zip code where it goes, not the other way around. What would that something be hmmmm. Some sort of database?
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  4. #4
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    A data structure you may also be interested in is a 'binary tree.' A binary tree is essentially linked list that points to 2 nodes instead of one.

    A major advantage of binary trees is the ability to search and find information wicked fast.

    A major disadvantage is that you will have to implement all your own binary tree class that will consist of function(s) of your own design. Most binary tree classes contain the usual 'node insert', 'node removal' and 'find' functions.

    More on the tress of binaryness: Eternally Confuzzled - Binary Search Trees I
    Last edited by The Brain; 10-23-2009 at 08:35 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  5. #5
    Registered User
    Join Date
    Nov 2007
    Posts
    46
    I don't know how many Zip codes you have, but since you're sorting them by "belts", why not skip the idea of having a "Zip structure" all together and do the following:

    You could have a map ( C++ Maps [C++ Reference] ) of sets ( C++ Sets [C++ Reference] ), where you would use the map to map a belt value to a set of Zip codes?

    That way you load all your zip codes in to this map of sets, and you can then use it for looking up a belt and see if a zip code is found for a given belt.

  6. #6
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    I'm working with hundreds of zip codes by the way. Perhaps thousands? Anywhere in the northeastern united states.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  7. #7
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    Oh and belt is just referring to which like, belt you put the box on to go through the rest of the automated sorting process.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  8. #8
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    One more consideration:

    Perhaps there is a possible numerical relationship you could exploit among the set of numbers we know as zip codes..

    For example, I know that many of the zip codes in the state of virginia start with '2'... perhaps it is possible to prove that all (or many) of zip codes starting with the number '2' could be grouped in the appropriate belt associated with the 'east coast.'

    Just something to consider.. there may or may not be any merit to this.. but seeing that zip codes are part of a well known standardized system, perhaps there is (by purpose) some relationship among zip codes. If so, you could assign the proper belt per package based on a simple test of the zip code rather than having to reference some sort of database.
    Last edited by The Brain; 10-23-2009 at 09:20 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  9. #9
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    Yeah, I don't feel like doing a database.

    I like that idea Brain, but what are we going to do tomorrow?
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  10. #10
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    Tomorrow, we do the same thing we do everyday.. try to take over the world.
    Last edited by The Brain; 10-24-2009 at 08:41 AM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  11. #11
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    Alright, so I just got the split chart, unfortunately there is no special order, or easy deduction of which zip code goes on what belt, it looks like the system was made by a package handler.

    The zip codes range from 00 all the way up to 99.

    I'm seeing that the only good way to accomplish this virtual split chart is to actually punch in a database via text file or something similar.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  12. #12
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    Quote Originally Posted by JacobN View Post
    I don't know how many Zip codes you have, but since you're sorting them by "belts", why not skip the idea of having a "Zip structure" all together and do the following:

    You could have a map ( C++ Maps [C++ Reference] ) of sets ( C++ Sets [C++ Reference] ), where you would use the map to map a belt value to a set of Zip codes?

    That way you load all your zip codes in to this map of sets, and you can then use it for looking up a belt and see if a zip code is found for a given belt.
    I've used maps before, but could I really connect like 100 or more zip codes to a single element of a map? Would that be efficient?
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  13. #13
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    I suppose I could have a belt structure, or rather a vector full of zip codes and connect that vector to one of the belt elements of the map.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  14. #14
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    Quote Originally Posted by Shamino View Post
    I suppose I could have a belt structure, or rather a vector full of zip codes and connect that vector to one of the belt elements of the map.
    I don't live in the US, but I would have to say that if the system used to assign zip codes was pretty much just a random number generator that checks previously used numbers, it'd be really stupid and bad for management.

    Are you sure you can't simply parse parts of the zipcode, and from there, parse the rest?
    It wouldn't surprise me if zipcodes were constructed in a similar manner to the following example.

    112233

    11 = state
    22 = city
    33 = certain area in city

    Obviously, they'd have to be longer for huge areas, but you get the drift.

    This, however, does not make it much easier to ascertain the exact area. You would have to have a database for doing that properly.

    Take a look at this page: ZIP code - Wikipedia, the free encyclopedia

    It seems like it might be what you need.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  15. #15
    Registered User
    Join Date
    Nov 2007
    Posts
    46
    Quote Originally Posted by Shamino View Post
    I've used maps before, but could I really connect like 100 or more zip codes to a single element of a map? Would that be efficient?
    I don't see why not? If you just make sure that if you pass this map of sets to functions by reference instead of value there shouldn't be a problem? As for whether it's the most efficient way to figure out if a ZIP code belongs to a band, I don't know, it was just the first idea that came to mind.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Proposal: Code colouring
    By Perspective in forum A Brief History of Cprogramming.com
    Replies: 28
    Last Post: 05-14-2007, 08:23 AM
  2. Values changing without reason?
    By subtled in forum C Programming
    Replies: 2
    Last Post: 04-19-2007, 11:20 AM
  3. Updated sound engine code
    By VirtualAce in forum Game Programming
    Replies: 8
    Last Post: 11-18-2004, 12:38 PM
  4. True ASM vs. Fake ASM ????
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 04-02-2003, 04:28 AM
  5. Replies: 4
    Last Post: 01-16-2002, 12:04 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21