Printable View
Use Quick Sort.
------------------
//SyS Specs//
AMD T-Bird 1.333GHz
256 mb DDR RAM (Micron)
Iwill KA266 MoBo
40GB Maxtor ATA100 7200RPM
LeadTek GeForce 2 PRO 64mb w/TV OUT
19" Sylvania Monitor
Intelli Mouse Optical(Explorer sux)
^^^^^^^^^^^^^^^^^^^^^
This system is the best
in this thread!
*****Quote:
Originally posted by Snakex:
I was wondering how you would be able to sort over 1 million numbers all random. They are all in 1 file and have to be made into another file. This is using C++.
I cant use an array because an array of 100,000,000 would be just oo big so would a linked list. Somehow I was thinking about sorting 1000 at a time then sorting those over and over again like the mergesort but im not sure.
any help?
Bryan
perhaps with a Shell sort, or modified Shell sort??
heres what I did, it took the use of 3 temp files.
Take 2 batches of 10000 numbers from the big file then sort those in an array then place them in temp1.num and temp2.num. Then merge temp1.num and temp2.num to temp3.num and then get 10000 more numbers in temp1.num sorted. Now merge temp1.num and temp3.num into temp2.num and keep doing that untill all the numbers are sorted
------------------
"Just remember the shark
that bit you is the one
gets to have a head full
of lead later on"
I suspect that if you look at the number of page accesses for a "dumb" quicksort and this file-based mergesort, you're going to get very similar numbers.Quote:
Originally posted by EdtheROM:
The underlying disk/file structure hasn't changed much, so the hint to use multiples of the cluster size is a good one.
Just why would you think that virtual memory would obviate this??
I'm interested...
-ed-
The analysis of the spatial locality of the accesses will prove educational:
For quicksort, at every level, you're basically going to have to load in every page.
Your operating system will basically keep the location of the "less" and the "Greater" array in memory, forcing a page miss once per level for them, and then a page miss for every page of the array.
When you subdivide, you repeatedly access pages for each half.
So, approximately nlogn page misses total(on a good day) and near n^2 on a bad(where n in this case is number of pages of memory worth of numbers).
For mergesort, first we have the cost of splitting everything up into files. This is the cost of loading the array into memory, and writing it all back out to disk(approx n page misses per level, log n levels).
Then we're looking at a bottom level of 1 page miss per page.
Now we have files of size cluster*2.
going through it again, there are n/2 files, but still n pages worth of numbers.
So again, n page misses.
This continues until mergesort finishes:
n log n page misses.
As far as i can tell, both methods incur roughly the same number of page misses.
With pathologically bad input, sure, quicksort will have n^2 page faults.
The likely scenario is that both will have roughly similar disk access needs, with one caveat. Mergesort is not in-place. THerefore, You not only have the overhead of splitting the array into files in the first place, you also have to put it back together.
Now, conventionally, memory accesses are cheap and don't count. When we're not dealing with primary memory, however, they get real expensive, real fast.
That's why i think that this mergesort is a big loser in this case: you're going to have to go to disk roughly twice as much.
Use a Hash Function. This doesn't sort the items at all, but uses pointers. That way when you need to insert/delete a new item into the list, you don't have to move the items. So, the first time around may be a little slower, but subsequent performance will be much faster.Quote:
Originally posted by Snakex:
I was wondering how you would be able to sort over 1 million numbers all random. They are all in 1 file and have to be made into another file. This is using C++.
I cant use an array because an array of 100,000,000 would be just oo big so would a linked list...
------------------
zBoss
I thought we talked about this, using pointers is very expensive in this case. Not a good soln'.Quote:
Originally posted by zboss:
Use a Hash Function. This doesn't sort the items at all, but uses pointers. That way when you need to insert/delete a new item into the list, you don't have to move the items. So, the first time around may be a little slower, but subsequent performance will be much faster.
------------------
DHAHL3seasons GP:73 G:121 A:55 Pts:176 GWG:12 +/-:184
UWSWA1season GP:9 G:12 A:8 Pts:20 GWG:3 +/-:-3
uwcdc.com or namgor.com
*****Quote:
Originally posted by sjelkjd:
I suspect that if you look at the number of page accesses for a "dumb" quicksort andQuote:
Originally posted by EdtheROM:
The underlying disk/file structure hasn't changed much, so the hint to use multiples of the cluster size is a good one.
Just why would you think that virtual memory would obviate this??
I'm interested...
-ed-
*********
*********
*********
That's why i think that this mergesort is a big loser in this case: you're going to have to go to disk roughly twice as much.
given all of this, have you ever considered Singleton's sort??
-ed-
Actually, i've never heard of Singleton's sort.Quote:
Originally posted by EdtheROM:
*****
given all of this, have you ever considered Singleton's sort??
-ed-
Could you describe the algorithm?