• 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • paul wheaton
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Ron McLeod
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Tim Holloway
  • Carey Brown
  • salvin francis

Sorting an array of integers

 
Ranch Hand
Posts: 31
3
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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 :


 
Bartender
Posts: 6140
58
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • 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: 13727
228
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • 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: 31
3
  • Mark post as helpful
  • send pies
  • 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: 31
3
  • Mark post as helpful
  • send pies
  • 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: 13727
228
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • 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: 13727
228
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • 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
Bartender
Posts: 6140
58
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • 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: 10777
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • 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: 7084
491
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@OP

Very nicely indented and formatted code. Have a cow for disciplined approach on that.
 
Marshal
Posts: 65465
249
  • Likes 2
  • Mark post as helpful
  • send pies
  • 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: 31
3
  • Mark post as helpful
  • send pies
  • 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: 31
3
  • Mark post as helpful
  • send pies
  • 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: 13727
228
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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: 31
3
  • Mark post as helpful
  • send pies
  • 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: 65465
249
  • Mark post as helpful
  • send pies
  • 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: 31
3
  • Mark post as helpful
  • send pies
  • 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: 65465
249
  • Mark post as helpful
  • send pies
  • 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.
 
Saloon Keeper
Posts: 3462
149
  • Mark post as helpful
  • send pies
  • 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: 65465
249
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Damn! It hasn't got that method. Piet has beaten me.
 
Carey Brown
Bartender
Posts: 6140
58
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • 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: 68
Eclipse IDE Debian Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is an optimized bubble sort. More efficient.

Here is the link.   webpage

 
You know it is dark times when the trees riot. I think this tiny ad is their leader:
professionally read, modify and write PDF files from Java
https://products.aspose.com/pdf/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!