# Thread: Fastest way to sort an Array

1. Member
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; 12-08-2014 at 08:13 PM.

2. ## 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 big-Oh.

kind regards,

Jos

3. Member
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 1-1000 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.

4. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## 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 write-ups on sorting.

Regards,
Jim

5. Member
Join Date
Nov 2014
Posts
11
Rep Power
0

## Re: Fastest way to sort an Array

Originally Posted by jim829
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 write-ups on sorting.

Regards,
Jim

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.

6. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Fastest way to sort an Array

Originally Posted by ItchyJuffoWup
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.
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,
Jim

7. ## 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,

Jos

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•