###
Sorting Algorithms Codes in C#.NET

**Bubble Sort**
In bubble sort, each element of the unsorted list is compared to the next element and if the value of first element is greater than the value of the second element, then they are swapped.

public List<int> bubblesort(List<int> a)
{
int temp;
// foreach(int i in a)
for(int i=1; i<=a.Count; i++)
for(int j=0; j<a.Count-i; j++)
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
return a;
}

**HeapSort **
The heapSort belongs to the selection sort algorithm paradigm and it is a comparison based algorithm.

int [] heapSort(int [] numbers, int array_size)
{
int i, temp;
for (i = (array_size / 2)-1; i >= 0; i--)
siftDown(numbers, i, array_size);
for (i = array_size-1; i >= 1; i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i-1);
}
return numbers;
}

There is function shifDown which is the heart of this heapsort. This function makes the heaps and sort them.

void siftDown(int [] numbers, int root, int bottom)
{
int done, maxChild, temp;
done = 0;
while ((root*2 <= bottom) && (done==0 ))
{
if (root*2 == bottom)
maxChild = root * 2;
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
if (numbers[root] < numbers[maxChild])
{temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;}
else
done = 1;
}}

**Merge Sort**
A Merge Sort is an example of divide and conquer paradigm. It is a comparison based sorting algorithm. It takes a list and divides the list in two lists of almost equal lengths. It then sorts the list by applying merge sort recursively, which divides the divided lists into two sublists for each and applying the merge sort to them as well.

A merge sort works as follows:
If the list is of length 0 or 1, then it is already sorted.
Otherwise:
Divide the unsorted list into two sublists of about half the size.
Sort each sublist recursively by re-applying merge sort.
Merge the two sublists back into one sorted list.

public List<int> mergesort(List<int> m)
{
List<int> result = new List<int>();
List<int> left=new List<int>();
List<int> right = new List<int>();
if (m.Count <= 1)
return m;

int middle = m.Count / 2;
for(int i=0;i<middle; i ++)
left.Add(m[i]);
for (int i = middle; i < m.Count; i++)
right.Add(m[i]);
left = mergesort(left);
right = mergesort(right);
if (left[left.Count - 1] <= right[0])
return append(left, right);
result = merge(left, right);
return result;
}

## No comments:

Post a Comment