RSS

Category Archives: C#

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

Read the rest of this entry »

Advertisements
 
Leave a comment

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

 

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

Read the rest of this entry »

 
3 Comments

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

 

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

Read the rest of this entry »

 
8 Comments

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

 

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++;
            }
        }
    }
}
 
3 Comments

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

 

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;
            }
        }
    }
}
 
Leave a comment

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

 

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;
    }
}
 
Leave a comment

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

 

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;
            }
        }
    }
}
 
Leave a comment

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