1. Member 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:

Random-Order-Number of swaps made 16196 Recursion Count is 1429
Sorted-Order-Number of swaps made 18242 Recursion Count is 2452
Reverse-Sorted-Number of swaps made 22790 Recursion Count is 3475
Random-Order-Number of swaps made 16072 Recursion Count is 1427
Sorted-Order-Number of swaps made 18118 Recursion Count is 2450
Reverse-Sorted-Number of swaps made 22666 Recursion Count is 3473
Random-Order-Number of swaps made 16205 Recursion Count is 1430
Sorted-Order-Number of swaps made 18251 Recursion Count is 2453
Reverse-Sorted-Number of swaps made 22799 Recursion Count is 3476
Random-Order-Number of swaps made 16333 Recursion Count is 1422
Sorted-Order-Number of swaps made 18379 Recursion Count is 2445
Reverse-Sorted-Number of swaps made 22927 Recursion Count is 3468
Random-Order-Number of swaps made 16283 Recursion Count is 1435
Sorted-Order-Number of swaps made 18329 Recursion Count is 2458
Reverse-Sorted-Number of swaps made 22877 Recursion Count is 3481
Random-Order-Number of swaps made 16224 Recursion Count is 1437
Sorted-Order-Number of swaps made 18270 Recursion Count is 2460
Reverse-Sorted-Number of swaps made 22818 Recursion Count is 3483
Random-Order-Number of swaps made 16203 Recursion Count is 1420
Sorted-Order-Number of swaps made 18249 Recursion Count is 2443
Reverse-Sorted-Number of swaps made 22797 Recursion Count is 3466
Random-Order-Number of swaps made 16366 Recursion Count is 1431
Sorted-Order-Number of swaps made 18412 Recursion Count is 2454
Reverse-Sorted-Number of swaps made 22960 Recursion Count is 3477
Random-Order-Number of swaps made 16277 Recursion Count is 1427
Sorted-Order-Number of swaps made 18323 Recursion Count is 2450
Reverse-Sorted-Number of swaps made 22871 Recursion Count is 3473
Random-Order-Number of swaps made 16290 Recursion Count is 1425
Sorted-Order-Number of swaps made 18336 Recursion Count is 2448
Reverse-Sorted-Number of swaps made 22884 Recursion Count is 3471
Random-Order-Number of swaps made 16231 Recursion Count is 1440
Sorted-Order-Number of swaps made 18277 Recursion Count is 2463
Reverse-Sorted-Number of swaps made 22825 Recursion Count is 3486
Random-Order-Number of swaps made 16088 Recursion Count is 1413
Sorted-Order-Number of swaps made 18134 Recursion Count is 2436
Reverse-Sorted-Number of swaps made 22682 Recursion Count is 3459
Random-Order-Number of swaps made 16195 Recursion Count is 1436
Sorted-Order-Number of swaps made 18241 Recursion Count is 2459
Reverse-Sorted-Number of swaps made 22789 Recursion Count is 3482
Random-Order-Number of swaps made 16274 Recursion Count is 1419
Sorted-Order-Number of swaps made 18320 Recursion Count is 2442
Reverse-Sorted-Number of swaps made 22868 Recursion Count is 3465
Random-Order-Number of swaps made 16074 Recursion Count is 1419
Sorted-Order-Number of swaps made 18120 Recursion Count is 2442
Reverse-Sorted-Number of swaps made 22668 Recursion Count is 3465
Random-Order-Number of swaps made 16246 Recursion Count is 1436
Sorted-Order-Number of swaps made 18292 Recursion Count is 2459
Reverse-Sorted-Number of swaps made 22840 Recursion Count is 3482
Random-Order-Number of swaps made 16177 Recursion Count is 1415
Sorted-Order-Number of swaps made 18223 Recursion Count is 2438
Reverse-Sorted-Number of swaps made 22771 Recursion Count is 3461
Random-Order-Number of swaps made 16006 Recursion Count is 1421
Sorted-Order-Number of swaps made 18052 Recursion Count is 2444
Reverse-Sorted-Number of swaps made 22600 Recursion Count is 3467
Random-Order-Number of swaps made 16245 Recursion Count is 1431
Sorted-Order-Number of swaps made 18291 Recursion Count is 2454
Reverse-Sorted-Number of swaps made 22839 Recursion Count is 3477
Random-Order-Number of swaps made 16102 Recursion Count is 1427
Sorted-Order-Number of swaps made 18148 Recursion Count is 2450
Reverse-Sorted-Number 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 = right-left+1;
if(size < 5)
insertionSort(left, right);
else
{
int median = medianOf3(left, right);
int partition = partitionIt(left, right, median);
recQuickSort(left, partition-1);
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("Random-Order-Number of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount() );
arrSorted.quickSort();
System.out.println("Sorted-Order-Number of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount());
arrReverseSorted.quickSort();
System.out.println("Reverse-Sorted-Number of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount());

}
}
}```  Reply With Quote

2. Member 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

Wally  Reply With Quote

3. Senior Member Join Date
Oct 2010
Posts
393
Rep Power
10

## 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 23-24 for example should read:
Java Code:
```arr = new ArrayQuickSort(maxSize);
arr.setSwapCount(0);```
Your code if full of lines which could be changed in a similar fashion. Making these changes would allow you to call methods like getMedianCount() on each instance for lines 55-59.

Regards.  Reply With Quote

4. Member 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.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•