Like Tree1Likes
  • 1 Post By laserlight

Selecting pivot in sorted array.

This is a discussion on Selecting pivot in sorted array. within the General Discussions forums, part of the Community Boards category; Hi folks, I'm having 200,000 records those are sorted by date. Now i want to insert one back dated record ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Location
    India
    Posts
    53

    Selecting pivot in sorted array.

    Hi folks,
    I'm having 200,000 records those are sorted by date. Now i want to insert one back dated record as order. If i using quick sort to insert back dated record inside the file, How to select pivot element ?

    for e.g. my records are like this.
    0
    1
    2
    4
    5
    3

    How can i sort this using quick sort? How to select pivot element?

    I'm using random structure access method in c. The records are stored sequentially in files. I'll store my daily transactions in that tile. If i got any back dated transaction, at that time i need to sort my file.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by infantheartlyje View Post
    Hi folks,
    I'm having 200,000 records those are sorted by date. Now i want to insert one back dated record as order. If i using quick sort to insert back dated record inside the file
    That's crazy -- or I misunderstand you. Are you saying you want to insert a single item randomly into an already sorted list, then re-sort it to get the item into the proper place? Don't do that. If the list is sorted, just walk the list and find the proper place.

    Quicksort works best on lists where the distribution is truly random. One of the cases where it fares poorly is a mostly sorted list. If that is the generally the situation, use mergesort instead.

    But again, don't use a sort to insert a new item into a sorted list. Using quicksort here will give you quicksort's worst case -- O(n^2). Mergesort is stable, so you will have O(n log n). But simply walking the list is at worst O(n), and on average should be O(n/2). If the list is less than 10 items, mergesort will perform better than that worst case, but it will never perform better than the average.

    Ie, by writing a sort, you will be wasting time and adding complexity in order to create greater inefficiency. Does that make sense?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,636
    Quote Originally Posted by MK27
    But again, don't use a sort to insert a new item into a sorted list. Using quicksort here will give you quicksort's worst case -- O(n^2). Mergesort is stable, so you will have O(n log n). But simply walking the list is at worst O(n), and on average should be O(n/2). If the list is less than 10 items, mergesort will perform better than that worst case, but it will never perform better than the average.
    Heh, I find it likely that insertion sort would be better than merge sort for this. Besides it literally does the "just walk the list and find the proper place" thing
    MK27 likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    Heh, I find it likely that insertion sort would be better than merge sort for this. Besides it literally does the "just walk the list and find the proper place" thing
    Yeah, I presume all reasonable people order data as it is read in (eg, from disk) using what is called "insertion sort". OTOH, I wouldn't call that a sort at all -- you are not sorting all the data, you are working on the premise that it is already in order. It is just an insertion, not a real sort.

    Looking at the OP again, it seems the issue is that the records are already mostly in order on disk, and infantheartlyje is suggesting they first be read in and then sorted, which is not efficient. However, if there is no other option than to first build the list then sort it, I would use mergesort instead of either quick or insertion because:

    - quicksort is hamstrung by mostly sorted lists, and no form of pivot selection will save it.

    - both mergesort and insertion sort are 0(n) on a sorted list, and as the list diverges from that, mergesort will do better.
    Last edited by MK27; 10-14-2011 at 09:30 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by infantheartlyje View Post
    Hi folks,
    I'm having 200,000 records those are sorted by date. Now i want to insert one back dated record as order. If i using quick sort to insert back dated record inside the file, How to select pivot element ?

    for e.g. my records are like this.
    0
    1
    2
    4
    5
    3

    How can i sort this using quick sort? How to select pivot element?

    I'm using random structure access method in c. The records are stored sequentially in files. I'll store my daily transactions in that tile. If i got any back dated transaction, at that time i need to sort my file.
    We already discussed this in C Programming... and I repeatedly told you the most efficient way of doing this with a records based random access file is to use a copy-insert algorythm... This is not a complex methodology, however I fear that after a dozen tries at explaining it to you, the concept still escapes you...

    1) examine the date of new records agains the last item in your main file...
    2) if the new date is older than the last record, write it to a temporary file.
    3) if the new date is newer, tack it onto the end of your main file (no sorting needed)

    4) once you have several out of order records ( a couple of dozen or so)
    5) open your temporary file, load the entire thing into memory and sort it (selection sort works well enough)
    6) now open your main file at record 0
    7) set the pointers for your in-memory temp file to it's record 0
    8) check the dates ...
    9) if the memory file is older, write it's record to disk and increment your pointer
    10) if the main file is older, write it's record to disk and increment the record number
    11) loop back to step 8 until all temporary records are written
    12) finish copying your main file to the new file
    13) close your main file
    14) Delete your main file
    15) rename the new file to the name of your main file.
    16) Wait till you have a bunch more out of date records and loop to step 5


    Really this is very fast and not terribly complex. In fact, with proper modularity in your code, it can be written in about 50 lines.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how delete 1th element of a sorted array
    By vicky_4040 in forum C Programming
    Replies: 4
    Last Post: 10-11-2009, 06:12 AM
  2. finding max/min in a sorted array
    By Crcullen3916 in forum C++ Programming
    Replies: 9
    Last Post: 09-23-2008, 02:18 AM
  3. Pivot Stickman bitmaps
    By Asbo in forum Game Programming
    Replies: 1
    Last Post: 01-14-2007, 12:56 AM
  4. selecting an array
    By ekarapanos in forum C Programming
    Replies: 6
    Last Post: 07-05-2003, 08:22 AM
  5. A simple question about selecting elements in an array
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 08-30-2001, 10:37 PM

Tags for this Thread


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