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;
}
}```
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. ## Re: Quick Sort Algorithm

Originally Posted by Teareal
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

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!!

#### Posting Permissions

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