7 Basic Algorithms Every Newbie Coder Should Know: Part 2
This article is part 2 of a series covering 7 Basic Algorithms Every Newbie Coder Should Know. Here’s a look at the plan for the series:
- Algorithms Introduction: Part 1
- Searching & Sorting Algorithms: Part 2
- Two Pointer & Sliding Window: Part 3
In this article, we will be covering the most basic searching & sorting algorithms. So throughout this article, I will be using an example of 7 people with different heights standing in a straight line/row to explain the algorithms.
LINEAR SEARCH
This is one of the most basic searching algorithms with a time complexity of O(n) for worst-case and O(1) for the best case.
Definition : In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.
So let’s understand this algorithm with a real-world example. As we knew we have 7 people with different heights standing in a row in random order & let the height of the people be 180, 140, 170, 160, 190, 130, 150 in centimeters & and let the people be named P1, P2, ….. P7 respectively. If we would like to find a person with a height of 160 cm, we can utilize linear search here. We begin to pass the row of individuals and ask every person their individual height and if it is equal to 160 cm we may provide back the person’s position or name and we can return a zero value if nobody exists. In this scenario, we are going to ask each person about his or her height and we will know by the time we come to P4 that this is a person with 160 cm in height. Below is the pseudo-code for a linear search and I hope you will try and implement it in your preferred programming language.
Step 1. Take Input of the array and x.Step 2. Start from the leftmost element of list/array and one by one compare x with each element of array/list.Step 3. If x matches with an element, return the index.Step 4. If x doesn’t match with any of elements, return -1.
BINARY SEARCH
Binary Search is a searching algorithm for finding an element’s position in a sorted array. In a nutshell, this search algorithm takes advantage of a collection of elements being already sorted by ignoring half of the elements after just one comparison.
Definition : In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.
Let’s Now understand the Binary Search with the same example that we used to understand Linear Search but before that let’s see the prerequisites of Binary Search; unlike the linear search where elements could be any order, the array in binary search must be sorted. This is the only prerequisite of the binary search.
1. Let us consider the people are standing in a row in such a way.
2. Let x = 4 (P4)be the person to be searched.
3. Set two pointers low and high at the first and the last element respectively.
4. Find the middle element mid of the array ie. arr[(low+high)/2] = 160.
5. If x == mid, then return mid. Else, compare the element to be searched with m.
6. If x > mid, compare x with the middle element of the elements on the right side of mid. This is done by setting low to low = mid + 1.
7. Else, compare x with the middle element of the elements on the left side of mid. This is done by setting high to high = mid-1.
8. Repeat these steps until low meets high. We found P4.
This searching technique is faster and easier to implement, requires no extra space & reduces the time complexity of the program to a greater extent. The time complexity for the worst case is O(nlogn). The Pseudo Code for this algorithm is given below, I hope you will implement the algorithm in your preferred language.
Step 1. Let the element we are searching for, in the given array/list is X.Step 2. Compare X with the middle element in the array.Step 3. If X matches with the middle element, we return the middle index.Step 4. If X is greater than the middle element, then X can only lie in the right (greater)half subarray after the middle element, then we apply the algorithm again for the right half.Step 5. If X is smaller than the middle element, then X must lie in the left (lower) half , this is because the array is sorted. So we apply the algorithm for the left half.
SORTING
Sorting is a permutation of a list of elements such that the elements are either in increasing (ascending) order or decreasing (descending) order. There are many different sorting techniques. The major difference is the amount of space and time they consume while being performed in the program. For now, we will be discussing the following sorting techniques:
- Selection sort
- Bubble sort
- Insertion sort
Let us now discuss these sorting techniques in detail.
SELECTION SORT
Definition : Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list. The detailed algorithm is given below.
After you’ve grasped the graphic above, I’ll describe how the Selection Sort algorithm works. I hope you got something out of the image; now I’ll break it down for you and make it extremely simple to understand. We start by assuming that the first bar (3) in the graph has the smallest height, and then we traverse the array, comparing it to each bar, and if the height of the bar is smaller, we make it the new minimum, and at the end of the graph, we will have the bar with the smallest height (2), which we will swap with the first bar, resulting in the smallest bar at the first position in the graph.
We’ll start with the second bar (44) as our minimum for the following iteration because the first bar is already sorted and in the correct location, and we’ll repeat the processes. We need to do n-1 iterations to fully sort the graph, where n is the number of elements/bars. The pseudocode for the same is provided below I hope you will try to implement the same in your preferred programming language.
Step 1 − Set MIN to location 0Step 2 − Search the minimum element in the listStep 3 − Swap with value at location MINStep 4 − Increment MIN to point to next elementStep 5 − Repeat until list is sorted.
BUBBLE SORT
Definition : Bubble sort, also known as sinking sort, is a basic sorting algorithm that iterates through a list, comparing neighboring elements and swapping them if they are out of order. The list is sent through again and again until it is sorted. The comparison sort method is named from the manner that smaller or larger components “bubble” to the top of the list. This simplistic method performs badly in real-world situations and is mostly used as a teaching aid.
After you’ve grasped the graphic above, I’ll describe how the Bubble Sort algorithm works. I hope you got something out of the image; now I’ll break it down for you and make it extremely simple to understand. We begin by traversing the graph/list and comparing every neighboring member, swapping them if they are out of order, and by the conclusion of our first iteration, we will have the largest element at the end.
For the following iteration, we’ll start with the first element and repeat the comparing and swapping procedure, but this time we’ll only go to the second last element because the last element has already been sorted and is in the correct position. To sort a list, we must perform this n-1 times, similar to selection sort where n stands for the number of elements in the list.
Below you can find the pseudo-code for the same and I hope you’ll implement it in your preferred programing language.
Step 1. In first cycle, Start by comparing 1st and 2nd element and swap if 1st element is greater. After that do the same for 2nd and 3rd element. At the end of cycle you will get max element at the end of list.Step 2. Now do the same in all subsequent cycles.Step 3. Perform this for (number of elements – 1) times.Step 4. You will get sorted list.
INSERTION SORT
Definition : Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages. Insertion sort is a sorting algorithm that builds a final sorted array (sometimes called a list) one element at a time. Insertion sort has an average and worst-case running time of O(n²) , O(n) , so in most cases , a faster algorithm is more desirable.
After you’ve grasped the graphic above, I’ll describe how the Insertion Sort algorithm works. I hope you got something out of the image; now I’ll break it down for you and make it extremely simple to understand.
Insertion Sort works in the similar way we sort cards in our hand during a game of cards. Assume the numbers in the graphic above are in your right hand, and you want to sort them; so you pick the leftmost card from the right and place it in your left hand. We can say the list on the left hand is sorted because there is only one card present & now we’ll again pick the leftmost card from the right hand and compare it with the only card in our left hand, and after comparison, we’ll place it in order. Then we’ll take the leftmost card from the right hand and compare it to all of the other cards in the left hand, placing it accordingly, until we have three cards in sorted order in our left hand, and we’ll repeat these processes until we don’t have any cards left in our right hand. Below you will find the pseudo-code for Insertion Sort & I hope you will implement it in your preferred programming language.
Step 1: Iterate through the array from arr[1] to arr[n].Step 2: Compare the current element (key) to the one that came before it.Step 3: Compare the essential element to the elements that came before it if it is smaller , To make room for the switched element, move the larger elements up one position.
Overview: We learned about two basic searching algorithms and three basic yet highly helpful sorting algorithms in this part of the series “7 Basic Algorithms Every Newbie Coder Should Know,” which will assist you out in problem-solving in the themes array/list, linked list, string, and so on.
We’ll learn about two really intriguing algorithms called Sliding Window and Two Pointer in the next and last section of this series. I hope you’re all as excited as I am.
Editors Note : First of all thankyou for reading the article till the end I hope you all have learned something new.
