Results 1 to 4 of 4
  1. #1
    wfsteadman is offline Member
    Join Date
    Jan 2013
    Location
    Texas
    Posts
    45
    Rep Power
    0

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

  2. #2
    wfsteadman is offline Member
    Join Date
    Jan 2013
    Location
    Texas
    Posts
    45
    Rep Power
    0

    Default 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

  3. #3
    Ronin is offline Senior Member
    Join Date
    Oct 2010
    Posts
    317
    Rep Power
    4

    Default 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.

  4. #4
    wfsteadman is offline Member
    Join Date
    Jan 2013
    Location
    Texas
    Posts
    45
    Rep Power
    0

    Default 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

  1. Adding Counts to a mergesort
    By wfsteadman in forum New To Java
    Replies: 0
    Last Post: 03-26-2013, 06:31 PM
  2. Creating a program that counts Votes??
    By besart in forum New To Java
    Replies: 4
    Last Post: 12-06-2012, 05:57 PM
  3. Replies: 5
    Last Post: 03-30-2012, 08:53 PM
  4. combo box comparison question
    By stuckonjava in forum New To Java
    Replies: 1
    Last Post: 03-16-2012, 07:43 PM
  5. Replies: 13
    Last Post: 10-31-2010, 08:42 PM

Posting Permissions

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