Randomized Quick Sort in C#

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);
    }
}

 

Quick Sort in C#

A simple Quick Sort implementation using C#. In this version the pivot is the last element in every sub array.

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

 

Heap Sort in C#

A simple Heap Sort implementation using C#.

public static void HeapSort(int[] input)
{
    //Build-Max-Heap
    int heapSize = input.Length;
    for (int p = (heapSize - 1) / 2; p >= 0; p--)
        MaxHeapify(input, heapSize, p);

    for (int i = input.Length - 1; i > 0; i--)
    {
        //Swap
        int temp = input[i];
        input[i] = input[0];
        input[0] = temp;

        heapSize--;
        MaxHeapify(input, heapSize, 0);
    }
}

 

Merge Sort in C#

A simple Merge Sort implementation using C#.

public static void MergeSort(int[] input, int left, int right)
{
    if (left < right)
    {
        int middle = (left + right) / 2;

        MergeSort(input, left, middle);
        MergeSort(input, middle + 1, right);

        //Merge
        int[] leftArray = new int[middle - left + 1];
        int[] rightArray = new int[right - middle];

        Array.Copy(input, left, leftArray, 0, middle - left + 1);
        Array.Copy(input, middle + 1, rightArray, 0, right - middle);

        int i = 0;
        int j = 0;
        for (int k = left; k < right + 1; k++)
        {
            if (i == leftArray.Length)
            {
                input[k] = rightArray[j];
                j++;
            }
            else if (j == rightArray.Length)
            {
                input[k] = leftArray[i];
                i++;
            }
            else if (leftArray[i] <= rightArray[j])
            {
                input[k] = leftArray[i];
                i++;
            }
            else
            {
                input[k] = rightArray[j];
                j++;
            }
        }
    }
}

 

Bubble Sort in C#

A simple Bubble Sort implementation using C#.

public static void BubbleSort(int[] input)
{
    for (int i = 0; i < input.Length - 1; i++)
    {
        for (int j = input.Length - 1; j > i; j--)
        {
            if (input[j] < input[j - 1])
            {
                //Swap
                int temp = input[j - 1];
                input[j - 1] = input[j];
                input[j] = temp;
            }
        }
    }
}

 

Selection Sort in C#

A simple Selection Sort implementation using C#.

public static void SelectionSort(int[] input)
{
    for (int i = 0; i < input.Length; i++)
    {
        int key = i;

        for (int j = i + 1; j < input.Length; j++)
        {
            if (input[j] < input[key])
            {
                key = j;
            }
        }
        //Swap
        int temp = input[i];
        input[i] = input[key];
        input[key] = temp;
    }
}

 

Insertion Sort in C#

A simple Insertion Sort implementation using C#.

public static void InsertionSort(int[] input)
{
    for (int j = 1; j < input.Length; j++)
    {
        int key = input[j];

        for (int i = j; i > 0; i--)
        {
            if (input[i - 1] > key)
            {
                //Swap
                input[i] = input[i - 1];
                input[i - 1] = key;
            }
        }
    }
}

 

Binary Search in C#

Simple iterative and recursive Binary Search implementations using C#. The int array has to be sorted before calling both methods.

public static int? IterativeBinarySearch(int[] source, int value, int left, int right)
{
    while (left <= right)
    {
        int middle = (left + right) / 2;

        if (source[middle] == value)
            return middle;
        else if (source[middle] > value)
            right = middle - 1;
        else if (source[middle] < value)
            left = middle + 1;
    }
    return null;
}

 

Linear Search in C#

A simple Linear Search implementation using C#.

public static int? LinearSearch(int[] source, int value)
{
    for (int i = 0; i < source.Length; i++)
    {
        if (source[i] == value)
            return i;
    }

    return null;
}

 

Why do subtrees have size at most 2n/3

Considering the worst case running time of Max-Heapify. At page 155 of Introduction to Algorithms 3rd edition, “The children’s subtrees each have size at most 2n/3 — the worst case occurs when the bottom level of the tree is exactly half full…”. Here’s the explanation why the size is at most 2n/3.

Heap is a complete binary tree. For a Heap of n nodes and x levels in the worst case scenario(the bottom level of the tree is exactly half full), the size of right subtree is(by the formula of geometric series):

The size of left subtree is: