Results 1 to 3 of 3
  1. #1
    Teareal is offline Member
    Join Date
    Mar 2013
    Posts
    2
    Rep Power
    0

    Default Quick Sort Algorithm

    Hey all, I am new to this forum and hoping that I can find my answer here.
    I am assigned with finding the number of swaps that are occurring on an unsorted array using the quick sort algorithm. My problem is that I can not figure out where to place my accumulator (swapCount) to keep up with the count and then only show the final count in my System.out.printlin statement.
    The following is a copy of the code that I am using, without the swapCount variable in it because I am not sure where to put it.

    Java Code:
    public class IntQuickSorter
    {
      /**
          The quickSort method calls the doQuickSort method
          to sort an int array.
          @param array The array to sort.
       */
       
       public static void quickSort(int array[])
       {
          doQuickSort(array, 0, array.length - 1);
       }
    
       /**
          The doQuickSort method uses the QuickSort algorithm
          to sort an int array.
          @param array The array to sort.
          @param start The starting subscript of the list to sort
          @param end The ending subscript of the list to sort
       */
       
       private static void doQuickSort(int array[], int start, int end)
       {
          int pivotPoint;
        
          if (start < end)
          {
             // Get the pivot point.
             pivotPoint = partition(array, start, end);
             
             // Sort the first sub list.
             doQuickSort(array, start, pivotPoint - 1);
             
             // Sort the second sub list.
             doQuickSort(array, pivotPoint + 1, end);
          }
       }
    
       /**
          The partiton method selects a pivot value in an array
          and arranges the array into two sub lists. All the
          values less than the pivot will be stored in the left
          sub list and all the values greater than or equal to
          the pivot will be stored in the right sub list.
          @param array The array to partition.
          @param start The starting subscript of the area to partition.
          @param end The ending subscript of the area to partition.
          @return The subscript of the pivot value.
       */
       
       private static int partition(int array[], int start, int end)
       {
          int pivotValue;    // To hold the pivot value
          int endOfLeftList; // Last element in the left sub list.
          int mid;           // To hold the mid-point subscript
    
          // Find the subscript of the middle element.
          // This will be our pivot value.
          mid = (start + end) / 2;
    
          // Swap the middle element with the first element.
          // This moves the pivot value to the start of 
          // the list.
          swap(array, start, mid);
    
          // Save the pivot value for comparisons.
          pivotValue = array[start];
          
          // For now, the end of the left sub list is
          // the first element.
          endOfLeftList = start;
          
          // Scan the entire list and move any values that
          // are less than the pivot value to the left
          // sub list.
          for (int scan = start + 1; scan <= end; scan++)
          {
             if (array[scan] < pivotValue)
             {
                endOfLeftList++;
                swap(array, endOfLeftList, scan);
             }
          }
          
          // Move the pivot value to end of the
          // left sub list.
          swap(array, start, endOfLeftList);
          
          // Return the subscript of the pivot value.
          return endOfLeftList;
       }
    
       /**
          The swap method swaps the contents of two elements
          in an int array.
          @param The array containing the two elements.
          @param a The subscript of the first element.
          @param b The subscript of the second element.
       */
       
       private static void swap(int[] array, int a, int b)
       {
          int temp;
    
          temp = array[a];
          array[a] = array[b];
          array[b] = temp;
       }
    }
    I have a test class that calls this one. If you need a copy of it too, please ask in this post.

    Thanks guys/gals

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,003
    Blog Entries
    7
    Rep Power
    20

    Default Re: Quick Sort Algorithm

    Quote Originally Posted by Teareal View Post
    My problem is that I can not figure out where to place my accumulator (swapCount) to keep up with the count and then only show the final count in my System.out.printlin statement.
    Make it a private static member variable; set it to zero in your public static quickSort( ... ) method and increment it in your swap( ... ) method.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Teareal is offline Member
    Join Date
    Mar 2013
    Posts
    2
    Rep Power
    0

    Default Re: Quick Sort Algorithm

    Thanks Jos, I actually tried that as my first attempt...and it actaully worked. I just missed that the swapCount value was being concatenated directly to the end of the line where I am printing the original array before it is sorted. I added another line stating that this is the original order of the array and when I did that, I saw that I needed to add a \n to that statement to bring it to the next line. It was a minor oversight on my part that has caused me to sit here looking at this thing for about 2 hours...what a waste when I could be playing an MMORPG, lol. Thanks again!!

Similar Threads

  1. Quick sort problem
    By fishy8158 in forum New To Java
    Replies: 0
    Last Post: 02-18-2012, 04:21 AM
  2. Need help with quick sort method
    By Get_tanked in forum New To Java
    Replies: 1
    Last Post: 03-14-2011, 09:44 PM
  3. Quick Sort explanation.
    By hawaiifiver in forum New To Java
    Replies: 4
    Last Post: 03-10-2009, 02:28 AM
  4. How to sort a list using Bubble sort algorithm
    By Java Tip in forum Algorithms
    Replies: 3
    Last Post: 04-29-2008, 08:04 PM
  5. Help with sort algorithm
    By zoe in forum New To Java
    Replies: 1
    Last Post: 08-07-2007, 06:09 AM

Posting Permissions

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