Need help in sorting

This is a discussion on Need help in sorting within the C++ Programming forums, part of the General Programming Boards category; I have a database in array list and I need to sort them in ascending order based on the frequency ...

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    163

    Need help in sorting

    I have a database in array list and I need to sort them in ascending order based on the frequency of the items, not on lexicographic order.

    E.g. Each row is an array with the items

    1 2 9
    1 2 3 4 5
    1 6 7 8

    will be arranged into

    9 2 1
    3 4 5 2 1
    6 7 8 1

    E.g. in row 1, item 1 is at the last because it has the highest frequency (3), follow by item 2 whose frequency is 2.

    Given that I have a large database, is there any way to efficiency sort them? Thanks for your help!

  2. #2
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    If all your values are low integers less than N (for some value of N), then first make a table of frequencies and have your comparison function look up the frequency on the table.

    If your values aren't integers filling the values up to N, use a hash table of freqencies and do the same.

    If this sorting operation is common, I'd use a different data structure for your database.

  3. #3
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    what data structure will you use?

  4. #4
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    I'd have a table of values by frequencies. The items in the rows in rows would be pointers to these pairs. The table of values with frequencies might be an array; it might be a hash table.

    Any insertion, removal functions, etc, would have to update frequencies. The table might have to be carefully designed so that it can grow (with rehashing) without invalidating all the pointers in the rows in rows, if enough unique values are added.

    This might be unnecessarily complicated for your task.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 02:33 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 03:14 AM
  3. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 06:50 PM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 09:41 PM
  5. selection sorting
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-13-2001, 09:05 PM

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