Hello, In this article I will discuss one of the very good example of recursive programming. This is the quick sort algorithm where we sort the input list of the elements by divide and conquer technique. The code for the explanation of the article is written in C#. But it is very easily understandable and can be written in any programming language.
In my one of the previous article I have discussed about bubble sort in C#.
Most of the article I have found on the web only show how to do quick sort. And their implementation is very complex. To understand quick sort we should first understand about it. In the below figures I will discuss about it with clear and simple explanation. Then we will look at the programming side of the same explanation.
Quick Sort Explanation
First things first, Let start with the understanding of the quick sort algorithm.
Suppose I have list of the characters as B, A, C, D, F, E. I want to sort this list. Check the below figure.
Step 1: As this algorithm is based on the divide and conquer technique. We will divide this list in two smaller lists. The lists will be created based on the pivot in the parent list. A pivot is a randomly selected item from the parent list. In this figure suppose the pivot is element D.
Now all the elements smaller than D will come to the left list and greater then D go to right list.
This process will continue unless and until we have only one element left in the list.
Step 2: Now as we can see in the figure 2. There are only pivots left out of the whole list. And it is a tree kind of structure. With a node having maximum of two child nodes.
Step 3: We will start from the bottom of the tree. The left children of the node are prefixed to the parent node and right children are suffixed. And thus we will get a fully sorted list as shown in the figure.
And the code for the above explanation is shown below
public List<char> Sort(List<char> charList)
{
if (charList.Count <= 1)
return charList;
int[] sortedList = new int[charList.Count];
Random ran = new Random();
int pointer = ran.Next(0, charList.Count - 1);
//select a pivot from the list based on the random number.
char pivot = charList[pointer];
//Create two lists for each pivot.Left list will contain the lesser items and right list
//will contain all the grater items then pivot
List<char> leftList= new List<char>();
List<char> rightList = new List<char>();
foreach (var item in charList)
{
if (item < pivot)
leftList.Add(item);
else if (item > pivot)
rightList.Add(item);
}
//Call the same method recursively unless we have one items left in each left and right
//side
var mergedSolution = Sort(leftList);
mergedSolution.Add(pivot);
mergedSolution.AddRange(Sort(rightList));
}And the above quick sort algorithm will help you to sort the character list.
I leave it to reader to make this program more generic to sort out any list.
I hope this small explanation will help out to understand quick sort and recursive programming.
Below is the list of other sorting algorithms with explanation in C#