Results 1 to 5 of 5
Thread: Data Sorting Questions
 10072011, 02:46 AM #1Member
 Join Date
 Oct 2011
 Posts
 2
 Rep Power
 0
Data Sorting Questions
I'm working with list of 100k Doubles with 8 digits to the right of the decimal point. All the numbers are between 0 and 1. My goal is to sort them as quickly as possible. I'm using a modified version of quicksort with insertion sort once the data is sorted to within blocks of 300. I thought I was doing well until I saw other people accomplishing the same task in under 10% of the time it's taking me. Even a standard mergesort (Arrays.sort()) is working somewhere near my time. I just don't see how I'm getting so dominated. Does anyone have any ideas for how to improve my sorting process?
 10072011, 04:35 AM #2Moderator
 Join Date
 Jul 2010
 Location
 California
 Posts
 1,638
 Rep Power
 12
Re: Data Sorting Questions
Does anyone have any ideas for how to improve my sorting process?
Even a standard mergesort (Arrays.sort()) is working somewhere near my time
 10072011, 05:53 AM #3
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
Re: Data Sorting Questions
Build a wall around Donald Trump; I'll pay for it.
 10072011, 06:54 PM #4Member
 Join Date
 Oct 2011
 Posts
 2
 Rep Power
 0
Re: Data Sorting Questions
I am writing the sort myself. I guess I assumed Arrays.sort(Double[] a) and Arrays.sort(Object[] a) were the same but after checking the API you're right. One is quicksort and the other is merge sort. I feel like I could sort either as Strings or Doubles. I chose Doubles but I plan to use the same process on strings and see how efficient it is.
Running the sort on 100k number a specified number of times (which I'm not told) my result is around 400 milliseconds. Others accomplishing the same sort with correct outputs are sorting in 3040 milliseconds. My process is an inplace quicksort until blocks are sorted within groups of 300. The quicksort is also using a median of three pivots modification to select a better pivot. Finally I call insertion sort on the entire array at this point since no number can be farther than 300 away from it's correct position. This was the best I could do using a combination of these sorts. I was going to try radix sort but I feel like the high constant here wouldn't make it worth sorting on the order of n. If you can provide any advice, that would be great. I'll give heapsort a try later today.
 10072011, 07:41 PM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
Re: Data Sorting Questions
Read my blog; it describes a heapsort implementation in great detail and has all the code in it (it isn't much). The implementation knows (almost) nothing about what it has to sort; that is left to an interface that has to supply the number of things to be sorted; it has to compare two things and it has to swap two things. If that is too slow for you, you can always optimize the interace out of the code (so it can only sort an array of doubles). The sorting algoritm itself is O(n*log(n)), always, so it is theoretically optimal.
kind regards,
JosLast edited by JosAH; 10072011 at 07:43 PM.
Build a wall around Donald Trump; I'll pay for it.
Similar Threads

sorting a set of data by 2 catagories?
By briangriffin in forum New To JavaReplies: 1Last Post: 10212010, 04:04 AM 
Sorting data
By yrollgayanth in forum Advanced JavaReplies: 7Last Post: 12302009, 06:16 PM 
Sorting data in a Vector
By SBL in forum AWT / SwingReplies: 11Last Post: 11272009, 03:20 AM 
sorting data in txt file
By cassysumandak in forum New To JavaReplies: 1Last Post: 04122009, 03:02 AM 
Data Sorting in a .data file using java
By stutiger99 in forum New To JavaReplies: 2Last Post: 10082008, 02:52 AM
Bookmarks