Results 1 to 7 of 7
Thread: Fastest way to sort an Array
 12082014, 08:58 PM #1Member
 Join Date
 Nov 2014
 Posts
 11
 Rep Power
 0
Fastest way to sort an Array
I will first start off by telling you that this IS for a homework assignment, so i'm not asking you to do the work for me. I have searched here on the forums as well as google ,and it seems to be a huge debate on what the fastest way to sort an array of random integers. My instructor told me to look into an algorithm that uses 2n, but that is all he gave me. I am unable to find anything of the sort (pun intended there) on google, in my text, in my other java books or on here. The only thing that I have come up with are things like mergesort with the exception that the indicies of the Array have to be even. The program that I'm writing takes user input for a minimum to maximum range, the amount of numbers to fill the array in that range, and verbose.
I've tried bubbleSort but it takes forever to sort under the conditions below. I have seen a sorting algorithm that uses n (log n) but didn't really understand how that one worked. If I could get any help here figuring out what this 2n algorithm is, or you can direct me to where I can read about it that would be great.
Using the 2n algorithm, I should be able to test the range from 1  1000 and have it populate an array of of 1,000,000 random integers. It should be able to complete in a matter of miliseconds. I can provide you with what ever other information you might need.
Thanks!Last edited by ItchyJuffoWup; 12082014 at 09:13 PM.
 12082014, 09:13 PM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
Re: Fastest way to sort an Array
If the input data is really unconstrained and really random, you can't do better than O(n*log(n)). Ints on a computer are constrained (limited), so in theory you set up an array of + 4 billion slots and start counting. After you have read all elements, walk over the array and print every non zero element. You have done O(n+n) == O(n) steps. Also read one of my blog articles about sorting. If explains a heap sort algorithm which is O(n*log(n)) and stable w.r.t. the bigOh.
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
 12082014, 09:20 PM #3Member
 Join Date
 Nov 2014
 Posts
 11
 Rep Power
 0
Re: Fastest way to sort an Array
Ok i'll check it out. I have seen the O(n*log(n)) algorithm and it was very confusing lol. There are constraints to the data but they are determined by the user. The user selects a minimum number and a maximum number. That is the range that the random numbers can be pulled from, then the user sets how many random numbers they want in that range. then the array that is created is sorted in ascending order. and the results of the array before sorting and after sorting are printed to the user if they chose to have verbose or not. I am able to get it to work using bubblesort, but it takes way to long using the 11000 range and 1 million numbers. I'll look more into you blog and see if I can work it out myself. I'll post the results here when I am done.
 12082014, 09:26 PM #4Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,226
 Rep Power
 13
Re: Fastest way to sort an Array
Bubble sort is a good method for introducing students to the topic of sorting. However, it is horribly inefficient. I would expect that your teacher is looking for you to find an algorithm that requires about 2n compare/swap operations for a group of n items. That seems extremely efficient to me but I can't point to a sort that meets that criteria. Typically anything on the order of Kn is referred to as O(n) and is expected to have linear efficiency (and is usually not achievable). Bubble sorts are O(n*n). But from my experience, one of the more efficient sorts is the quick sort (even though it has its downside). But sorting is a complex subject and it can also be optimal to understand the nature of the data prior to choosing an algorithm. Did you web search sorting algorithms? I believe Wikipedia should have some reasonable writeups on sorting.
Regards,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 12082014, 09:48 PM #5Member
 Join Date
 Nov 2014
 Posts
 11
 Rep Power
 0
Re: Fastest way to sort an Array
Jim,
Yeah my instructor first showed up Rob sort and told us how horrible that was, then told us about bubble sort and told us that it is great if you are using it in smaller ranges and array entries, it can be fairly effective. I googles searched it asking in different ways. I came across one called Radix sort that seemed like it could meet what I was looking into, then when I looked at the example code I was lost lol. I wasn't able to find anything that used 2n respectively. It always came up with mergesort or the n log n. (unless i'm misinterpreting and those are the same thing). But upon investigating merge sort, it said the indicies of the arrray had to be even. That won't work in my case due to the user being able to choose the number of entries. It seems to me that all the Sorts can be effective and maybe even efficient, but most seem that they have pretty nasty downsides to them. or very specific restrictions.
 12082014, 10:05 PM #6Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,226
 Rep Power
 13
Re: Fastest way to sort an Array
I am not certain what you mean when you ask if they are the same thing. nlog(n) is the order of time (compare operations) that the sort might take. So if you have 100 items. Then 100 * 2 = 200 (which in that case is 2n so that may be what your teacher was talking about). When I said I didn't know of any algorithm for 2n I wasn't thinking as it applied to a constrained number of items.
And I am not certain what you mean about even indices of a merge sort.
Regards,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 12092014, 09:40 AM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
Re: Fastest way to sort an Array
Sort algorithms that need to compare the elements to be sorted, can't do better than O(n*log(n)); for a proof, read these slides: CS 332: Algorithms.
Of course, if the data is constrained or not random,you can play tricks to beat that lower limit.
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
Similar Threads

Need help with Array.sort()
By Kinney.j in forum New To JavaReplies: 1Last Post: 10162011, 07:51 AM 
sort array >> need help
By hongi in forum New To JavaReplies: 4Last Post: 04252010, 10:37 PM 
Need help. Array sort
By buzz1500 in forum New To JavaReplies: 3Last Post: 11072008, 05:24 AM 
Array sort
By Jeremy720 in forum New To JavaReplies: 2Last Post: 10082008, 12:41 AM 
How to sort an array
By Java Tip in forum java.langReplies: 0Last Post: 04142008, 09:48 PM
Bookmarks