How to sort a file fast?

This is a discussion on How to sort a file fast? within the C++ Programming forums, part of the General Programming Boards category; I want to sort a file with records which is bigger than the memory available.The thing is that I want ...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    27

    How to sort a file fast?

    I want to sort a file with records which is bigger than the memory available.The thing is that I want the file to be sorted depending on a field which only can take two values:0 and 1.
    For example the file :

    9423 John Pappas 0
    2342 George Beckham 1
    9423 Mary Lu 0
    7123 Nick Zidane 1
    1234 Ann Adams 1

    should become :

    7123 Nick Zidane 1
    1234 Ann Adams 1
    2342 George Beckham 1
    9423 Mary Lu 0
    9423 John Pappas 0

    not caring about the order of all the records with 1's or all those with 0's in the sorted file.

    Is there a better way than external merge sort that this could be done?Maybe in O(n) time?

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    The only pure sorting algorithm (as far as I know) that runs in O(n) is bucket sort, and that won't work since the keys aren't unique for the items.

    You could however use a modified quick sort that runs in O(n).
    Use two pointers to the items. Place them at both ends.

    Move the left pointer to the right until you find an item with a 1.
    Move the right pointer to the left until you find an item with a 0.
    If the left pointer is to the right of the right pointer, stop.
    Swap the items pointed out by the two pointers.
    Repeat.

    This will cause all 0's to be placed to the left and all 1's to be placed at the right.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    There are no elegant solutions for sorting data in files. One alternative is to use a temporary file and swap data. Another solution is file-mapping.

    Kuphryn

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Formatting a text file...
    By dagorsul in forum C Programming
    Replies: 12
    Last Post: 05-02-2008, 03:53 AM
  2. Formatting the contents of a text file
    By dagorsul in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2008, 12:36 PM
  3. gcc link external library
    By spank in forum C Programming
    Replies: 6
    Last Post: 08-08-2007, 03:44 PM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM

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