• Post Reply Bookmark Topic Watch Topic
  • New Topic

Random array sorting (1,000,000)  RSS feed

 
Jacob Sousie
Ranch Hand
Posts: 53
1
Eclipse IDE Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey everyone! I'm back with another Java question.  So, what I was supposed to do was create 3 randomly generated arrays.  one with 10 values, one with 1000, and one with 1,000,000. and then list ONLY the first ten elements of each, and then sort ONLY the first 10 digits of the whole array.

So everything was going well.  I made a few methods for each of my cases, my RandomArray for 10 and 1000 worked just fine.  But when I got to the 1,000,000 RandomArray it wouldn't print the sorted values, and never stops running the program.  Is this because the number is so big? 

(sorry its a bit of a mess, but I was trying to work on the logic before I made it look pretty)  Is my logic still valid for the RandomArray 1,000,000   would it work in theory, but just not on my laptop?

Here's my code so far:





Thanks in advance!
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was trying to work on the logic before I made it look pretty)  Is my logic still valid 

I don't see any of the logic expressed in comments in the code so its hard to comment on the logic without seeing what it is.
 
Liutauras Vilda
Sheriff
Posts: 4927
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm looking to the code, well, not looking for particular mistake now, but seeing lots of same methods. Why have you created each method multiple times? Probably you know that purpose of methods ar partially that, not to repeat yourself, but rather re-use methods for the same kind of task.

Feels like you can throw away about 1/3 of the code and have same functionality.

Now there are other insteresting things. I'm not trying to look for potential mistakes, just looking for weird things now. countM() method, why you have loop starting like that? "for (int j = 999990..." Can't wrap my head.

Let's do that way - try to put some print statements on quite a few places by writing i.e.: "i'm in a for loop, my i is: + i"... values after swap are ... and you'll likely see unexpected things.
 
Jacob Sousie
Ranch Hand
Posts: 53
1
Eclipse IDE Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:I'm looking to the code, well, not looking for particular mistake now, but seeing lots of same methods. Why have you created each method multiple times? Probably you know that purpose of methods ar partially that, not to repeat yourself, but rather re-use methods for the same kind of task.

Feels like you can throw away about 1/3 of the code and have same functionality.

Now there are other insteresting things. I'm not trying to look for potential mistakes, just looking for weird things now. countM() method, why you have loop starting like that? "for (int j = 999990..." Can't wrap my head.

Let's do that way - try to put some print statements on quite a few places by writing i.e.: "i'm in a for loop, my i is: + i"... values after swap are ... and you'll likely see unexpected things.


Why I used 999,990 is because I only need the first 10 out of the 1,000,000(that's what my teacher told me to do)  so I start the value at 999,990 because 1,000,000 - 999,990 = 10
it worked for my other methods(10 and 1000),  but for some reason when I try it with 1,000,000 it won't work.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jacob Sousie wrote:So, what I was supposed to do was create 3 randomly generated arrays.  one with 10 values, one with 1000, and one with 1,000,000. and then list ONLY the first ten elements of each, and then sort ONLY the first 10 digits of the whole array.

I see attempts to sort and print the entire array, your instructions say to do this for ONLY the first 10 [numbers] of the whole array.
 
Liutauras Vilda
Sheriff
Posts: 4927
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jacob Sousie wrote:Why I used 999,990 is because I only need the first 10 out of the 1,000,000(that's what my teacher told me to do)  so I start the value at 999,990 because 1,000,000 - 999,990 = 10

Alright. So if I have 10 apples, counting from the left 1, 2, 3, 4, 5, ... and somebody told me to take first 3 apples, what I do? taking them starting from 1st up to 3rd including or from 8th up to 10th including?
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:
Jacob Sousie wrote:So, what I was supposed to do was create 3 randomly generated arrays.  one with 10 values, one with 1000, and one with 1,000,000. and then list ONLY the first ten elements of each, and then sort ONLY the first 10 digits of the whole array.

I see attempts to sort and print the entire array, your instructions say to do this for ONLY the first 10 [numbers] of the whole array.

Doesn't make sense to fill an array with a million numbers and then only deal with the first 10. Are you sure about those instructions? Are you paraphrasing?
 
Liutauras Vilda
Sheriff
Posts: 4927
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can you show us those instructions?
 
Jacob Sousie
Ranch Hand
Posts: 53
1
Eclipse IDE Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:Can you show us those instructions?


3. Selection sort, based on Gaddis in-chapter example. (15 points)
Create a new Java project and class. Add the following method, based on the Gaddis in-chapter example. Please remember to type in this code rather than copy-and-pasting; Word loves to mangle source code.
public static void selectionSort(int[] array) {
int startScan, index, minIndex, minValue;
for (startScan = 0; startScan < (array.length - 1); startScan++) {
minIndex = startScan;
minValue = array[startScan];
for (index = startScan + 1; index < array.length; index++) {
if (array[index] < minValue) {
minValue = array[index];
minIndex = index;
}
}
array[minIndex] = array[startScan];
array[startScan] = minValue;
}
}
Create an array of ten random integers, and array of 1,000 random integers, and an array of a million (1,000,000) random integers.
For each array:
Display the first ten elements of the array.
Call selection sort for the array.
Display the first ten elements of the sorted array.







These are the instructions
 
Jacob Sousie
Ranch Hand
Posts: 53
1
Eclipse IDE Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:
Carey Brown wrote:
Jacob Sousie wrote:So, what I was supposed to do was create 3 randomly generated arrays.  one with 10 values, one with 1000, and one with 1,000,000. and then list ONLY the first ten elements of each, and then sort ONLY the first 10 digits of the whole array.

I see attempts to sort and print the entire array, your instructions say to do this for ONLY the first 10 [numbers] of the whole array.

Doesn't make sense to fill an array with a million numbers and then only deal with the first 10. Are you sure about those instructions? Are you paraphrasing?



I cleaned up the code a bit:


 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jacob Sousie wrote:Create an array of ten random integers, and array of 1,000 random integers, and an array of a million (1,000,000) random integers.
For each array:
Display the first ten elements of the array.
Call selection sort for the array.
Display the first ten elements of the sorted array.

You don't need different sort methods for each array length, one will do the job.
You need a method: displayFirstTen( int[] array )
You can reuse that display method.
 
Jacob Sousie
Ranch Hand
Posts: 53
1
Eclipse IDE Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:
Jacob Sousie wrote:Create an array of ten random integers, and array of 1,000 random integers, and an array of a million (1,000,000) random integers.
For each array:
Display the first ten elements of the array.
Call selection sort for the array.
Display the first ten elements of the sorted array.

You don't need different sort methods for each array length, one will do the job.
You need a method: displayFirstTen( int[] array )
You can reuse that display method.


I just cut them out   now I just have one selectionSort(int[] array)     (required to use that method name)

why does it work with 10 and 1000, but not 1,000,000?  I tried debugging but it just skips over the code.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jacob Sousie wrote:I just cut them out   now I just have one selectionSort(int[] array)     (required to use that method name)
why does it work with 10 and 1000, but not 1,000,000?  I tried debugging but it just skips over the code.

What makes you think it's not working? It might just take a long time, about one thousand times longer than the sort of 1000.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
On my (fast) machine, sorting a million took 3.5 minutes.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

You don't want to be printing the whole array here. Remove lines 34-37. Every method should only do one thing.

You don't want to repeat your code. Move your functionality into reusable methods. For instance, your main() might look something like this:
 
Jacob Sousie
Ranch Hand
Posts: 53
1
Eclipse IDE Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Norm Radder wrote:
I was trying to work on the logic before I made it look pretty)  Is my logic still valid 

I don't see any of the logic expressed in comments in the code so its hard to comment on the logic without seeing what it is.


All I meant were my formulas.
 
Jacob Sousie
Ranch Hand
Posts: 53
1
Eclipse IDE Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:
You don't want to be printing the whole array here. Remove lines 34-37. Every method should only do one thing.

You don't want to repeat your code. Move your functionality into reusable methods. For instance, your main() might look something like this:


When I get rid of the other methods, it prints 1000 numbers.  that's why I made different methods for each case.  Because when I use the one that was meant for the number 10 it doesn't count them right.  And when I try using the run(10) methods I get an error.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jacob Sousie wrote:When I get rid of the other methods, it prints 1000 numbers.  that's why I made different methods for each case.  Because when I use the one that was meant for the number 10 it doesn't count them right.

You've got a printArray() method, no other method should be printing the array, that's why I told you to remove those lines and the corresponding lines in the other copies of the method. You can call printArray() after you populate the array, and then again after you sort.

And when I try using the run(10) methods I get an error.

To use the run(10) approach you'd need to get rid of all of your redundant methods and then insert calls to the remaining methods inside the run() method. Note that there's nothing special about the name 'run', I picked that name off the top of my head, it's a method like any other method.
 
Jacob Sousie
Ranch Hand
Posts: 53
1
Eclipse IDE Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:
You don't want to be printing the whole array here. Remove lines 34-37. Every method should only do one thing.

You don't want to repeat your code. Move your functionality into reusable methods. For instance, your main() might look something like this:


Okay, I got rid of some of my methods and got this:



And here's the output:


The original order is:
1
2
2
3
7
3
1
1
3
3
The sorted values are:
1 1 1 2 2 3 3 3 3 7
The original order is:
9
7
4
8
6
3
0
2
2
8
The sorted values are:
0 0 0 0 0 0 0 0 0 0
The original order is:
9
8
1
1
6
3
8
2
7
0




Which looks right so far.  But I don't know why 1,000,000 wont print it's 10 sorted values!



I don't know how to use that run method you showed me. :/  I don't know what would go inside of it for the random numbers.  Maybe if I use that it will help xD
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jacob Sousie wrote:Which looks right so far.  But I don't know why 1,000,000 wont print it's 10 sorted values!

You may not be waiting long enough for the sort to finish. Depending on the speed of your machine it may take anywhere from 5 to 15 minutes.
I don't know how to use that run method you showed me. :/  I don't know what would go inside of it for the random numbers.  Maybe if I use that it will help xD

So far so good. You've eliminated a bunch of redundancy, these 4 lines are the only redundant ones left. Put them inside run().
 
Jacob Sousie
Ranch Hand
Posts: 53
1
Eclipse IDE Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:
Jacob Sousie wrote:Which looks right so far.  But I don't know why 1,000,000 wont print it's 10 sorted values!

You may not be waiting long enough for the sort to finish. Depending on the speed of your machine it may take anywhere from 5 to 15 minutes.
I don't know how to use that run method you showed me. :/  I don't know what would go inside of it for the random numbers.  Maybe if I use that it will help xD

So far so good. You've eliminated a bunch of redundancy, these 4 lines are the only redundant ones left. Put them inside run().



I see!  using run() made it so much easier!


Here's my updated code:





It's so much shorter than before hahaha.   Thank you so much!  I understand it now!  lets just hope my laptop will print the 1000000 soon lol.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A selectionSort's time does not increase linearly, meaning, adding just a few more elements to an array can add a lot more to the time. If you're curious about how long the sort takes you can instrument your code like this:
Then you might want to increase your array sizes a little slower, perhaps: 1_000, 10_000, 100_000, and then 1_000_000. In this way you can see for yourself how the length of time increases.

BTW, inserting underscores (_) in a number is ignored by the compiler but is available to use to improve human readability.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Another tweak you might consider is passing in a String as well as the array to your printArray() method so that the message "The sorted values are:" is not hard coded but passed in. Doing this allows you to do away with the printOriginal() method.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

On line 16 you are generating random numbers from 0 through 9 inclusive. This was not part of your requirements. Additionally if you have a million of these and sort them your sorted list will probably come out as: 0 0 0 0 0 0 0 0 0 0.

I think you want random integers. Using Math.random() is now considered obsolete and has been replaced with the Random class. Then you can use its nextInt() to get a random integer.
 
Jacob Sousie
Ranch Hand
Posts: 53
1
Eclipse IDE Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:
On line 16 you are generating random numbers from 0 through 9 inclusive. This was not part of your requirements. Additionally if you have a million of these and sort them your sorted list will probably come out as: 0 0 0 0 0 0 0 0 0 0.

I think you want random integers. Using Math.random() is now considered obsolete and has been replaced with the Random class. Then you can use its nextInt() to get a random integer.



When I changed it to that the output was this:
(P.S I didn't wait the 10 minutes it takes for the 1,000,000 to print lol)


----------------------
The original order is:
-1879149745
1757240302
1055153058
1596833882
-523450158
622502470
1349540553
-625047098
1121336350
-718157567
The sorted values are:
-1879149745 -718157567 -625047098 -523450158 622502470 1055153058 1121336350 1349540553 1596833882 1757240302
----------------------
The original order is:
1487329618
-1693883286
-823401678
2141062909
-1758188659
-1475810748
1820909735
625575232
742380899
-586603047
The sorted values are:
-1758188659 -1693883286 -1475810748 -823401678 -586603047 0 0 0 0 0
----------------------
The original order is:
-749229472
-133866982
-1136321893
497656738
496711691
1924788732
-882747006
1804858718
1480091910
2104589220
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:On my (fast) machine, sorting a million took 3.5 minutes.
Have you compared that with Arrays#sort? Selection sort runs in On² complexity and, the last time I timed it, I found it only slightly faster than bubble sort. But it was still much faster than bogosort You will probably find that Arrays#sort, which uses quicksort, will run in 100ms or something like that.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!