Searching Algorithms In C#

Introduction

In this article, I am going to discuss two of the most commonly-used searching algorithms in the programming world

1. Linear Search
2. Binary Search

I will be explaining the algorithms with the help of an example and will provide a C# code to execute that.

Linear Search

This algorithm will perform a sequential search of item in the given array. Every element is checked from start to end and if a match is found, the index of matched element will be returned; otherwise, -1 will be returned.

Pseudo Code for Linear Search 

procedure LinearSearch(array, value)

foreach item in array

if item == value

return the item's index

end if

end foreach

return -1

end procedure

Let us understand this with the help of an example.

Consider the array below.

If we want to determine the position of number 1 in this array, we have to traverse every element from start to end; i.e from index=0 to index = 7 and compare it with 1. We will return the position of element which matches with 1, which is 6 (index+1). Hence, the element 1 is found at position 6 in input array.

Time Complexity

Since all the array elements are compared only once with the input element, hence the time complexity of the linear search is O(N).

Binary Search

Binary search is an efficient and commonly used searching algorithm.This algorithm works only on sorted sets of elements. So if the given array is not sorted then we need to sort it before applying Binary search.

This algorithm searches a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.if found return the index of matched element , else return -1.

Pseudo Code for Binary Search

Procedure BinarySearch(array,value)

Set lowerBound = 1

Set upperBound = size of array

while (lowerBound <= upperBound)

set midPoint = (lowerBound + upperBound ) / 2

if array[midPoint] > value

set upperBound = midPoint - 1

else if array[midPoint] < value

set lowerBound = midPoint + 1

else return midPoint

end while

return -1;

end procedure

Let us understand this with the help of an example.

Referring to the image below; if we need to find the position of 2 in the given array using binary search ,

The lower bound is 0 and the upper bound is 7. The median of the lower and upper bounds is (lower_bound + upper_bound) / 2 = 3. Here array[3] = 4. The value mid element (4) is greater than the value to be found(2). Therefore, we do not need to conduct a search on any element beyond 4 as the elements beyond it will obviously be greater than 2.

Therefore, we drop the upper bound of the array to the position of element just before the mid element. Now, we follow the same procedure on the same array with the following values,

Now, the lower bound is 0 and the upper bound is 2. The median of the lower and upper bounds is (lower_bound + upper_bound) / 2 = 1. Here array[1] = 2.Hence the value of mid element matches the value to be searched.Therefore we return the position of 2 as 2.

Time Complexity

The array to be searched is reduced by half in every iteration. Hence time complexity of the Binary search is O(LogN).

Linear Search vs Binary Search

Linear Search is sequential search which scans one item at a time.The time taken to search a given element will increase if the number of elements in the array increases.

For Binary Search the input array needs to be in sorted order. It also accesses the data randomly as it always compares to the middle element of array and hence discarding the half of array in every iteration.

Linear search performs equality comparisons whereas Binary search performs ordering comparisons

Conclusion

In this article, we learned about Linear search and binary search.These can be asked in job interviews also.

You can download the source code from here

Quick Sort Algorithm In C#

Introduction

In this article, I am going to explain about the Quicksort algorithm.This is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.

This algorithm is very common in job interviews.So first, I am going to explain Quick Sort algorithm; then, I will be providing the C# code to execute it.

The Quicksort Algorithm

This Algorithm selects an element as pivot element from the given array and partitions the array around it such that, Left side of pivot contains all the elements that are less than the pivot element. The right side contains all elements that are greater than the pivot element. Let P be the index of pivot after partitioning the array. Then, the left subarray(start to P-1) and right subarray(P+1 to end) are sorted recursively to get the final sorted array as output.

Different versions of Quicksort pick pivot in different ways such as.

1. Always pick the first element as a pivot.
2. Always pick the last element as pivot
3. Pick a random element as pivot.
4. Pick median as pivot.

Selecting a pivot element reduces the space complexity and removes the use of the auxiliary array that is used in merge sort. Selecting a random pivot in an array results in an improved time complexity in most of the cases.

How the array is partitioned around pivot?

1. Assume the last element as pivot .
2. We want larger elements to go to the right and smaller to go to left. We maintain two indexes i and j, whereas i pointing to the leftmost element and j is pointing to last element(pivot).
3. While i is to the left of j, we move i right, skipping all the elements less than the pivot. If an element is found greater than the pivot, i stops
4. While j is to the right of i, we move j left, skipping all the elements greater than the pivot. If an element is found less than the pivot, j stops
5. When both i and j have stopped, the elements are swapped.
6. When i and j have crossed, no swap is performed, scanning stops, and the element pointed to by i is swapped with the pivot.

Let us understand this with the help of an example.

Let us take input array as – 9 7 5 3 10 6

The sorted output for this array is – 3 5 6 7 9 10

Step 1

Select the last element (6) as pivot element and partition the array around 6.

Step 2

After partitioning, we get the following.

Step 3

Now, we will recursively sort the left subarray (5 3).Which gives –

Step 4

Since the left subarray is now sorted, we will recursively sort the right subarray (7 10 9). The last element of right subarray (9) is selected as pivot and right subarray is partitioned around it. Which gives

Step 5

Since the left side of Pivot element(9) has only one element i.e (7) hence it is sorted. Similarly, the right side of pivot has only one element i.e (10) hence that is also sorted.

Hence, we get our sorted array using Quicksort as follows –

Time Complexity

The complexity of QuickSort depends on the selection of pivot.

The worst case time complexity of this algorithm is O(N²),if largest or smallest element is selected as pivot.

The best case occurs when the partition process always selects the middle element as pivot.This can be achieved by using random function to select pivot element.There are logN partitions, and to obtain each partitions we do N comparisons. Hence the complexity is O(NlogN).

The average case time complexity of this algorithm is also O(NLogN).

QuickSort Vs MergeSort

Quicksort in its general form is an in-place sort (i.e. it doesn’t require any extra storage) whereas merge sort requires O(N) extra storage, N denoting the array size which may be quite expensive. Allocating and deallocating the extra space used for merge sort increases the running time of the algorithm. Comparing average complexity we find that both type of sorts have O(NlogN) average complexity. For arrays, merge sort loses due to the use of extra O(N) storage space.

In case of linked lists the case is different mainly due to difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes may not be adjacent in memory. In linked list, we can insert items in the middle in O(1) extra space and O(1) time. Therefore merge operation of merge sort can be implemented without extra space for linked lists.

Conclusion

In this tutorial we learnt about the Quicksort algorithm and its implementation using C#.

You can download the source code from here

Merge Sort Algorithm In C#

Introduction

In this article, I will be discussing Merge sort algorithm. Merge sort is a comparison based sorting algorithm based on the divide and conquer approach.

The input array will be divided into subarrays and those subarrays will be further divided until each subarray contains a single element. Then, these subarrays will be merged together to get a single sorted array.

This algorithm is asked frequently in job interviews.So first, I am going to explain Merge sort algorithm. Then, I will be providing a C# code to execute it.

The Merge Sort Algorithm

This algorithm works as follows.

• Divide the unsorted array of size N into N subarrays having single element each.
• Take two adjacent subarrays and merge them to form a sorted subarray having 2 elements.Now we have N/2 subarrays of size 2.
• Repeat the process until a single sorted array is obtained.

Let us understand this with the help of an example.

Let us take input array as – 9 8 5 7 3 1

The sorted output for this array is – 1 3 5 7 8 9

As evident from the diagram below, at each step, the array of size N is being divided into 2 subarrays of size N/2 until no further division is possible.

Step 1

At first step, the array is divided into 2 subarrays (9 8 5) and (7 3 1) of size 3 each.The subarray (9 8 5) is further divided into subarrays(9 8) and (5).The subarray (9 8) is further divided into (9) and (8). Since no further division is possible so division process will stop.Similarly, the subarray  (7 3 1) from will be divided into subarrays (7 3) and (1).The subarray (7 3) is further divided into (7) and (3) and then the division process will stop.

Step 2

Since all subarrays now contain one element each, the merge process will start.Subarrays (9) and (8) will merge in sorted order to form subarray(8 9), subarrays (7) and (3) will merge to form sorted subarray (3 7). Subarrays(8 9) and (5) will merge to form sorted array (5 8 9), subarrays   (3 7) and (1) will merge to form sorted array (1 3 7).Finally, subarrays (5 8 9) and (1 3 7) will merge to produce the final sorted array (1 3 5 7 8 9).

Fig :- Pictorial representation of Merge Sort algorithm

Time Complexity

Merge sort is a recursive algorithm.The array of size N is divided into the maximum of logN parts, and the merging of all subarrays into a single array takes O(N) time. Hence in all the three cases (worst, average, best), the time complexity of Merge sort is O(NLogN).

Conclusion

In this tutorial, we learned about the Merge sort algorithm and its implementation using C#.

You can download the source code from here

Selection Sort Algorithm In C#

Introduction

In this article, I am going to explain about the Selection sort algorithm. It is an in-place comparison sorting algorithm. It is also a major question in job interviews.

So first, I am going to explain Selection Sort algorithm. Then, I will be providing a C# code to execute it.

The Selection sort Algorithm

This algorithm follows the concept of dividing the given array into two subarrays.

1. The subarray of sorted elements
2. The subarray of unsorted elements

The algorithm will find the minimum element in the unsorted subarray and put it into its correct position in the sorted subarray. Let us understand this with the help of an example.

Let us take an input array as – 8 5 7 3 1

The sorted output for this array is – 1 3 5 7 8

At nth iteration, elements from position 0 to n-1 will be sorted.

Iterations	Input Array	Sorted Array	UnSorted Array
Iteration 1	8 5 7 3 1	1	5 7 3 8
Iteration 2	1 5 7 3 8	1 3	7 5 8
Iteration 3	1 3 7 5 8	1 3 5	7 8
Iteration 4	1 3 5 7 8	1 3 5 7	8
Iteration 5	1 3 5 7 8	1 3 5 7 8

Hence, we got the sorted array in iteration 5.

Time Complexity

Every element needs to be compared to every other element and then get swapped to its correct position. After every iteration, the size of unsorted array reduces by 1.

Hence n swaps and (n*(n-1))/2 comparisons result in the complexity of Selection Sort as O(n²).

Conclusion

In this tutorial, we learned about the Selection Sort algorithm and its implementation using C#.

You can download the source code from here

Bubble Sort Algorithm In C#

Introduction

In this article, I am going to explain the Bubble sort algorithm. Bubble sort is one of the most widely used sorting algorithms by the programmers worldwide. It can be applied to any collection including array, string, numbers, or characters.

Bubble sort is very frequently asked about in job interviews. So first I am going to explain the bubble sort algorithm; Then, I will be providing a C# code to execute it.

The Bubble sort algorithm

This algorithm follows the concept of iterating through the array from the first index to the last index and comparing adjacent elements and then swapping them if they appear in the wrong order. i.e. If the next element is smaller than the current element, they are swapped.

Let us understand this with the help of an example. Let us take an input array such as – 8 5 7 3 1

The sorted output for this array is – 1 3 5 7 8

Let us see the step by step execution of the Bubble sort algorithm on the input array to get the sorted output.

1.  Iteration 1: – 8 5 7 3 1 → 5 8 7 3 1 → 5 7 8 3 1 → 5 7 3 8 1→ 5 7 3 1 8
2.  Iteration 2: – 5 7 3 1 8 → 5 3 7 1 8→ 5 3 1 7 8
3.  Iteration 3: – 5 3 1 7 8 → 3 5 1 7 8 → 3 1 5 7 8
4.  Iteration 4: – 3 1 5 7 8 → 1 3 5 7 8
5.  Iteration 5: – 1 3 5 7 8

Hence, we got the sorted array in iteration 5.

Time Complexity

Since we need to iterate the entire array for every element, the average and the worst case complexity of bubble sort is O(n²).

Conclusion

In this tutorial, we learned about the Bubble sort algorithm and its implementation using C#.

Linked List Implementation In C#

Introduction

In this article, I am going to discuss one of the most important Data Structures- Linked List.

I will be explaining about

• Linked List
• Advantage of Linked List
• Types of Linked List
• How to Create a Linked List
• Various operations on Linked list.

Source Code

Before proceeding further i would recommend to download source code from Github

What is a Linked List ?

Linked List is a linear data structure which consists of a group of nodes in a sequence. Each node contains two parts.

• Data− Each node of a linked list can store a data.
• Address − Each node of a linked list contains an address to the next node, called “Next”.

The first node of a Linked List is referenced by a pointer called Head

Advantages of Linked List

• They are dynamic in nature and allocate memory as and when required.
• Insertion and deletion is easy to implement.
• Other data structures such as Stack and Queue can also be implemented easily using Linked List.
• It has faster access time and can be expanded in constant time without memory overhead.
• Since there is no need to define an initial size for a linked list, hence memory utilization is effective.
• Backtracking is possible in doubly linked lists.

Types of Linked List

• Singly Linked List: Singly linked lists contain nodes which have a data part and an address part, i.e., Next, which points to the next node in the sequence of nodes. The next pointer of the last node will point to null.

• Doubly Linked List: In a doubly linked list, each node contains two links – the first link points to the previous node and the next link points to the next node in the sequence.The prev pointer of the first node and next pointer of the last node will point to null.

• Circular Linked List: In the circular linked list, the next of the last node will point to the first node, thus forming a circular chain.

• Doubly Circular Linked List: In this type of linked list, the next of the last node will point to the first node and the previous pointer of the first node will point to the last node.

Creating a Linked List

The node of a singly linked list contains a data part and a link part. The link will contain the address of next node and is initialized to null. So, we will create class definition of node for singly linked list as follows –

internal class Node {

internal int data;

internal Node next;

public Node(int d) {

data = d;

next = null;

}

}

The node for a Doubly Linked list will contain one data part and two link parts – previous link and next link. Hence, we create a class definition of a node for the doubly linked list as shown below.

internal class DNode {

internal int data;

internal DNode prev;

internal DNode next;

public DNode(int d) {

data = d;

prev = null;

next = null;

}

}

Now, our node has been created, so, we will create a linked list class now. When a new Linked List is instantiated, it just has the head, which is Null.The SinglyLinkedList class will contain nodes of type Node class. Hence, SinglyLinkedList class definition will look like below.

internal class SingleLinkedList {

internal Node head;

}

The DoublyLinkedList class will contain nodes of type DNode class. Hence, DoublyLinkedList class will look like this.

internal class DoubleLinkedList {

internal DNode head;

}

Various operations on Linked list

1. Insert data at front of the Linked List

• The first node, head, will be null when the linked list is instantiated. When we want to add any node at the front, we want the head to point to it.
• We will create a new node. The next of the new node will point to the head of the Linked list.
• The previous Head node is now the second node of Linked List because the new node is added at the front. So, we will assign head to the new node.

internal void InsertFront(SingleLinkedList singlyList, int new_data) {

Node new_node = new Node(new_data);

new_node.next = singlyList.head;

singlyList.head = new_node;

}

To insert the data at front of the doubly linked list, we have to follow one extra step .i.e point the previous pointer of head node to the new node. So, the method will look like this.

internal void InsertFront(DoubleLinkedList doubleLinkedList, int data) {

DNode newNode = new DNode(data);

newNode.next = doubleLinkedList.head;

newNode.prev = null;

if (doubleLinkedList.head != null) {

doubleLinkedList.head.prev = newNode;

}

doubleLinkedList.head = newNode;

}

2. Insert data at the end of Linked List

• If the Linked List is empty, then we simply add the new node as the Head of the Linked List.
• If the Linked List is not empty, then we find the last node and make next of the last node to the new node, hence the new node is the last node now.

internal void InsertLast(SingleLinkedList singlyList, int new_data)

{

Node new_node = new Node(new_data);

if (singlyList.head == null) {

singlyList.head = new_node;

return;

}

Node lastNode = GetLastNode(singlyList);

lastNode.next = new_node;

}

To insert the data at the end of a doubly linked list, we have to follow one extra step; .i.e., point previous pointer of new node to the last node.so the method will look like this.

internal void InsertLast(DoubleLinkedList doubleLinkedList, int data) {

DNode newNode = new DNode(data);

if (doubleLinkedList.head == null) {

newNode.prev = null;

doubleLinkedList.head = newNode;

return;

}

DNode lastNode = GetLastNode(doubleLinkedList);

lastNode.next = newNode;

newNode.prev = lastNode;

}

The last node will be the one with its next pointing to null. Hence we will traverse the list until we find the node with next as null and return that node as last node. Therefore the method to get the last node will be

internal Node GetLastNode(SingleLinkedList singlyList) {

Node temp = singlyList.head;

while (temp.next != null) {

temp = temp.next;

}

return temp;

}

In the above mentioned method, pass doubleLinkedList object to get last node for Doubly Linked List.

3. Insert data after a given node of Linked List

• We have to insert a new node after a given node.
• We will set the next of new node to the next of given node.
• Then we will set the next of given node to new node

So the method for singly Linked List will look like this,

internal void InsertAfter(Node prev_node, int new_data)

{

if (prev_node == null) {

Console.WriteLine("The given previous node Cannot be null");

return;

}

Node new_node = new Node(new_data);

new_node.next = prev_node.next;

prev_node.next = new_node;

}

To perform this operation on doubly linked list we need to follow two extra steps

• Set the previous of new node to given node.
• Set the previous of the next node of given node to the new node.

So, the method for Doubly Linked List will look like this.

internal void InsertAfter(DNode prev_node, int data)

{

if (prev_node == null) {

Console.WriteLine("The given prevoius node cannot be null");

return;

}

DNode newNode = new DNode(data);

newNode.next = prev_node.next;

prev_node.next = newNode;

newNode.prev = prev_node;

if (newNode.next != null) {

newNode.next.prev = newNode;

}

}

4. Delete a node from Linked List using a given key value

• First step is to find the node having the key value.
• We will traverse through the Linked list, and use one extra pointer to keep track of the previous node while traversing the linked list.
• If the node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next element from the Node to be deleted.
• Or if the node is in the middle somewhere, then find the node before it, and make the Node before it point to the Node next to it.
• If the node to be deleted is last node, then find the node before it, and set it to point to null.

So, the method for singly linked list will look like this,

internal void DeleteNodebyKey(SingleLinkedList singlyList, int key)

{

Node temp = singlyList.head;

Node prev = null;

if (temp != null && temp.data == key) {

singlyList.head = temp.next;

return;

}

while (temp != null && temp.data != key) {

prev = temp;

temp = temp.next;

}

if (temp == null) {

return;

}

prev.next = temp.next;

}

To perform this operation on doubly linked list we don’t need any extra pointer for previous node as Doubly linked list already have a pointer to previous node.so the delete method will be

internal void DeleteNodebyKey(DoubleLinkedList doubleLinkedList, int key)

{

DNode temp = doubleLinkedList.head;

if (temp != null && temp.data == key) {

doubleLinkedList.head = temp.next;

doubleLinkedList.head.prev = null;

return;

}

while (temp != null && temp.data != key) {

temp = temp.next;

}

if (temp == null) {

return;

}

if (temp.next != null) {

temp.next.prev = temp.prev;

}

if (temp.prev != null) {

temp.prev.next = temp.next;

}

}

5. Reverse a Singly Linked list

This is one of the most famous interview questions. We need to reverse the links of each node to point to its previous node, and the last node should be the head node.This can be achieved by iterative as well as recursive methods. Here I am explaining the iterative method.

• We need two extra pointers to keep track of previous and next node, initialize them to null.
• Start traversing the list from head node to last node and reverse the pointer of one node in each iteration.
• Once the list is exhausted, set last node as head node.

The method will look like this,

public void ReverseLinkedList(SingleLinkedList singlyList)

{

Node prev = null;

Node current = singlyList.head;

Node temp = null;

while (current != null) {

temp = current.next;

current.next = prev;

prev = current;

current = temp;

}

singlyList.head = prev;

}

Conclusion

We have implemented Singly Linked list and Doubly Linked list using C#. We have also performed various operations on them. Please refer to the attached code for better understanding. You will find a few more methods in the attached code such as finding middle element and searching a linked list.

Download the source code from Github