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 made16196Recursion Count is 1429

Sorted-Order-Number of swaps made18242Recursion Count is 2452

Reverse-Sorted-Number of swaps made22790Recursion Count is 3475

Random-Order-Number of swaps made16072Recursion Count is 1427

Sorted-Order-Number of swaps made18118Recursion Count is 2450

Reverse-Sorted-Number of swaps made22666Recursion Count is 3473

Random-Order-Number of swaps made16205Recursion Count is 1430

Sorted-Order-Number of swaps made18251Recursion Count is 2453

Reverse-Sorted-Number of swaps made22799Recursion 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

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;

}

}

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());

}

}

}