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;

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

    return i;
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: Logo

You are commenting using your 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: