The Coding Shala

Home >> Algorithms >> Boyer Moore Voting Algorithm  In this post, we will learn what is Boyer Moore Voting Algorithm and how to implement it. Boyer-Moore Voting Algorithm The Boyer-Moore Majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space. [Wikipedia] Approach  Initially set the first element as the Majority element and count as 1 and move the pointer forward over an element[start loop from index 1] if the count is 0 then, set the current element as the Majority element and count as 1. if the current element is the same as the Majority element then increase the counter by 1. if the current element is not the same as the Majority element then decrease the element by 1. When we are done, the current Majority element is our answer. let's take an example under this. Find Majority Element Using Boyer Moore's Voting Algorithm In the given array we are going to find out the majority elemen...

Home >> Algorithms >> Selection Sort  In this post, we will learn what is Selection Sort Algorithm and how to implement Selection Sort in Java. Selection Sort Algorithm The selection sort algorithm is a sorting algorithm that sorts an array by repeatedly finding minimum element(ascending order)/maximum element(descending order) from the unsorted part and put it at the beginning of the unsorted array. This algorithm maintains two subarrays in a given array, one is sorted and the second is the remaining unsorted subarray. Working of Selection Sort Algorithm We follow the below steps to implement the Selection Sort Algorithm: Step 1. We pick the minimum element from the unsorted subarray. Step 2. Swap it with the first element of the unsorted subarray. Step 3. Now the first element of unsorted subarray becomes a part of the sorted subarray. Here is an example that explains the selection sort algorithm: Array:  64 25 12 22 11     ...

Last Updated: 27-Jan-2021 Home >> Algorithms >> Radix Sort Algorithm  In this post, we will learn what is Radix Sort Algorithm and how to implement Radix Sort in Java. Radix Sort Algorithm As we know sorting algorithms like Merge sort, Quicksort, etc is works in O(N log N) time. They can not do better than NlogN. We have another option as Counting sort that works in a linear time O(n+k) but the limitation in the range is there. We use the Radix sort algorithm when we have elements in the range from 1 to n^2. In the Radix sort algorithm, we do digit by digit sort starting from least significant digit(leftmost) to most significant digit(rightmost). We use counting sort to sort the digits because the range of these digits is less in the range of 0 to 9. Working of Radix Sort Algorithm Radix sort works by sorting the input numbers one digit at a time. let's take an example: input array->  { 127,  324, 173,  4,  38,  217,  134...

Last Updated: 27-Jan-2021 Home >> Algorithms >> Quick Sort Algorithm  In this post, we will learn what is Quick Sort Algorithm and will write a Java program for Quick Sort. Quick Sort Algorithm Quick Sort is one of the most efficient sorting algorithms. If effectively implemented quick sort algorithm is significantly faster than any of the common sorting algorithms. Like Merge Sort, Quicksort is also a classic example of the divide-and-conquer approach. Working of Quick Sort Algorithm In a quick sort algorithm, we follow the divide and conquer approach. The following are the steps used in quicksort: step 1. First, we select a value from the list, called pivot value and it divides the list into two sublists. One sublist contains all the values that are less than the pivot value, another sublist contains the values that are greater than or equal to the pivot value. This process is also called partitioning. we can choose the first/last element in the list as the ...

Last Updated: 27-Jan-2021 Home >> Algorithms >> Sliding Window Algorithm  In this post, we will learn what is Sliding Window Algorithm and how to implement it in Java. Sliding Window Algorithm What do you mean by Sliding Window? A window of fixed length can be slide over the input. The sliding window algorithm is used to reduce the time complexity by converting the nested for loops into a single for loop. Let's take an example and understand the sliding window problem. we have given an array of integers of size n and need to find the maximum sum of k consecutive elements in the array. Input array:  { 100, 200, 300, 400} k = 2 Output: 700 So how we solve this problem we start outer loop from index 0 and inner loop runs till i+k size every time and compare the maximum sum. The following is the code for this brute force approach. Java Program:  static int maxSum ( int arr [], int n , int k ) { // Initialize result ...

Last Updated: 20-Jan-2021 Home >> Algorithms >> Merge Sort Algorithm  In this post, we will learn what is Merge Sort Algorithm and how it works. We will write a Java Program for Merge Sort. Merge Sort Algorithm Merge Sort is an efficient and general-purpose sorting algorithm. It is a classic example of the divide-and-conquer algorithm. The merge sort algorithm can be divided into three steps, like all the divide-and-conquer algorithm: step 1. Divide the given unsorted list into several sublists. (Divide) step 2. Sort each of the sublists recursively. (Conquer) Step 3. Merge the sorted sublists to produce a new sorted list. (Combine) Here is an example that explains the working of the merge sort algorithm: The time complexity of Merge Sort Algorithm The time complexity of the merge sort algorithm is O(NlogN), where N is the length of the input list. Merge Sort Algorithm Java Program Java Program:  import java.util.Arrays ; //merger sort //t...

Last Updated: 20-Jan-2021 Home >> Algorithms >> Insertion Sort  In this post, we will learn what is Insertion Sort Algorithm and how it works. We will write a Java program for Insertion Sort. Insertion Sort Algorithm Insertion sort is an algorithm to sort a given array. The Insertion sort works on the principle of inserting an element at a particular position, hence known as Insertion Sort. Working of Insertion Sort Algorithm The Insertion sort works as follows: step 1. We take an element as key starts from index 1. Step 2. we compare all previous elements from the key element index if elements are greater than the key we move them to the next index. Step 3. At last, we insert a key at the index where all the previous elements are less than or equals to the key. Here is an example of the Insertion sort algorithm: Array ->   17 25 31 13 2 key 25    17 25 31 13 2 key 31    17 25 31 13 2 key 13    17 25 31...

Last Updated: 20-Jan-2021 Home >> Algorithms >> Counting Sort  In this post, we will learn what is Counting Sort Algorithm and how it works. We will write a Java program for Counting Sort. Counting Sort Algorithm Counting Sort Algorithm is an algorithm used to sort a given array. We use counting sort if given array elements are in a specific range. It works by counting the number of objects having distinct key values and using those counts we compute an item's index in the final sorted array. Working of Counting Sort Algorithm The following steps we follow for the counting sort algorithm: Step 1. We will iterate through the input once and count the number of times each item occurs. Step 2. Now we modify our count array to pre-compute where each item from the input should go. This step is a little be tricky. We add the previous sum to the current element in the count array. To get more understanding see the below example. Step 3. Now we will use our pre-com...