﻿ Implementation | C# Examples
03 Jul

A sorting algorithm is an algorithm that puts elements of a list in a certain order. Following sorting algorithms are used by most developer/student.

03 Jul

Merge sort is a comparison-based sorting algorithm. It is based on divide-and-conquer paradigm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

http://en.wikipedia.org/wiki/Merge_sort

Implementation and Usage:

```            int[] arr = new int
{
1, 5, 4, 11, 20, 8, 2, 98, 90, 16
};

MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine("Sorted Values:");
for (int i = 0; i < arr.Length; i++)
Console.WriteLine(arr[i]);

//Output:
//Sorted Values:
//1
//2
//4
//5
//8
//11
//16
//20
//90
//98
```
```        private void Merge(int[] input, int left, int middle, int right)
{
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++;
}
}
}

private 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(input, left, middle, right);
}
}
```

03 Jul

Quicksort algorithm is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items.

http://en.wikipedia.org/wiki/Quicksort

Implementation and Usage:

```            int[] arr = new int
{
1, 5, 4, 11, 20, 8, 2, 98, 90, 16
};

QuickSort(arr, 0, arr.Length - 1);
Console.WriteLine("Sorted Values:");
for (int i = 0; i < arr.Length; i++)
Console.WriteLine(arr[i]);

//Output:
//Sorted Values:
//1
//2
//4
//5
//8
//11
//16
//20
//90
//98
```
```        private void QuickSort(int[] arr, int start, int end)
{
int i;
if (start < end)
{
i = Partition(arr, start, end);

QuickSort(arr, start, i - 1);
QuickSort(arr, i + 1, end);
}
}

private int Partition(int[] arr, int start, int end)
{
int temp;
int p = arr[end];
int i = start - 1;

for (int j = start; j <= end - 1; j++)
{
if (arr[j] <= p)
{
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

temp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = temp;
return i + 1;
}
```

03 Jul

Counting sort is an sorting algorithm for sorting a collection of objects according to keys that are small integers;

http://en.wikipedia.org/wiki/Counting_sort

Implementation and Usage:

```            int[] arr = new int
{
1, 5, 4, 11, 20, 8, 2, 98, 90, 16
};

int[] sortedArray = CountingSort(arr);
Console.WriteLine("Sorted Values:");
for (int i = 0; i < sortedArray.Length; i++)
Console.WriteLine(sortedArray[i]);

//Output:
//Sorted Values:
//1
//2
//4
//5
//8
//11
//16
//20
//90
//98
```
```        public int[] CountingSort(int[] array)
{
int[] sortedArray = new int[array.Length];

// find smallest and largest value
int minVal = array;
int maxVal = array;
for (int i = 1; i < array.Length; i++)
{
if (array[i] < minVal) minVal = array[i];
else if (array[i] > maxVal) maxVal = array[i];
}

// init array of frequencies
int[] counts = new int[maxVal - minVal + 1];

// init the frequencies
for (int i = 0; i < array.Length; i++)
{
counts[array[i] - minVal]++;
}

// recalculate
counts--;
for (int i = 1; i < counts.Length; i++)
{
counts[i] = counts[i] + counts[i - 1];
}

// Sort the array
for (int i = array.Length - 1; i >= 0; i--)
{
sortedArray[counts[array[i] - minVal]--] = array[i];
}

return sortedArray;
}
```

03 Jul

The simplest sorting algorithm is bubble sort. It works by repeatedly stepping through the list to be sorted. It walks from the first element to the last and compares each pair of elements and switches their positions if necessary.

http://en.wikipedia.org/wiki/Bubble_sort

Implementation and Usage:

```            int[] arr = new int
{
1, 5, 4, 11, 20, 8, 2, 98, 90, 16
};

BubbleSort(arr);
Console.WriteLine("Sorted Values:");
for (int i = 0; i < arr.Length; i++)
Console.WriteLine(arr[i]);

//Output:
//Sorted Values:
//1
//2
//4
//5
//8
//11
//16
//20
//90
//98
```
```        private void BubbleSort(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
for (int j = arr.Length - 1; j > i; j--)
{
if (arr[j] < arr[j - 1])
{
Swap(ref arr[j], ref arr[j - 1]);
}
}
}
}

private void Swap(ref int x, ref int y)
{
int temp = x;
x = y;
y = temp;
}
```