Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: QuickSort Help

  1. #1
    Junior Member
    Join Date
    Feb 2013
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default QuickSort Help

    I'm working on this program which uses the quickSort algorithm to sort arrays of N sizes using the median of 3 to determine the pivot. The output is to print the list the number of comparisons for the arrays of N= 64 and 128 to a file named "output.txt". Also as another requirement, when the arrays get repartitioned below 10 elements, it switches to bubbleSort. So far I have this:

    import java.util.Random;
    import java.io.*;
     
    public class Project3 {
     
        /**
         * @param args the command line arguments
         */
        public static void main(String[] args) throws IOException {
            //array n = the size of arrays to sort
            //array bsa and ssa for BubbleSort and SelectionSort
            int[] n = {16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768};
            int count = 0;
            int[] qsa = new int[n.length];
     
            Random randomNumber = new Random();
     
            for(int i = 0; i < n.length; i++){
                int[] array = new int[n[i]];
                for(int j= 0; j < array.length; j++){
                    array[j] = randomNumber.nextInt(4999);
                }
     
                int quickSortCount = quickSort(array, 0, array.length - 1);
     
                if(count <= 2){
                    System.out.println("Sorted Array of "+n[i]+": " + java.util.Arrays.toString(array));
                    count++;
                }
     
                qsa[i] = quickSortCount;
            }
     
            System.out.println();
     
            /**
             * Writes the # of comparisons in the quickSort
             * method at each n[x] location.
             */
            PrintWriter out = new PrintWriter("Output.txt");
     
            out.println("N\tQuickSort");
            System.out.println("N\t\tQuickSort");
     
            for(int x = 0; x < qsa.length; x++){
                out.println(n[x]+"\t"+qsa[x]);
                System.out.println(n[x]+"\t\t"+qsa[x]);
            }
     
            out.close();
        }
     
        /**
         * QuickSort: Sorts the array recursively through the 
         * quickSort method until the  partitioned array size
         * is less than 10, at with point it switches to 
         * bubbleSort.
         * 
         * @param array
         * @param left
         * @param right 
         */
        static int quickSort(int[] array, int left, int right){
            int size = right - left + 1;
            int count = 0;
            int bsc = 0;
     
            count++;
     
            if(size < 10){
     
                bsc = bubbleSort(array);
     
            }
            else{
                double median = medOf3(array, left, right);
                int p = partition(array, left, right, median);
                quickSort(array, left, p - 1);
                quickSort(array, p + 1, right);
            }
     
            count += bsc;
            return count;
        }
     
        /**
         * 
         * @param array
         * @return 
         */
        static int bubbleSort(int[] array){
            int n = array.length;
            int count = 0;
     
            for(int pass=1; pass<=n; pass++){
                for(int current=0; current<n-pass; current++){
                    if(array[current] > array[current+1]){
                        //swap 
                        int temp = array[current];
                        array[current] = array[current+1];
                        array[current+1] = temp;
                        count++;
                    }
                }
            }
     
            return count;
        }
        /**
         * MedOf3: computes the the median.
         * 
         * @param array
         * @param left
         * @param right
         * @return 
         */
        static int medOf3(int[] array, int left, int right){
            int center = (left+right) / 2;
     
            if(array[left] > array[center])
                swap(array, left, center);
            if(array[left] > array[right])
                swap(array, left, right);
            if(array[center] > array[right])
                swap(array, center, right);
     
            swap(array, center, right - 1);
     
            return array[right - 1];
        }
     
        /**
         * Partitions the array.
         * 
         * @param intArray
         * @param left
         * @param right
         * @param pivot
         * @return 
         */
        static int partition(int[] array, int left, int right, double pivot) {
        int lPointer = left;
        int rPointer = right - 1;
     
        while (true) {
          while (array[++lPointer] < pivot)
            ;
          while (array[--rPointer] > pivot)
            ;
          if (lPointer >= rPointer)
            break;
          else
            swap(array, lPointer, rPointer);
        }
        swap(array, lPointer, right - 1);
        return lPointer;
      }
     
        /**
         * Swaps elements within the array.
         * 
         * @param array
         * @param index1
         * @param index2 
         */
        static void swap(int[] array, int index1, int index2) {
        int temp = array[index1];
     
        array[index1] = array[index2];
        array[index2] = temp;
      }
     
     
    }

    It lists the sorted arrays of N = 64, 128, and 256 but after that is when I start having issues. Is it a continuous loop or something else that is bogging it down?

    The output is supposed to look something like this:

    Sorted Array of 64:[*,*,*,*]
    Sorted Array of 128:[*,*,*,*]
    Sorted Array of 256:[*,*,*,*]

    N Comp
    64 *
    128 *


    Any help would be highly useful

    Thanks


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,949
    Thanks
    56
    Thanked 2,353 Times in 2,324 Posts

    Default Re: QuickSort Help

    Can you explain what the problem is?
    that is bogging it down
    My suggestion is to try debugging the code by adding println() statements to show where the execution goes and how the values of variables change as the code is executed. The System currrentTimeMillis() method is useful for computing how long a section of code took to execute.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Feb 2013
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: QuickSort Help

    The problem is that it takes roughly 25-30 min for the program to finish running. That's what I meant by bogging it down. I'm confused on whats going on within the quickSort method that's causing such a delay?

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    21,949
    Thanks
    56
    Thanked 2,353 Times in 2,324 Posts

    Default Re: QuickSort Help

    Some suggestions;
    Use a seed value in the Random class's constructor so the same sequence of numbers is generated while debugging.
    Pick ONE array size that has enough elements to show the problem and work with that while debugging. That will reduce the debug output.
    Add printlns to show where the time is being spent. Use times of execution (See post#2) or the counts to see where the code is executing too much.
    If you don't understand my answer, don't ignore it, ask a question.

  5. The Following User Says Thank You to Norm For This Useful Post:

    3sbwya (March 27th, 2013)

Similar Threads

  1. Help me, java quicksort!
    By Joeyeyey in forum What's Wrong With My Code?
    Replies: 7
    Last Post: January 30th, 2013, 10:11 AM
  2. Stackoverflow Recursive quicksort
    By IHeartProgramming in forum Algorithms & Recursion
    Replies: 2
    Last Post: September 23rd, 2012, 02:42 PM
  3. Quicksort
    By wholegrain in forum Java Theory & Questions
    Replies: 7
    Last Post: February 12th, 2012, 08:31 PM
  4. QuickSort method
    By D3158 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: June 15th, 2011, 10:17 PM
  5. StackOverflowError when using quicksort
    By Mathew.Williams in forum What's Wrong With My Code?
    Replies: 3
    Last Post: April 22nd, 2011, 06:24 PM