-
October 14th, 2011, 02:23 AM
#1
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?
-
October 14th, 2011, 02:46 AM
#2
Re: Selecting pivot in sorted array.
Originally Posted by infantheartlyjes
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.
-
October 14th, 2011, 03:10 AM
#3
Re: Selecting pivot in sorted array.
Originally Posted by nuzzle
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.
-
October 14th, 2011, 03:03 PM
#4
Re: Selecting pivot in sorted array.
Originally Posted by infantheartlyjes
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?
-
October 14th, 2011, 03:54 PM
#5
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|