Results 1 to 7 of 7
  1. #1
    ItchyJuffoWup is offline Member
    Join Date
    Nov 2014
    Posts
    11
    Rep Power
    0

    Default 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 09:13 PM.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default 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
    Build a wall around Donald Trump; I'll pay for it.

  3. #3
    ItchyJuffoWup is offline Member
    Join Date
    Nov 2014
    Posts
    11
    Rep Power
    0

    Default 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. #4
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default 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
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  5. #5
    ItchyJuffoWup is offline Member
    Join Date
    Nov 2014
    Posts
    11
    Rep Power
    0

    Default Re: Fastest way to sort an Array

    Quote Originally Posted by jim829 View Post
    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. #6
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Fastest way to sort an Array

    Quote Originally Posted by ItchyJuffoWup View Post
    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
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default 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
    Build a wall around Donald Trump; I'll pay for it.

Similar Threads

  1. Need help with Array.sort()
    By Kinney.j in forum New To Java
    Replies: 1
    Last Post: 10-16-2011, 07:51 AM
  2. sort array >> need help
    By hongi in forum New To Java
    Replies: 4
    Last Post: 04-25-2010, 10:37 PM
  3. Need help. Array sort
    By buzz1500 in forum New To Java
    Replies: 3
    Last Post: 11-07-2008, 05:24 AM
  4. Array sort
    By Jeremy720 in forum New To Java
    Replies: 2
    Last Post: 10-08-2008, 12:41 AM
  5. How to sort an array
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-14-2008, 09:48 PM

Posting Permissions

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