Introduction to Algorithms
When you are doing computer science engineering, you are been told to make sure you are good at data structure and algorithm. This is a quick introduction to what is an algorithm and its different types.
What is an Algorithm?
According to Google, the algorithm is
A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.
To take a real-life example such as Going to the office requires certain steps: -
- Bike to the station.
- Take the train.
- Walk to the office.
Now, this algorithm can be written in many ways according to the transport he prefers. All the different ways accomplish exactly the same goal, but each algorithm does it in a completely different way.
Similarly, algorithm in computer science is the following:-
In computer programming, there are often many different ways algorithms to do any given task. Each algorithm has advantages and disadvantages in different situations. Algorithms put the Science in computer science have to do with finding a good algorithm and when to apply them. Because you choose the algorithm based on the circumstances. To make a computer do anything, you have to write a computer program. To write a computer program, you have to tell the computer, step by step, exactly what you want it to do. The computer then “executes” the program, following each step, to accomplish the end goal.
Searching Algorithm
Not even a single day pass, when we do not have to search for something in our day to day life. Same is the life of a computer, there is so much data stored in it, that whenever a user asks for some data, computer has to search it’s memory to look for the data and make it available to the user. So there are two popular algorithm to search.
Linear Search
Linear search is an algorithm we can use to find an element in an array. The linear search algorithm works as follows. Iterate across the array from left to right, looking for a specified element. It can be clear seeing example in image.
It generates two scenarios:-
- Best case :- If the target element is at beginning of array, that's the best case scenario. So time complexity is Ω(1)
- Worst case :- If the target element is not in the array this time we get no output and computer has to go through all the entries. this is the worst case scenario. So time complexity is O(n)
//Code for linear search in C
#include<stdio.h>int main()
{
int n;
printf("Enter no of elements in array: \n");
scanf("%d", &n);
int arr[n],i;
printf("enter array elements: \n");
for (i = 0; i < n; i++)
{
scanf("%d",&arr[i]);
}
int m;
printf("Enter the element to be searched: \n");
scanf("%d", &m);for (i = 0; i < n; i++)
{
if (arr[i] == m)
{
printf("Found \n");
return 0;
}
}
printf("Not found \n");
return 1;
}
Binary Search
Binary search is an algorithm we can use to find an element inside of an array.
Unlike linear search, it requires a special condition be met beforehand,
but it’s so much more efficient if that condition is, in fact, met. Idea here is divide and conquer. We want to reduce the size of the search area by half each time in order to find a target number. This is where that condition (the array to be sorted ) comes into play. If the array is sorted we know that everything to the left of where we currently are must be lower than the value we’re currently at. And everything to the right of where we are must be greater than the value we’re currently looking at.
So we keep on dividing the array to half depending upon which half our target lies and till our target is at middle. This can be cleared with example and code given below.
//C program for binary search.
#include<stdio.h>int main()
{
int n, i;
printf("Enter no of elements in array: \n");
scanf("%d", &n);
int arr[n];
printf("enter array element in sorted order: \n");
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}int m;
printf("Enter the element to be searched: \n");
scanf("%d", &m);int start = 0;
int end = n-1;while(start <= end)
{
int mid = (start + end) / 2;
if (arr[mid] == m)
{
printf("Found at loc %d \n",mid+1);
return 0;
}
else if(m > arr[mid])
{
start = mid+1;
}
else
{
end = mid - 1;
}}
printf("Item not found\n");
return 1;
}
It generates two scenarios:-
- Best case :- The target element is at midpoint of array and so we can stop as soon as we start. So time complexity is Ω(1)
- Worst case :- If we have to repeatedly half the array and search for element due to element being at the end of the list or does not exist. So time complexity is O(log(n))
Sorting
Sorting is one place where a lot of research has been done, because computers spend a lot of time sorting lists. Here are five different algorithms that are used in sorting :-
Bubble sort
We’re actually going to be building the sorted array from right to left, largest to smallest. Once the larger element is sorted we don’t don’t have to consider it anymore.
For example :-
First thing we do is set swap counter to 0 and look every adjacent pair and sort it if needed and incrementing counter. So from above example 6 will be sorted
Repeat the same procedure by again resetting the swap counter to 0.
It generates two scenarios:-
- Best case :- If array is already sorted than we have sorted list in just one pass. So time complexity is Ω(n).
- Worst case :- If the sorted in reverse order than that’s the worst case. So time complexity is O(n²).
//Code for bubble sort
#include<stdio.h>int main()
{
int arr[10] = {55, 100, 78, 55, 89, 110, 45, 109, 41, 19};int swap = -1,i;int sorted = 0;
while (swap != 0)
{
swap = 0;
for(i=0; i < 10 - sorted - 1; i++)
{
if(arr[i]>=arr[i+1])
{
int temp = arr[i+1];
arr[i+1] = arr[i];
arr[i] = temp;
swap += 1;}
}
sorted += 1;
}
for (i = 0; i < 10; i++)
{
printf("%i ",arr[i]);
}
printf("\n");
}
Selection sort
In selection sort the basic idea is, find the smallest unsorted element and add it to the end of the sorted list. Effectively what this does is build a sorted list, one element at a time.
So , we’re gonna repeat until no unsorted elements remain. We’re gonna search through the data to find the smallest value, and then swap that value with the first element of the unsorted part. Right now, again, the entire array is the unsorted part. All of the red elements are unsorted. So we search through and we find the smallest value. And then, swap that value with the first element of the unsorted part.
Suppose for example we have this array and smallest element one and then swap it with 5 and declare one as sorted:-
It generates two scenarios:-
- Best case :- If array is already sorted than that’s the best case. We actually have to still step through every single element of the array in order to confirm that it is, in fact, the smallest element .So time complexity is Ω(n²)
- Worst case :- Well in the absolute worst case, we have to look over all of the elements of the array to find the smallest unsorted element, and we have to repeat this process n times. Once for each element of the array because we only, in this algorithm, sort one element at time. So time complexity is O(n²)
So the worst case runtime, we have to repeat a process n times, once for each of n elements. And in the best case scenario, we have to do the same.
//C program for selection sort
#include<stdio.h>
int main()
{
int arr[10] = {55, 100, 78, 55, 89, 110, 45, 109, 41, 19};
int min, i, minpos, sorted = 0, temp;
while(sorted != 10)
{
min = arr[sorted];
for (i = sorted; i < 10; i++)
{
if(arr[i] <= min)
{
min = arr[i];
minpos = i;
}
}
temp = arr[sorted];
arr[sorted] = min;
arr[minpos] = temp;
sorted++;
}
for (i = 0; i < 10; i++)
{
printf("%i ",arr[i]);
}
printf("\n");
}Insertion sort
It’s little different from selection and bubble sort. Well let’s just arbitrarily say that the first element of the array is sorted. We’re building it in place (not as we were adjusting place in other algorithm). We’re gonna go one element at a time and build it, and so the first thing we see is a one element array. And by definition, a one element array is sorted. Then we’ll repeat this process until all of the elements are sorted. Look at the next unsorted element and insert it into the sorted portion, by shifting the required number of elements out of the way.
So for example in the array let’s assume 5 is sorted:-
Now we will look at 2 and then sort 2, 5.
Notice with insertion sort, we didn’t have to go back and forth across the array. We only went across the array one time, and we shifted things that we’d already encountered, in order to make room for the new elements.
It generates two scenarios:-
- Best case :- In the best case, the array is perfectly sorted. Where we could just tack it on without having to do any shifting, we’d essentially do that. We’re not making any swaps, we’re just moving this arbitrary line between sorted and unsorted as we go. So time complexity is Ω(n)
- Worst case :- In the worst case, the array is in reverse order. You have to shift each of the n elements up to n positions, every single time we make an insertion. So time complexity is O(n²)
//C program for insertion sort.
#include<stdio.h>
int main()
{
int i,j,key,k;
int arr[10] = {55, 100, 78, 55, 89, 110, 45, 109, 41, 19};for(i=1;i<10;i++)
{
key = arr[i];
j = i - 1;
while(j >= 0 && arr[j] >= key)
{
arr[j+1] = arr[j];
j = j -1;
}
arr[j+1] = key;
}
for (k = 0; k < 10; k++)
{
printf("%i ",arr[k]);
}
printf("\n");
}
Merge sort
In merge sort, the idea of the algorithm is to sort smaller arrays and then combine those arrays together (merge them) in sorted order. It leverages something called recursion.
So for example in below first we sort first half and then second half
And so by going through this process recursively and breaking the problem down into smaller and smaller sub-arrays, sorting those, merging them together, we sort the array.
Summary
In this article we learned about a variety of sorting and searching algorithms. And sometimes it can be a little tricky to keep track of what algorithm does what. We’ve really only skimmed the surface too, there are many other searching and sorting algorithms. Here a jist of all the algorithms that we discussed to give you a quick idea whenever u are stuck.
Visit to this site to get the visual representation of how arrays are stored. https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
