This week's book giveaway is in the Android forum.
We're giving away four copies of Head First Android and have David & Dawn Griffiths on-line!
See this thread for details.
Win a copy of Head First Android this week in the Android forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Rob Spoor
  • Bear Bibeault
Saloon Keepers:
  • Jesse Silverman
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Al Hobbs
  • salvin francis

Sorting an array of integers

 
Ranch Hand
Posts: 34
3
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello. I've given myself a task to come up with a way to sort an array of integers. It seems to be working fine but I would love to hear some feedback on it from you guys.

The solution works in the following way :
The nested loop compares each value of the array to every other value of the array.  It skips the comparison between values of the same index. There is a counter declared at the beginning of the nested loop which will increase every time a value being compared is found to be either smaller or equal to the other value.The value of the counter is then used to determine a relative position of the tested value and the value is assigned to an appriopriate index position to the newly created array. So, for example, if after all the comparisons the counter remains 0, then we know that the value being tested is the biggest one and it goes at the last index position of the newly created array.

Aside of a sorting method, there is also a printer method for testing purposes. It prints all the values of the arrays after the sorting is done. Other than that the methods can't handle exceptions and printer() could print the data in a nicer way but I think it would be best to try getting some feedback before putting more work into it.

Here is the code :


 
Saloon Keeper
Posts: 8740
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It would be interesting to see some performance numbers for very large arrays comparing your method to a simple bubble sort.
Your method has these nested loops
A bubble sort has these
Note the inner loop gets shorter and shorter as the outer loop progresses.

 
Sheriff
Posts: 16657
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Instead of writing your own printer() method, you could just use java.util.Arrays.toString() to display an int[]. To display nested arrays, you can use Arrays.deepToString()
 
Dawid Smith
Ranch Hand
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:It would be interesting to see some performance numbers for very large arrays comparing your method to a simple bubble sort.
Your method has these nested loops
A bubble sort has these
Note the inner loop gets shorter and shorter as the outer loop progresses.



How would you go about comparing performances of 2 methods?
 
Dawid Smith
Ranch Hand
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:Instead of writing your own printer() method, you could just use java.util.Arrays.toString() to display an int[]. To display nested arrays, you can use Arrays.deepToString()



Thank you for the suggestion. I didn't know that such methods exist. Still, what do you think about writing your own version just for practice? I imagine it seems supereasy for someone experienced but I had to think how to print those results
 
Junilu Lacar
Sheriff
Posts: 16657
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If it's your first try, then it's a pretty good try. This algorithm, however, is quite inefficient. If I'm not mistaken, it is best case and worst case O(n²) which means that for large arrays, it takes a very long time, even if it's already sorted. You're basically looking through the entire list NxN times to find the largest unsorted element, including the elements that you've already looked at before and determined to be larger than all others.

Sorting algorithms are a basic area of study in computer science so I suggest you take a look at the various ones already existing and commonly used and compare them with yours to see what kind of improvements you might make.
 
Junilu Lacar
Sheriff
Posts: 16657
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dawid Smith wrote:I didn't know that such methods exist. Still, what do you think about writing your own version just for practice? I imagine it seems supereasy for someone experienced but I had to think how to print those results


It's good for practice. Once you know the mechanics of it though, you'll probably rather have something that's already been tried and tested. Kind of like how it might be fun to build your own bicycle from scratch but if you've already done it once and you just want to ride a bike, then I'd rather just go and buy one that's already pre-assembled. I've done that (assembled my own bike). Once.
 
Carey Brown
Saloon Keeper
Posts: 8740
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's some boiler plate, just do the same for your method. You'll have to play with the size you pass in to createRandomArray() to get an elapsed time from 1-4 minutes. Milliseconds should be sufficient granularity for this. No need to go with nano-time, but you could if you wanted to look into it.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dawid Smith wrote:Still, what do you think about writing your own version just for practice?


Nothing wrong with it at all; just don't expect too much in the way of enlightenment unless you repeat the process at least 10,000 times, or work with arrays involving millions of objects, which probably isn't very practical.

Java does things very quickly indeed, so the difference between one instruction (or technique) and another might be measured in picoseconds (thats 10⁻¹²), and since the best Java time counter (System.nanotime()) is good to about 1/100th of a second, if you're lucky, you're unlikely to get any meaningful information unless you're running your comparisons on very large samples.

I'm with Junilu - right now, you might get more mileage out of looking at sorting algorithms and working out why you might use them; but don't ignore the simple ones simply because they're supposedly "inefficient" (O(n²) or worse).

The technique you're using, for example, is very similar to a Selection sort, which is still used to sort small datasets ... although Insertion sort is usually quicker.

And in trawling Wikipedia, I was also reminded of Cycle sort, which is basically a "write-optimized" Insertion sort.
All these sorts are supposedly "slow", but they all have their uses, especially in hybrid algorithms that combine them with other, theoretically faster techniques, like Quicksort.

Hope it helps.

Winston
 
Marshal
Posts: 8107
571
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@OP

Very nicely indented and formatted code. Have a cow for disciplined approach on that.
 
Marshal
Posts: 74371
334
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Once you have passed all your exams and got a job, you will sort your array like this
 
Dawid Smith
Ranch Hand
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:If it's your first try, then it's a pretty good try. This algorithm, however, is quite inefficient. If I'm not mistaken, it is best case and worst case O(n²) which means that for large arrays, it takes a very long time, even if it's already sorted. You're basically looking through the entire list NxN times to find the largest unsorted element, including the elements that you've already looked at before and determined to be larger than all others.

Sorting algorithms are a basic area of study in computer science so I suggest you take a look at the various ones already existing and commonly used and compare them with yours to see what kind of improvements you might make.



Now I can see the efficiancy problem with my method. Not that I expected it to be anywhere close in terms of performance to already existing solutions. Thank you
 
Dawid Smith
Ranch Hand
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Dawid Smith wrote:Still, what do you think about writing your own version just for practice?


Nothing wrong with it at all; just don't expect too much in the way of enlightenment unless you repeat the process at least 10,000 times, or work with arrays involving millions of objects, which probably isn't very practical.



I am not sure if I understand your point. Do you mean that getting better by writing your own code takes crazy amount of time?

Winston Gutkowski wrote:I'm with Junilu - right now, you might get more mileage out of looking at sorting algorithms and working out why you might use them; but don't ignore the simple ones simply because they're supposedly "inefficient" (O(n²) or worse).



Thank you for the advice. Right now, my studying is heavily skewed towards writing my own stuff instead of looking up what's already out there. Maybe that's a mistake.
 
Junilu Lacar
Sheriff
Posts: 16657
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dawid Smith wrote:Right now, my studying is heavily skewed towards writing my own stuff instead of looking up what's already out there. Maybe that's a mistake.


Practice by writing code on your own. Expand your horizons and learn from others by studying how they solved the same problem.
 
Dawid Smith
Ranch Hand
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:@OP

Very nicely indented and formatted code. Have a cow for disciplined approach on that.



Thank you. I am trying to make it easy to read.

Campbell Ritchie wrote:Once you have passed all your exams and got a job, you will sort your array like this



But.. where would the fun be in that?

I get your point though, there are ready-made solutions for common problems.
 
Campbell Ritchie
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dawid Smith wrote:. . . But.. where would the fun be in that? . . .

A $40,000 starting salary?
 
Dawid Smith
Ranch Hand
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Dawid Smith wrote:. . . But.. where would the fun be in that? . . .

A $40,000 starting salary?



Oh, that Still, there is so much to learn I haven't even started thinking about salaries yet
 
Campbell Ritchie
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You are only allowed to start thinking about starting salaries; don' start thinking about non‑starting salaries or you will have a start.
 
Bartender
Posts: 4681
183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Once you have passed all your exams and got a job, you will sort your array like this


I bet not. What about sorting in descending order?
 
Campbell Ritchie
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Damn! It hasn't got that method. Piet has beaten me.
 
Carey Brown
Saloon Keeper
Posts: 8740
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A side topic here would be how to benchmark your program. It seems like sorting might be as good a place as any to compare benchmarks from various techniques. I would be interested to know how the streaming version compares to the Arrays.sort version, for instance.
 
Ranch Hand
Posts: 91
Eclipse IDE Debian Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There is an optimized bubble sort. More efficient.

Here is the link.   webpage

 
Dawid Smith
Ranch Hand
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:A side topic here would be how to benchmark your program. It seems like sorting might be as good a place as any to compare benchmarks from various techniques. I would be interested to know how the streaming version compares to the Arrays.sort version, for instance.



I am getting myself familiar with some of the well-known algorithms that Ranch Members pointed out to me. I will try to do some comparisons later on. Hopefully I can manage to do that
 
Campbell Ritchie
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Dawid Smith wrote:. . . some of the well-known algorithms . . .

Try here to see what the algorithms look like animated. I can't remember whether they provide details of the algorithm on that site, too, but you can always search Wikipedia or similar.
 
Dawid Smith
Ranch Hand
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mark Ii wrote:There is an optimized bubble sort. More efficient.

Here is the link.   webpage

[/code]



Thank you for the link. Afaik, bubble sort is the simplest one so it would be a good place to start.

Campbell Ritchie wrote:

Dawid Smith wrote:. . . some of the well-known algorithms . . .

Try here to see what the algorithms look like animated. I can't remember whether they provide details of the algorithm on that site, too, but you can always search Wikipedia or similar.



Thanks for the suggestion. Graphic representation is certainly something new to me.
 
Campbell Ritchie
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why don't you try benchmarking. It needs arrays/collections of various sizes because different algorithms perform differently with different amounts to sort.
 
Carey Brown
Saloon Keeper
Posts: 8740
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
When you benchmark you often need to loop through a large number of method calls in order to accumulate enough milliseconds. Then divide the time by the number of iterations. Note that if you have a method, e.g. 'sort()', that modifies the data in place, then you'd need to reset the array prior to each call. For sort(), the algorithm efficiency depends on the initial state of the array, e.g.: a) an array that's already sorted, b) an array that's already sorted and then moving the least value to the end, c) an array presorted in reverse order, d) random numbers, e) small range of random numbers with lots of duplicates.
 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,
There are many ways to sort an Array in Java. I have written below program for sorting an Array.



There are many other ways through which you can Sort Array
 
Campbell Ritchie
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ashish Chandra Gupta wrote:. . . Sort Array

Kindly don't simply promote that tutorial, which I presume you have written yourself.The link doesn't actually add anything new.
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic