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

- Pick an element, called a Pivot, from the list.
- 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.
- 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.

- List Name
`less`

- Variable
`pivot`

- 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:

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

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;
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^{2}).

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