13,193,970 members (47,730 online)
Add your own
alternative version

#### Stats

189.9K views
7.3K downloads
123 bookmarked
Posted 5 May 2010

# Sorting Algorithms Codes in C#.NET

, 18 May 2010
 Rate this:
Please Sign up or sign in to vote.
This article has the code of QuickSort, MergeSort, BubbleSort, HeapSort

## 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(n2).

## 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.

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## About the Author

 Web Developer Pakistan
No Biography provided

 Pro

## Comments and Discussions

 First Prev Next
 HeapSort Issue Programm3r28-Sep-17 20:45 Programm3r 28-Sep-17 20:45
 source code asem aly4-May-15 6:53 asem aly 4-May-15 6:53
 hi sir Member 1145194028-Apr-15 23:19 Member 11451940 28-Apr-15 23:19
 much thanks for a clear easy to understand article zircon7472-Sep-14 3:22 zircon747 2-Sep-14 3:22
 missing element NguyenTrungK4a18-Apr-14 17:27 NguyenTrungK4a 18-Apr-14 17:27
 Sorting algorithm israrali28-Feb-14 21:51 israrali 28-Feb-14 21:51
 My vote of 5 csharpbd22-Nov-12 1:08 csharpbd 22-Nov-12 1:08
 search hornratha24-Oct-11 18:44 hornratha 24-Oct-11 18:44
 Cool... But... luisvaldez23-Aug-11 4:32 luisvaldez 23-Aug-11 4:32
 good intro to sorting article CIDev28-Oct-10 10:15 CIDev 28-Oct-10 10:15
 My vote of 5 jeff.hua20-Aug-10 4:27 jeff.hua 20-Aug-10 4:27
 Re: My vote of 5 Muhammad Jibran Khan13-Sep-10 2:23 Muhammad Jibran Khan 13-Sep-10 2:23
 My vote of 4 Simon Dufour21-Jul-10 4:28 Simon Dufour 21-Jul-10 4:28
 Re: My vote of 4 Muhammad Jibran Khan13-Sep-10 2:21 Muhammad Jibran Khan 13-Sep-10 2:21
 My vote of 5 johannesnestler21-Jul-10 3:32 johannesnestler 21-Jul-10 3:32
 Re: My vote of 5 Muhammad Jibran Khan13-Sep-10 2:13 Muhammad Jibran Khan 13-Sep-10 2:13
 Nice martyn_mcfly18-May-10 8:44 martyn_mcfly 18-May-10 8:44
 Re: Nice Muhammad Jibran Khan18-May-10 18:56 Muhammad Jibran Khan 18-May-10 18:56
 My Vote of 5 Jitendra Zaa18-May-10 2:32 Jitendra Zaa 18-May-10 2:32
 Re: My Vote of 5 Muhammad Jibran Khan18-May-10 19:02 Muhammad Jibran Khan 18-May-10 19:02
 Wow... Abhishek Sur5-May-10 22:07 Abhishek Sur 5-May-10 22:07
 Reminds me the early days .. Amazing work. Should be helpful to all the beginners. 5 from me . Abhishek Sur Don't forget to click "Good Answer" if you like this Solution.Visit My Website-->www.abhisheksur.com
 Re: Wow... Muhammad Jibran Khan5-May-10 22:30 Muhammad Jibran Khan 5-May-10 22:30
 Source link is broken Tony Bermudez5-May-10 18:24 Tony Bermudez 5-May-10 18:24
 Re: Source link is broken Muhammad Jibran Khan5-May-10 19:00 Muhammad Jibran Khan 5-May-10 19:00
 Re: Source link is broken Johann Krenn5-May-10 20:53 Johann Krenn 5-May-10 20:53
 Re: Source link is broken Muhammad Jibran Khan5-May-10 21:32 Muhammad Jibran Khan 5-May-10 21:32
 Pictures source mejval5-May-10 13:35 mejval 5-May-10 13:35
 Re: Pictures source Muhammad Jibran Khan5-May-10 18:54 Muhammad Jibran Khan 5-May-10 18:54
 Multi-pass merge sort supercat95-May-10 9:14 supercat9 5-May-10 9:14
 Re: Multi-pass merge sort Muhammad Jibran Khan5-May-10 19:20 Muhammad Jibran Khan 5-May-10 19:20
 Last Visit: 31-Dec-99 18:00     Last Update: 18-Oct-17 22:37 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.171018.2 | Last Updated 18 May 2010
Article Copyright 2010 by Muhammad Jibran Khan
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid