Results 1 to 4 of 4
 03272013, 03:25 PM #1Member
 Join Date
 Jan 2013
 Location
 Texas
 Posts
 45
 Rep Power
 0
Another question about Comparison counts
Good morning all,
So I have an program that I am running doing a quicksort on an array with 5000 elements. I run it with the array in random order (300, 60, 57, 299), in ascending numerical order (0,1,2,3,4.....) and in reverse numerical order (4999, 4998, 4997, 4996.....). First off, I am not a math guy so the BigO notation is fuzzy to me, but I figure it out on the fly and use web resources to get the information. I have read that the big O notation for a quicksort was O(n log n) so when I turn that into numbers that becomes if using base 2 log: O(5000 * 12.287712) = 61438.56, and if using base 10 log O(5000 * 3.69897) = 18494.85
As I sit here writing this, I was under the impression that the counts were based on the base log 2, but as I read the formula, I now think it might be based on the base log 10 since there is not indicator in O(n log n) that I should use base log 2?
I am counting the number of times numbers were swapped and I also count how many times the median is defined, the second number is probably not relevant. But i am surprised to see that there are a similar number of swaps when comparing a random number list, to sorted and a reverse sorted list. I have posted my code below:
I guess what I am trying to see is if I am using the right counts to see how much Big O time is required to create a sorted array using the quicksort.
I would appreciate any feedback. This is homework and I am having to do comparisons on mergesorts and quicksorts, the code is done, I am just asking if I am going in the right direction with the comparisons and if I am understanding the Big O notation correctly.
Thanks
Wally
Details below:
When I run my quicksort I am getting the below outputs for 20 runs:
RandomOrderNumber of swaps made 16196 Recursion Count is 1429
SortedOrderNumber of swaps made 18242 Recursion Count is 2452
ReverseSortedNumber of swaps made 22790 Recursion Count is 3475
RandomOrderNumber of swaps made 16072 Recursion Count is 1427
SortedOrderNumber of swaps made 18118 Recursion Count is 2450
ReverseSortedNumber of swaps made 22666 Recursion Count is 3473
RandomOrderNumber of swaps made 16205 Recursion Count is 1430
SortedOrderNumber of swaps made 18251 Recursion Count is 2453
ReverseSortedNumber of swaps made 22799 Recursion Count is 3476
RandomOrderNumber of swaps made 16333 Recursion Count is 1422
SortedOrderNumber of swaps made 18379 Recursion Count is 2445
ReverseSortedNumber of swaps made 22927 Recursion Count is 3468
RandomOrderNumber of swaps made 16283 Recursion Count is 1435
SortedOrderNumber of swaps made 18329 Recursion Count is 2458
ReverseSortedNumber of swaps made 22877 Recursion Count is 3481
RandomOrderNumber of swaps made 16224 Recursion Count is 1437
SortedOrderNumber of swaps made 18270 Recursion Count is 2460
ReverseSortedNumber of swaps made 22818 Recursion Count is 3483
RandomOrderNumber of swaps made 16203 Recursion Count is 1420
SortedOrderNumber of swaps made 18249 Recursion Count is 2443
ReverseSortedNumber of swaps made 22797 Recursion Count is 3466
RandomOrderNumber of swaps made 16366 Recursion Count is 1431
SortedOrderNumber of swaps made 18412 Recursion Count is 2454
ReverseSortedNumber of swaps made 22960 Recursion Count is 3477
RandomOrderNumber of swaps made 16277 Recursion Count is 1427
SortedOrderNumber of swaps made 18323 Recursion Count is 2450
ReverseSortedNumber of swaps made 22871 Recursion Count is 3473
RandomOrderNumber of swaps made 16290 Recursion Count is 1425
SortedOrderNumber of swaps made 18336 Recursion Count is 2448
ReverseSortedNumber of swaps made 22884 Recursion Count is 3471
RandomOrderNumber of swaps made 16231 Recursion Count is 1440
SortedOrderNumber of swaps made 18277 Recursion Count is 2463
ReverseSortedNumber of swaps made 22825 Recursion Count is 3486
RandomOrderNumber of swaps made 16088 Recursion Count is 1413
SortedOrderNumber of swaps made 18134 Recursion Count is 2436
ReverseSortedNumber of swaps made 22682 Recursion Count is 3459
RandomOrderNumber of swaps made 16195 Recursion Count is 1436
SortedOrderNumber of swaps made 18241 Recursion Count is 2459
ReverseSortedNumber of swaps made 22789 Recursion Count is 3482
RandomOrderNumber of swaps made 16274 Recursion Count is 1419
SortedOrderNumber of swaps made 18320 Recursion Count is 2442
ReverseSortedNumber of swaps made 22868 Recursion Count is 3465
RandomOrderNumber of swaps made 16074 Recursion Count is 1419
SortedOrderNumber of swaps made 18120 Recursion Count is 2442
ReverseSortedNumber of swaps made 22668 Recursion Count is 3465
RandomOrderNumber of swaps made 16246 Recursion Count is 1436
SortedOrderNumber of swaps made 18292 Recursion Count is 2459
ReverseSortedNumber of swaps made 22840 Recursion Count is 3482
RandomOrderNumber of swaps made 16177 Recursion Count is 1415
SortedOrderNumber of swaps made 18223 Recursion Count is 2438
ReverseSortedNumber of swaps made 22771 Recursion Count is 3461
RandomOrderNumber of swaps made 16006 Recursion Count is 1421
SortedOrderNumber of swaps made 18052 Recursion Count is 2444
ReverseSortedNumber of swaps made 22600 Recursion Count is 3467
RandomOrderNumber of swaps made 16245 Recursion Count is 1431
SortedOrderNumber of swaps made 18291 Recursion Count is 2454
ReverseSortedNumber of swaps made 22839 Recursion Count is 3477
RandomOrderNumber of swaps made 16102 Recursion Count is 1427
SortedOrderNumber of swaps made 18148 Recursion Count is 2450
ReverseSortedNumber of swaps made 22696 Recursion Count is 3473
Java Code:package QuickSort; public class ArrayQuickSort { private int[] theArray; private int nElms; private static int swapCount=0; private static int medianCount = 0; public ArrayQuickSort(int max) { theArray = new int[max]; nElms = 0; } public void insert(int value) { theArray[nElms] = value; nElms++; } public void display() { System.out.print("Array = "); for (int i = 0; i < nElms; i++) { System.out.print(theArray[i] + " "); if(i%25==0) System.out.println(); } System.out.println(); } private void swap(int dx1, int dx2) { int temp = theArray[dx1]; theArray[dx1] = theArray[dx2]; theArray[dx2] = temp; swapCount++; // I am counting here to see how many times numbers are swapped. } private int medianOf3(int left, int right) { int center =(left+right)/2; if(theArray[left] > theArray[center]) swap(left, center); if(theArray[left] > theArray[right]) swap(left, right); if(theArray[center] > theArray[right]) swap(center, right); swap(center, right); medianCount++; // I am counting here to see how many times the pivot is changed return theArray[right]; } public void quickSort() { recQuickSort(0, nElms 1); } private void recQuickSort(int left, int right) { int size = rightleft+1; if(size < 5) insertionSort(left, right); else { int median = medianOf3(left, right); int partition = partitionIt(left, right, median); recQuickSort(left, partition1); recQuickSort(partition+1, right); } } private int partitionIt(int left, int right, int pivot) { int leftPtr = left  1; int rightPtr = right; while (true) { while (theArray[++leftPtr] < pivot) ; while (theArray[rightPtr] > pivot) ; if(leftPtr >= rightPtr) break; else swap(leftPtr, rightPtr); } swap(leftPtr, right); return leftPtr; } private void insertionSort(int left, int right) { int in, out; for (out = left + 1; out <= right; out++) { int temp = theArray[out]; in = out; while (in > left && theArray[in  1] >= temp) { theArray[in] = theArray[in  1]; in; } theArray[in] = temp; } } public static int getMedianCount() { return medianCount; } public static void setMedianCount(int medianCount) { ArrayQuickSort.medianCount = medianCount; } public static int getSwapCount() { return swapCount; } public static void setSwapCount(int swapCount) { ArrayQuickSort.swapCount = swapCount; } }
Java Code:package QuickSort; import java.util.Random; public class QuickSortApp { /** * @param args the command line arguments */ public static void main(String[] args) { // This for loop just runs through the code 20 times. for(int loop = 0; loop < 20; loop++) { // This creates an array with 5000 random numbers int maxSize = 5000; ArrayQuickSort arr; Random rnd = new Random(); arr = new ArrayQuickSort(maxSize); ArrayQuickSort.setSwapCount(0); ArrayQuickSort.setMedianCount(0); for (int j = 0; j < maxSize; j++) { int n = rnd.nextInt(50000); arr.insert(n); } // This creates a sorted array to test ArrayQuickSort arrSorted; arrSorted = new ArrayQuickSort(maxSize); ArrayQuickSort.setSwapCount(0); ArrayQuickSort.setMedianCount(0); for (int j = 0; j < maxSize; j++) { int n = j + 1; arrSorted.insert(n); } // This creates a reverse sorted array for checks ArrayQuickSort arrReverseSorted; arrReverseSorted = new ArrayQuickSort(maxSize); ArrayQuickSort.setSwapCount(0); ArrayQuickSort.setMedianCount(0); for (int j = 5000; j > 0; j) { int n = j; arrReverseSorted.insert(n); } arr.quickSort(); System.out.println("RandomOrderNumber of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount() ); arrSorted.quickSort(); System.out.println("SortedOrderNumber of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount()); arrReverseSorted.quickSort(); System.out.println("ReverseSortedNumber of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount()); } } }
 04032013, 12:01 AM #2Member
 Join Date
 Jan 2013
 Location
 Texas
 Posts
 45
 Rep Power
 0
Re: Another question about Comparison counts
Hello all,
I am just reviving this as I was hoping that someone might be able to tell me the best place to put counters to make comparisons. I can add a zipped file with the code if necessary
Thanks in advance
Wally
 04032013, 01:42 AM #3Senior Member
 Join Date
 Oct 2010
 Posts
 384
 Rep Power
 5
Re: Another question about Comparison counts
Hi Wally,
Looking at the outputs you already have I am a little confused by what you would like to compare.
Going over you code though, lines 2324 for example should read:
Java Code:arr = new ArrayQuickSort(maxSize); arr.setSwapCount(0);
Regards.
 04032013, 04:10 PM #4Member
 Join Date
 Jan 2013
 Location
 Texas
 Posts
 45
 Rep Power
 0
Re: Another question about Comparison counts
Thanks for the catch, I will make those changes. Not sure why I did that. So I have a list of 5000 random numbers and I am just trying to find the best way to count the number of comparisons and swaps I guess, to get a sorted list. I am not sure I am making my counts in the right places.
Similar Threads

Adding Counts to a mergesort
By wfsteadman in forum New To JavaReplies: 0Last Post: 03262013, 06:31 PM 
Creating a program that counts Votes??
By besart in forum New To JavaReplies: 4Last Post: 12062012, 05:57 PM 
Help fix program counts words in sentance, display odd or even, than true or false
By JMAsterson in forum New To JavaReplies: 5Last Post: 03302012, 08:53 PM 
combo box comparison question
By stuckonjava in forum New To JavaReplies: 1Last Post: 03162012, 07:43 PM 
a program that counts the number of each word in a sentence given by the user
By rambo126 in forum New To JavaReplies: 13Last Post: 10312010, 08:42 PM
Bookmarks