Selecting pivot in sorted array.

[infantheartlyje]

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.

[MK27]

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?

[laserlight]

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]

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.

[CommonTater]

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.