[mattlyons]

I am trying to create a random list in the main, use the quickSort algorithm method on it, print how long it took, use the same random list generated, use the quickInsertionSort algorithm method on it, and print how long it took to do that one. I am a little confused on how to actually the random list with the method I wrote and then use the list with the two algorithm sorting methods I wrote (quicksort and quickInsertionSort). Help please! This is due fairly quickly, like little over two hours

Thanks in advance.

class

import java.util.Random;

public class qsComparison {
	
	public qsComparison() {
	}
	
	public class ExecutionTimer {
		  private long start;
		  private long end;

		  public ExecutionTimer() {
			  reset();
		  }

		  public void start() {
			  start = System.currentTimeMillis();
		  }

		  public void end() {
			    end = System.currentTimeMillis();
		  }

		  public double durationInSeconds() {
			    return ((end - start) / 1000.0);
		  }

		  public void reset() {
			    start = 0;  
			    end   = 0;
		  }
	}
	
	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 void 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);
	}
	
	public void quickInsertionSort(int a[], int left, int right) {
   		if(a.length < 30) {
   			insertionSort(a, a.length);
   			return;
   		}
		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;
			}
			else {
				quicksort(a, left, j);
			}
		}
		if(i < right) {
			if(mid < 30) {
				insertionSort(a, a.length);
				return;
			}
			else {
				quicksort(a, i, right);
			}
		}
	}
	
	public int[] randomList() {
		Random r = new Random();
		int a[] = new int[1000000];
		
		for(int i = 1; i <= 1000000; i++) {
			int j = r.nextInt(101);
			a[i - 1] = j;
		}
		return a;
	}

	public static void main(String[] args) {
		
	    for (int trial = 1; trial <= 3; trial++) {
	    	ExecutionTimer t = new ExecutionTimer();
	    	t.start();
	    	System.out.println("Trial " + trial);
	    	randomList();
	    	quicksort();
		t.end();
		System.out.println("\n" + t.durationInSeconds() + " seconds\n");
		t.start();
		quickInsertionSort();
                t.end();
		System.out.println("\n" + t.durationInSeconds() + " seconds\n");
		}
	}
}

This post has been edited by mattlyons: 19 April 2010 - 11:20 AM

[Dogstopper]

Sorry I'm late answering this, but your error is simple and lies in main:

public static void main(String[] args) {
                
            for (int trial = 1; trial <= 3; trial++) {
                ExecutionTimer t = new ExecutionTimer();
                t.start();
                System.out.println("Trial " + trial);
                // This method returns an int[]
                randomList();
                // This method takes arguments
                quicksort();
                t.end();
                System.out.println("\n" + t.durationInSeconds() + " seconds\n");
                t.start();
                // This takes arguments
                quickInsertionSort();
                t.end();
                System.out.println("\n" + t.durationInSeconds() + " seconds\n");
                }
        }

So basically, you forgot to take and pass variables to and from the well-made methods that you wrote...

[mattlyons]

Okay so I need to create an instance of randomList, quickSort, and quickInsertionSort. I can do that. But I don't quite know what I should pass into those as parameters. Yea the date has passed but I just want to know for me now.

[Dogstopper]

You need a qsComparison object and simply match the variables:

public static void main(String[] args) {
                
            for (int trial = 1; trial <= 3; trial++) {
                ExecutionTimer t = new ExecutionTimer();
                System.out.println("Trial " + trial);

                int[] list = randomList();

                // Start the timer here to be consistent.
                t.start();
                quicksort(list);
                t.end();
                System.out.println("\n" + t.durationInSeconds() + " seconds\n");
                t.start();
                quickInsertionSort(list);
                t.end();
                System.out.println("\n" + t.durationInSeconds() + " seconds\n");
                }
        }

[mattlyons]

Ok I got a few questions.

I added parameters to the spots needed but it said "Cannot make a static reference to a non-static method randomList() from the type Test". It said that for randomList(), quicksort(), and quickInsertionSort(). Should I just change the signatures of the three methods to static to fix this or should I solve this in a different way?

I added a "test line of code in the main, System.out.println(list), and it only printed the memory address and not the integers stored in it.

Seems like there was one more but I can't seem to remember it so I'll stay with this for now.

[Dogstopper]

*facepalm*

My bad...I started the right answer here:

Quote

You need a qsComparison object and simply match the variables:

But I posted the wrong code...You need to reference those methods through an object:

public static void main(String[] args) {
                
            for (int trial = 1; trial <= 3; trial++) {
                ExecutionTimer t = new ExecutionTimer();
                qsComparison q = new quComparison();
                System.out.println("Trial " + trial);

                int[] list = q.randomList();

                // Start the timer here to be consistent.
                t.start();
                q.quicksort(list);
                t.end();
                System.out.println("\n" + t.durationInSeconds() + " seconds\n");

                t.start();
                q.quickInsertionSort(list);
                t.end();
                System.out.println("\n" + t.durationInSeconds() + " seconds\n");
                }
        }

This post has been edited by Dogstopper: 21 April 2010 - 02:29 PM
Reason for edit:: code tags

[mattlyons]

Haha its all good. That does look better now though; I knew all those static methods couldn't be the best way.

I put this in my code:

public static void main(String[] args) {
                
    for (int trial = 1; trial <= 1; trial++) {  
        Test test = new Test();
        ExecutionTimer t = new ExecutionTimer();  //ERROR #2
        System.out.println("Trial " + trial);
        int[] list = randomList();
        System.out.println(list);  //ERROR #1

Error #1: The print line only prints out the memory location of list. How can I get it to print out the list?

Error #2: "No enclosing instance of type Test is accessible. Must qualify the allocation with an enclosing instance of type Test." What does this mean? I thought it was because you had put created the instance of Test after created the instance of ExecutionTimer but that wasn't it.

[Dogstopper]

Error #2:

Since ExecutionTimer is an internal class, you have to have a qsComparison object create a new instance of ExecutionTimer...That is weird...I know.

qsComparison q = new qsComparison();
ExecutionTimer t = q.new ExecutionTimer();

And now for Error #1:
You can loop through and print each index OR use the Arrays class:

System.out.println(Arrays.toString(list));

[mattlyons]

Thanks a lot Dogstopper. That was really strange with the creating the instance of the ExecutionTimer. Never seen nothing like that before. I got it compiling and printing stuff out but not quite performing the way it should.

Error #1: It prints out the list before the sort and afterwards, but the afterwards printout is the same as the first. So, in other words, it is not sorting the list. I can't seem to figure out why. I understand the algorithm pretty decently even though I did get the code for this particular quicksort from google.

Error #2: I put 100 million ints in the list and had it sort it (even though it didn't sort it) and it took well over a minute to finish whatever it was doing. The timer printout at the end always says 0.0 seconds

Here is the up to date code after it has been compiling:

import java.util.Arrays;
import java.util.Random;

public class Test {
        
        public Test() {
        }
        
        public class ExecutionTimer {
                  private long start;
                  private long end;

                  public ExecutionTimer() {
                          reset();
                  }

                  public void start() {
                          start = System.currentTimeMillis();
                  }

                  public void end() {
                            end = System.currentTimeMillis();
                  }

                  public double durationInSeconds() {
                            return ((end - start) / 1000);
                  }

                  public void reset() {
                            start = 0;  
                            end   = 0;
                  }
        }
        
        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 void 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);
        }
        
        public void quickInsertionSort(int a[], int left, int right) {
                if(a.length < 30) {
                        insertionSort(a, a.length);
                        return;
                }
                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;
                        }
                        else {
                                quicksort(a, left, j);
                        }
                }
                if(i < right) {
                        if(mid < 30) {
                                insertionSort(a, a.length);
                                return;
                        }
                        else {
                                quicksort(a, i, right);
                        }
                }
        }
        
        public static int[] randomList() {
                Random r = new Random();
                int a[] = new int[10];
                
                for(int i = 1; i <= 10; 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();
                ExecutionTimer t = test.new ExecutionTimer();
                System.out.println("Trial " + trial);
                int[] list = randomList();
                System.out.println(Arrays.toString(list));
                t.start();                
                test.quicksort(list, list.length  / 4, list.length / 3);                
                t.end(); 
                System.out.println(Arrays.toString(list));
                System.out.println("\nControl: " + t.durationInSeconds() + " seconds\n");
                t.start();
                test.quickInsertionSort(list, list.length / 4, list.length / 3);
                t.end();
                System.out.println("\nTest: " + t.durationInSeconds() + " seconds\n");
                }
        }
}

This post has been edited by mattlyons: 21 April 2010 - 03:51 PM

[Dogstopper]

#1: Oops, I thought you WANTED it that way... Well, objects passed to methods are never changed as explained HERE. The workaround is to have each of those methods return the sorted array and receive it like so:

t.start();                
                list = test.quicksort(list, list.length  / 4, list.length / 3);                
                t.end(); 
                System.out.println(Arrays.toString(list));
                System.out.println("\nControl: " + t.durationInSeconds() + " seconds\n");
                t.start();
                list = test.quickInsertionSort(list, list.length / 4, list.length / 3);
                t.end();
                System.out.println("\nTest: " + t.durationInSeconds() + " seconds\n");

As for #2, I'm really not sure, but right now, you aren't returning a double...You divide by 1000 instead of 1000.0 which could cause a problem.

                  public double durationInSeconds() {
                            return ((end - start) / 1000.0);
                  }

[mattlyons]

I tried that but it still isn't sorting the list because both printouts are the same. Maybe I will go search for another quicksort online and see if theirs work. But if anyone catches why it is not sorting/printing the right thing, feel free to fix my current code.

As for the double/long thing. That was just an overlook by me so I changed the durationInSeconds() method to a long as well. Timer still not working either.

Thanks for the help Dogstopper. You have gotten me far. Its compiling at least and is practically finished now. Just one little thing messed up someowhere, I can feel it!

[mattlyons]

I just worked on it about an hour with fresh eyes and fixed a couple things. I got the quickInsertionSort to work completely. It sorts any list thrown at it. The quicksort, for some reason, does not work. It shuffles a couple of the values around in the list to be sorted, but it doesn't finish it. For example, the list:

[20, 57, 43, 58, 10, 95, 99, 15, 16, 38]

gets "sorted" halfwayish to this:

[20, 43, 57, 58, 10, 95, 99, 15, 16, 38]

Not sure what is wrong with it.

And still, the timers are always saying 0 seconds. I put the list to 10 million ints and it takes almost a whole second to execute. I have it just printing the starting and ending times, and they are equal for some reason. For example, one test print this:

Start: 1271917526554
End: 1271917526554

EDIT:: The quickInsertionSort falls to pieces and does not work when the list is over 30. In the code I have it to go directly to the insertionSort if the list was under 30 and if not, to go to quicksort. This means that my insertionSort works perfectly and, still, the quicksort does not work.

import java.util.Arrays;
import java.util.Random;

public class Test {
        
        public Test() {
        }
        
        public class ExecutionTimer {
        	private long start;
        	private long end;

        	public ExecutionTimer() {
        		reset();
        	}

        	public void start() {
        		start = System.currentTimeMillis();
        	}

        	public void end() {
        		end = System.currentTimeMillis();
        	}

        	public long durationInSeconds() {
        		return ((end - start) / 1000);
        	}

        	public void reset() {
        		start = 0;  
        		end = 0;
        	}
        }
        
        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[10];
                
        	for(int i = 1; i <= 10; 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();
                ExecutionTimer t = test.new ExecutionTimer();
                int[] z = randomList();
                System.out.println("Trial " + trial);
                
                int[] controlList = z;
                System.out.println(Arrays.toString(controlList));
                t.start();
                controlList = test.quicksort(controlList, trial, trial + 1);                
                t.end(); 
                System.out.println(Arrays.toString(controlList));
                System.out.println("\nControl: " + t.durationInSeconds() + " seconds\n");

                int[] testList = z;
                System.out.println(Arrays.toString(testList));
                t.start();
                testList = test.quickInsertionSort(testList, trial, trial + 1);
                t.end();
                System.out.println(Arrays.toString(testList));
                System.out.println("\nTest: " + t.durationInSeconds() + " seconds\n");
                }
        }
}

This post has been edited by mattlyons: 21 April 2010 - 11:28 PM

[mattlyons]

maybe i need a whole new quicksort?

[mattlyons]

I don't know if it is allowed to "bump" things but this was about to fall off the first page and I haven't gotten any help in a while and I need some help

[nick2price]

Dogstopper is a mod on this forum, and is on all of the time. As he has been going through all of this post with you, which is quite long, might be better to ask for further help when he is online. Otherwise, some other member is going to have to go through the whole page reading whats been done already (Although, this is a nice community and someone might just do that!)