RSS

Randomized Quick Sort in C#

22 Aug

Instead of choosing the last element of every sub array as the pivot, we choose a random element in Randomized version and swap it with the last element before partitioning.

public static void RandomizedQuickSort(int[] input, int left, int right)
{
    if (left < right)
    {
        int q = RandomizedPartition(input, left, right);
        RandomizedQuickSort(input, left, q - 1);
        RandomizedQuickSort(input, q + 1, right);
    }
}

private static int RandomizedPartition(int[] input, int left, int right)
{
    Random random = new Random();
    int i = random.Next(left, right);

    int pivot = input[i];
    input[i] = input[right];
    input[right] = pivot;

    return Partition(input, left, right);
}

The Partition method is the same.

private static int Partition(int[] input, int left, int right)
{
    int pivot = input[right];
    int temp;

    int i = left;
    for (int j = left; j < right; j++)
    {
        if (input[j] <= pivot)
        {
            temp = input[j];
            input[j] = input[i];
            input[i] = temp;
            i++;
        }
    }

    input[right] = input[i];
    input[i] = pivot;

    return i;
}
Advertisements
 
Leave a comment

Posted by on August 22, 2012 in Algorithm, C#

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: