Results 1 to 3 of 3
Thread: Quick Sort Algorithm
- 03-17-2013, 07:51 PM #1
Member
- Join Date
- Mar 2013
- Posts
- 2
- Rep Power
- 0
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; } }
Thanks guys/gals
- 03-17-2013, 08:18 PM #2
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
- 03-17-2013, 08:27 PM #3
Member
- Join Date
- Mar 2013
- Posts
- 2
- Rep Power
- 0
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
-
Quick sort problem
By fishy8158 in forum New To JavaReplies: 0Last Post: 02-18-2012, 04:21 AM -
Need help with quick sort method
By Get_tanked in forum New To JavaReplies: 1Last Post: 03-14-2011, 09:44 PM -
Quick Sort explanation.
By hawaiifiver in forum New To JavaReplies: 4Last Post: 03-10-2009, 02:28 AM -
How to sort a list using Bubble sort algorithm
By Java Tip in forum AlgorithmsReplies: 3Last Post: 04-29-2008, 08:04 PM -
Help with sort algorithm
By zoe in forum New To JavaReplies: 1Last Post: 08-07-2007, 06:09 AM
Bookmarks