Simon Simon - 3 months ago 36
C# Question

Is this Quicksort correct?

I changed the pivot to be the first element in the array, will this Quicksort algorithm still be ok? and will the variable "l" in the data array be the first element in all the partitioning steps?

x = data[l] // pivot

thanks

public void QuickSort(int[] data)
{
QuickSort(data, 0, data.Length - 1);

}
private void QuickSort(int[] data, int l, int r)
{
int i, j;
int x;
i = l;
j = r;
x = data[l];
while (true)
{
while (data[i] < x)
{
i++;
}
while (data[j] > x)
{
j--;
}
if (l <= j)
{
int temporary = data[i];
data[i] = data[j];
data[j] = temporary;
i++;
j--;
}
if (i > j)
{
break;
}
}
if (l < j)
{
QuickSort(data, l, j);
}
if (i < r)
{
QuickSort(data, i, r);
}

}

Answer
static public int Partition(int[] numbers, int left, int right)
        {
            int pivot = numbers[left];
            while (true)
            {
                while (numbers[left] < pivot)
                    left++;

                while (numbers[right] > pivot)
                    right--;

                if (left < right)
                {
                    int temp = numbers[right];
                    numbers[right] = numbers[left];
                    numbers[left] = temp;
                }
                else
                {
                    return right;
                }
            }
        }

        static public void QuickSort(int[] arr, int left, int right)
        {
            // For Recusrion  
            if (left < right)
            {
                int pivot = Partition(arr, left, right);

                if (pivot > 1)
                    QuickSort(arr, left, pivot - 1);

                if (pivot + 1 < right)
                    QuickSort(arr, pivot + 1, right);
            }
        }

your logic is not ok try this logic understand it first it's similar to your's but a slight difference