M
Meyvn
Dear microsoft.public.dotnet.languages.csharp-ers,
I'm struggling with my implementation of a QuickSort algorithm. I
believe I grasp the concept (after looking up some explanation of the
algorithm), but there seems to be something wrong with my code. Any
help would be appreciated .
Note: The items in this array are randomized.
Regards,
Meyvn.
private void Sort()
{
QuickSort(0, array.Length - 1);
}
/**************Implementation of The Quick Sort
Algorithm**************
This is an in-place, divide-and-conquer, massively recursive
sort.
Step 1. Pick an element, called a pivot, from the list.
Step 2. Reorder the list so that all elements which are less
than the pivot
come before the pivot and so that all elements
greater than the pivot
come after it (equal values can go either way).
After this partitioning, the pivot is in its final
position.
This is called the partition operation.
Step 3. Recursively sort the sub-list of lesser elements
and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one,
which are always sorted.
**********************************************************************/
private void QuickSort(int left, int right)
{
//set value of pivot to leftmost item in the array
int pivot = getrokkenGetallen
I'm struggling with my implementation of a QuickSort algorithm. I
believe I grasp the concept (after looking up some explanation of the
algorithm), but there seems to be something wrong with my code. Any
help would be appreciated .
Note: The items in this array are randomized.
Regards,
Meyvn.
private void Sort()
{
QuickSort(0, array.Length - 1);
}
/**************Implementation of The Quick Sort
Algorithm**************
This is an in-place, divide-and-conquer, massively recursive
sort.
Step 1. Pick an element, called a pivot, from the list.
Step 2. Reorder the list so that all elements which are less
than the pivot
come before the pivot and so that all elements
greater than the pivot
come after it (equal values can go either way).
After this partitioning, the pivot is in its final
position.
This is called the partition operation.
Step 3. Recursively sort the sub-list of lesser elements
and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one,
which are always sorted.
**********************************************************************/
private void QuickSort(int left, int right)
{
//set value of pivot to leftmost item in the array
int pivot = getrokkenGetallen
;
int hold_left = left;
int hold_right = right;
int temp;
//partition the list, moving from the left looking for a
value > pivot and
//moving from the right looking for a value <= pivot, if
you find a match,
//swap the values. Keep doing this until left < right
becomes false. Swap the pivot
//with array
int hold_left = left;
int hold_right = right;
int temp;
//partition the list, moving from the left looking for a
value > pivot and
//moving from the right looking for a value <= pivot, if
you find a match,
//swap the values. Keep doing this until left < right
becomes false. Swap the pivot
//with array
and you are done. Recursively sort the
subarrays
//the same way.
while (left < right)
{
//look for items smaller and larger then pivot while
left < right, if so swap.
//When we finish swap pivot with array
subarrays
//the same way.
while (left < right)
{
//look for items smaller and larger then pivot while
left < right, if so swap.
//When we finish swap pivot with array
.
while (array
while (array
<= pivot && left < right)
left++;
while (array
left++;
while (array
> pivot && left < right)
right--;
if (left != right)
{
temp = array
right--;
if (left != right)
{
temp = array
;
array
array
= array
;
array
array
= temp;
}
}
//out of the loop - we are almost done sorting this list
//all that remains is to swap array
}
}
//out of the loop - we are almost done sorting this list
//all that remains is to swap array
with pivot
temp = array
temp = array
;
array
array
= array[hold_left];
array[hold_left] = temp;
//partitioning is now complete, pivot is in its final
position,
//recursively sort the two subarrays
pivot = right;
left = hold_left;
right = hold_right;
if (left < pivot)
QuickSort(left, pivot - 1);
if (right > pivot)
QuickSort(pivot + 1, right);
}
array[hold_left] = temp;
//partitioning is now complete, pivot is in its final
position,
//recursively sort the two subarrays
pivot = right;
left = hold_left;
right = hold_right;
if (left < pivot)
QuickSort(left, pivot - 1);
if (right > pivot)
QuickSort(pivot + 1, right);
}