Selecting pivot in sorted array.
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Selecting pivot in sorted array.

  1. #1
    Join Date
    Oct 2011
    Posts
    2

    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?

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Selecting pivot in sorted array.

    Quote Originally Posted by infantheartlyjes View Post
    How can i sort this using quick sort? How to select pivot element?
    Why don't you just add the out-of-order element(s) at the end of the file and resort it?

    Quicksort is quite good actually also at almost-ordered sorting.

  3. #3
    Join Date
    Oct 2011
    Posts
    2

    Re: Selecting pivot in sorted array.

    Quote Originally Posted by nuzzle View Post
    Why don't you just add the out-of-order element(s) at the end of the file and resort it?
    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.

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Selecting pivot in sorted array.

    Quote Originally Posted by infantheartlyjes View Post
    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.
    Sorry but I don't understand what you're asking.

    What's your problem?

  5. #5
    Join Date
    Nov 2002
    Location
    California
    Posts
    4,553

    Re: Selecting pivot in sorted array.

    For most quicksort implementations, the pivot is selected arbitrarily. Many implementations select the first element as the pivot, but since that's completely arbitrary, you could just as easily select the middle element.

    Quicksort works best on randomly ordered data, since the recursion on both sides of the pivot is generally equalized with randomly ordered data. Since your data is already sorted (mostly), selection of the middle element would result in a better balance of the recursion, as opposed to selection of the first element.

    However, there is another quirk with quicksort, not widely recognized, which adversely affects performance and speed of sorting (that's what we're talking about here, right?)

    The issue comes up when sorting data whose value is repeated many times between different elements. Examples include sorting on gender (M/F) or state (only 50 of them). Quicksort becomes very slow when sorting elements whose value changes only infrequently.

    So, assuming that your 200,000 records are transactions, sorting on date will perform poorly, since the date is likely to be shared among many transactions.

    The solution is to sort on concatenated fields, where the concatenation will result in many unique values. You might, for example, try sorting on date concatenated with time of day, since the resulting concatenation is likely to yield many unique values. Or you might concatenate a transaction identifier, which is probably a unique number, Or, since quicksort is not robust (i.e., quicksort will not preserve the order of a prior sort), you might concatenate the field used in a prior sort, which will transform quicksort into a robust algorithm.

    Good luck,
    Mike

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center