Sorting Algorithms Codes in C#.NET

• Download source - 27.54 KB

Introduction

I have placed some sorting algorithms in one file in which a beginner can find how the different sorting techniques work.

Background

When I needed to implement these sorting algorithms, I found it difficulty to find all the techniques in one place. That's why I am publishing this tiny application which will help students and beginners.

Using the Code

Just unpack the zip file and open it in Visual Studio. Run the project. The unsorted list is predefined and you can change it by yourself or also you can make it more interactive.

QuickSort

The QuickSort works as divide and conquer. It divides the unsorted list into sublists and then sorts the individual lists.

The steps of the QuickSort are:

1. Pick an element, called a Pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

In the code, we have unsorted of type "List of integers", which will be sorted using different algorithms.

We start the coding by starting the new project of C#, select type WindowsForm and create it somewhere in your PC harddisk.

Or if you are using the project file that is given above, just download it and unpack the zip somewhere on your hardisk. Then open Visual Studio and Open Project, browse to the location where you unzip the downloaded files and open the project file.

Look at the source code. Here you will find the default using directives. In this project, I haven't included any other namespaces.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

We start the codes by starting our new namespace that is quicksort.

namespace quicksort
{
public partial class Form1 : Form{public Form1()
{
InitializeComponent();
}
}

Here we will define the unsorted list which will be used in all of our sorting algorithms.

List<int> unsorted = new List<int> { 9, 8, 7, 6 };

In our button1_Click event, we call our quicksort function which then returns the sorted list in the result list. The showsort function will then display the sorted list.

private void button1_Click(object sender, EventArgs e)
{
List<int> result = new List<int>(quicksort(unsorted));
showsort(result);
}

List<int> unsorted = new List<int> { 9, 8, 7, 6 };

The quicksort function starts its work by selecting a random value from the unsorted list, this value is called the pivot value. Then we remove the pivot value from the unsorted list. Now each element x in the unsorted list is compared with this pivot. We have two other lists less and greater. If any element is less than the pivot, it is placed in the less list and if it is greater than the pivot value, it is placed in the greater list. Then we call the concat function with three arguments in it.

1. List Name less
2. Variable pivot
3. List Name greater

public List<int> quicksort( List<int> a)
{
Random r = new Random();
List<int> less = new List<int>();
List<int> greater = new List<int>();
if (a.Count <= 1)
return a;
int pos =r.Next(a.Count);

int pivot = a[pos];
a.RemoveAt(pos);
foreach (int x in a)
{
if (x <= pivot)
{
less.Add(x);
}
else
{
greater.Add(x);
}
}
return concat(quicksort(less), pivot, quicksort(greater));
}

The concat function here performs a very important role, the quicksort algorithm uses the recursive approach throgh concat function.

Here concat function receives the three arguments, two lists and pivot value. We have defined a new list of integers here name sorted. It concats the less, pivot and greater all together in sorted list and then returns this sorted list to quicksort method. The quicksort method receives this sorted list and then returns the sorted list to the function which sends the unsorted list to quicksort method.

The listing of concat is:

public List<int> concat(List<int> less, int pivot, List<int> greater)
{
List<int> sorted = new List<int>(less);
sorted.Add(pivot);
foreach (int i in greater)
{

sorted.Add(i);
}

return sorted; 
}

MergeSort

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:

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

In the diagram above, we have a list and it shows how the merge sort works.

In the function mergesort, we provide the list of integers named m to the mergesort function in our project. We have the other two lists defined in the function named right and left. The result list will have the sorted list which will then return by this function.

We start by looking the length of the m list. If the length of the m will equal or less than 1, it means the list is already sorted and we return this list to the calling function. If not, then we will get the middle by dividing the length of the given m list by 2. For example, if the length will be of 5 elements, the m will have the value of 2. Similarly if the elements of m list will be 4 in numbers, then the middle will have the value of 2 as well. Actually the Integer part of the length/2 will be given to the middle. 5/2= 2.5 and hence 2 will assign to middle.

We divide the list from this middle into two sublists. Assign the items to the left which are on the left of the middle point of m and assign the items to the right which are on the right of the middle point of m.

left = mergesort(left);

right = mergesort(right);

By using the recursion at this point, we pass the left and right list to the mergesort method and get the sorted list back to these lists.

Once we have received the sorted list in left and right, we compare the lists to conclude which list should be at the left hand side and which list should be at the right hand side in the result. If the sorted lists are already in order, we call the append function.

if (left[left.Count - 1] <= right[0])

return append(left, right);

The listing of mergesort is:

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

The append function does nothing else than to concat the given lists in arguments in the same order as they are given.

public List<int> append(List<int> a, List<int> b)
{
List<int> result = new List<int>(a);
foreach (int x in b)
result.Add(x);
return result;
}

If the subdivided lists were not in order, then we call the merge function here. The Merge function takes two lists in its argument, here in the code list a and list b. Another list s is defined which will hold the sorted list. It compares the first element of two lists. We will add the shortest element in s list and remove that element from the list.

s.Add(a[0]);
a.RemoveAt(0);

When this comparison is over, we will place the remaining element from the list in which we have more elements to s list and return this list to the mergesort method.

The code of merge method:

public List<int> merge(List<int> a,List<int> b)
{
List<int> s = new List<int>();
while (a.Count > 0 && b.Count > 0)
{

if (a[0] < b[0])

{ 
s.Add(a[0]);
a.RemoveAt(0);
}
else
{
s.Add(b[0]);
b.RemoveAt(0);
}

while (a.Count >0)

{s.Add(a[0]);

a.RemoveAt(0);
}

HeapSort

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

The Heapsort works as a recursive fashion. It makes the heap of the given data and then sorts that heaps.

In the code of the heapsort, we have the heapsort method which receives an array numbers and the variable array_size which has the length of this array.

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.

The shiftDown ensures that the root of the heap contains the largest element then its predecessor. If it is, then its ok otherwise it swap the elements to make it sort and then sends the result to the heapsort function.

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

Bubble Sort

The bubble is the very common technique for beginners. It is easy to implement and understand. 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.

The same is applied again and again until every element gets compared with the whole list.

The result may have ascending or descending sorted elements.

The bubble sort consists on the passes. The number of passes depends on the number of elements in the list. More elements means more passes.

The codes of the bubble sort are very easy write and understand. It consists of the two loops - a main loop and a nested loop. The main loop describes the number of passes and the nested loops defined the number of comparisons. The listing is:

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

The bubblesort is easy to implement but it is a slow sorting algorithm. It traverses each and every element of the unsorted list in every case. That's why it has the worst case and average case complexity as 0(n²).

Points of Interest

Sources: Pictures used in this article have been taken from en.wikipedia.com.

I wish this could be the helpful for beginners and information seekers. You may contact me at jibran82@hotmail.com.