Are you saying that I should contact Dogstopper privately?
And should I make a fresh post for other people to know what I am asking for quickly?
22 Replies  1249 Views  Last Post: 24 April 2010  09:00 AM
#17
Re: Calling methods in a main
Posted 22 April 2010  08:24 PM
No. Please don't contact me privately. Keep all things on the forums. What nick2price was saying that as a mod of this forum, I have to check constantly, and it might be good to ask while I a online. I disagree. I check all of the posts I have contributed to first, then check "0"s, and then others.
However, I am leaving town tomorrow and will not be on much, so anyone feel free to jump in.
@mattlyons: You might want to ensure that your quicksort algorithm works before trying to implement into a larger program. So do something like try it in a separate program all by itself, make it so that is can return what it needs to be returning and doing what needs to be done. Then and only then, stick it back into the big algorithm.
However, I am leaving town tomorrow and will not be on much, so anyone feel free to jump in.
@mattlyons: You might want to ensure that your quicksort algorithm works before trying to implement into a larger program. So do something like try it in a separate program all by itself, make it so that is can return what it needs to be returning and doing what needs to be done. Then and only then, stick it back into the big algorithm.
#18
Re: Calling methods in a main
Posted 22 April 2010  10:57 PM
Ok thanks, I will try that.
#19
Re: Calling methods in a main
Posted 23 April 2010  12:29 AM
So when professors actually say not to try and tackle the whole project at one time and to break it up into pieces, apparently they know what they are talking about. I did like you said Dogstopper and got the quicksort to work
I changed the timer up a little bit by taking out the inner class and added 4 lines of code in the main. The timer is STILL coming up with 0 seconds every time though, even when I ran the code and it took 6 or 7 minutes to sort all the way. So I do still need help with the timer. Help is appreciated and thanks again Dogstopper.
Here is my up to date code:
I changed the timer up a little bit by taking out the inner class and added 4 lines of code in the main. The timer is STILL coming up with 0 seconds every time though, even when I ran the code and it took 6 or 7 minutes to sort all the way. So I do still need help with the timer. Help is appreciated and thanks again Dogstopper.
Here is my up to date code:
import java.util.Arrays; import java.util.Random; public class Test { public Test() { } public void insertionSort(int a[], int n) { int temp; int i; int j; for(j = 1; j < n; j++) { i = j  1; temp = a[j]; while(i >= 0 && temp < a[i]) { a[i+1] = a[i]; i; } a[i+1] = temp; } } public int[] quicksort(int a[], int left, int right) { int mid; int temp; int i = left; int j = right; mid = a[(left + right) / 2]; do { while(a[i] < mid) i++; while(mid < a[j]) j; if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j; } } while(i <= j); if(left < j) quicksort(a, left, j); if(i < right) quicksort(a, i, right); return a; } public int[] quickInsertionSort(int a[], int left, int right) { if(a.length < 30) { insertionSort(a, a.length); return a; } int mid; int temp; int i = left; int j = right; mid = a[(left + right) / 2]; do { while(a[i] < mid) i++; while(mid < a[j]) j; if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j; } } while(i <= j); if(left < j) { if(mid < 30) { insertionSort(a, a.length); return a; } else { quicksort(a, left, j); } } if(i < right) { if(mid < 30) { insertionSort(a, a.length); return a; } else { quicksort(a, i, right); } } return a; } public static int[] randomList() { Random r = new Random(); int a[] = new int[500000]; for(int i = 1; i <= 500000; i++) { int j = r.nextInt(101); a[i  1] = j; } return a; } public static void main(String[] args) { for (int trial = 1; trial <= 1; trial++) { Test test = new Test(); System.out.println("Trial " + trial + "\n"); int[] y = randomList(); System.out.println(Arrays.toString(y)); long startTime1 = System.nanoTime(); y = test.quicksort(y, 0, y.length  1); long endTime1 = System.nanoTime(); System.out.println(Arrays.toString(y)); System.out.println("That took " + (endTime1  startTime1) / 1000000000.0 + " seconds."); int[] z = randomList(); System.out.println(Arrays.toString(z)); long startTime2 = System.currentTimeMillis(); z = test.quickInsertionSort(z, 0, z.length  1); long endTime2 = System.currentTimeMillis(); System.out.println(Arrays.toString(z)); System.out.println("That took " + (endTime2  startTime2) / 1000 + " seconds."); } } }
This post has been edited by mattlyons: 23 April 2010  12:37 PM
#20
Re: Calling methods in a main
Posted 23 April 2010  03:18 AM
Ok, so the algorithm for me is happening instantly and so the millisecond is proving too slow. The algorithm on my computer takes 7.6896E6 seconds. Thus the time in milliseconds before and after is identical, which makes it 0. I highly suggest nanoTime(), which gives the time in milliseconds to see if that works.
Results:
The first time is currentTimeMillies(), the second is nanoTime().
DON'T FORGET THE DOUBLE! That's so important here.
By the way, a nano is 10E9, so you need to divide it be 1000000000.0 to make it a second.
Results:
The first time is currentTimeMillies(), the second is nanoTime().
Quote
Trial 1
[9, 79, 94, 42, 93, 71, 97, 52, 35, 45]
[9, 35, 42, 45, 52, 71, 79, 93, 94, 97]
That took 0.0 seconds.
[50, 0, 59, 72, 16, 53, 23, 5, 44, 75]
[0, 5, 16, 23, 44, 50, 53, 59, 72, 75]
That took 9.708E7 seconds.
[9, 79, 94, 42, 93, 71, 97, 52, 35, 45]
[9, 35, 42, 45, 52, 71, 79, 93, 94, 97]
That took 0.0 seconds.
[50, 0, 59, 72, 16, 53, 23, 5, 44, 75]
[0, 5, 16, 23, 44, 50, 53, 59, 72, 75]
That took 9.708E7 seconds.
DON'T FORGET THE DOUBLE! That's so important here.
public static void main(String[] args) { for (int trial = 1; trial <= 1; trial++) { Test test = new Test(); System.out.println("Trial " + trial + "\n"); int[] y = randomList(); System.out.println(Arrays.toString(y)); long startTime1 = System.currentTimeMillis(); y = test.quicksort(y, 0, y.length  1); long endTime1 = System.currentTimeMillis(); System.out.println(Arrays.toString(y)); System.out.println("That took " + (endTime1  startTime1) / 1000.0 + " seconds."); int[] z = randomList(); System.out.println(Arrays.toString(z)); long startTime2 = System.nanoTime(); z = test.quickInsertionSort(z, 0, z.length  1); long endTime2 = System.nanoTime(); System.out.println(Arrays.toString(z)); System.out.println("That took " + (endTime2  startTime2) / 10000000000.0 + " seconds."); } }
By the way, a nano is 10E9, so you need to divide it be 1000000000.0 to make it a second.
#21
Re: Calling methods in a main
Posted 23 April 2010  11:20 PM
Same thing happens with nanoseconds; I put in enough integers in the Array so that it takes several minutes to finish sorting and the result still stays under one second (i.e. .0249398 seconds). Could it possibly be that my laptop is too slow and that it is actually sorting it in under a second, it is just my laptop is too slow to keep up?
#22
Re: Calling methods in a main
Posted 24 April 2010  06:45 AM
Honestly, runtime in metricPrefixseconds is not a good estimate of the efficiency of an algorithm, only how well it runs relative to other algorithms. This is due to the fact that runtime is unique to that particular computer. Even if we have two identical computers in terms of hardware, we don't have identical computers in terms of software configurations. So the better unit of measurement is the number of steps your algorithm takes based on the size of the problem. You can plot this data for increasing sizes, and run regression tests to approximate/prove the BigO of the algorithm statistically.
#23
Re: Calling methods in a main
Posted 24 April 2010  09:00 AM
Well the problem is that our assignment says to represent it in terms of seconds. I am going to have to go sit down with the teacher with this one I guess.
