Arrays

Question: Given an array of n numbers. Give an algorithm for finding the element which appears maximum number of times in the array? Input: 3, 2, 1, 2, 2, 3 Output: 2 One simple and a brute force solution to this is, for each input element check whether there is any element with same value and for each occurrence, increment the counter. Each time, check the current counter with the max counter and update it if this value is greater than max counter. This we can solve just by using…

Question: Given an array of n numbers, give an algorithm for checking whether there are any duplicated elements in the array or not? Input: 4, 8, 15, 16, 23, 42 Output: NO Input: 4, 8, 4, 15, 23, 42 Output: YES Another possible and better way to solve this problem based on a certain condition. Let us assume that the array elements are positive numbers and also all the elements are in the range 0 to n-1. For each element A[i], go to the array element whose index is A[i].…

Question: Given an array of n numbers, give an algorithm for checking whether there are any duplicated elements in the array or not? Input: 4, 8, 15, 16, 23, 42 Output: NO Input: 4, 8, 4, 15, 23, 42 Output: YES Now the question arises, if we can improve the complexity of the above problem. We discussed the most basic method to find duplicates here. The time complexity can be improved by sorting the given array. After sorting, all the elements with equal values come adjacent to each other. Now,…

Question: Given an array of n numbers, give an algorithm for checking whether there are any duplicated elements in the array or not? Input: 4, 8, 15, 16, 23, 42 Output: NO Input: 4, 8, 4, 15, 23, 42 Output: YES This is one of the simplest problems. One obvious solution to this is, exhaustively searching for duplicated elements in the array. That means, for each input element check whether there is any element with the same value. This we can solve by using two simple for loops. The code…

Binary Search only works when your input list of elements is already sorted. This is main and the most important condition for this search algorithm. Unlike Linear Search, we take advantage of the sorted nature of the array. We always search in the middle portion of the array. Working of Binary Search: Let us say we have this sample array. Note that this array is sorted. I want to search for the element 12 in this array. One way, I can proceed is by dividing the array in 2 halves.…

Iterative way: 1) Initialize start and end indexes. start = 0, end = n-1 2) In a loop, swap arr[start] with arr[end] and change start and end as follows. start = start +1; end = end – 1 Time Complexity: O(n) Recursive Way: 1) Initialize start and end indexes start = 0, end = n-1 2) Swap arr[start] with arr[end] 3) Recursively call reverse for rest of the array. Time Complexity: O(n)

Counting sort is not a comparison sort algorithm. The sorting techniques that work on comparison are: Selection Sort Bubble Sort Insertion Sort Merge Sort Quick Sort The best time complexity you can achieve in any of these sorting techniques is . However, is some very specific cases, you can achieve an even faster computation time of . This is made possible by an assumption. We assume that the input data set is within a finite limit. For example, if you want to sort some characters of the English alphabet. You…

Shell sort (also called diminishing increment sort) was invented by Donald Shell. This sorting algorithm is a generalization of insertion sort. Insertion sort works efficiently on input that is already almost sorted. In insertion sort, comparison happens between the adjacent elements. At most 1 inversion is eliminated for each comparison done with insertion sort. The variation used in shell sort is to avoid comparing elements until the last step of the algorithm. So, the last step of shell sort is to avoid comparing adjacent elements until the last step of…

This algorithm is one of the specific ones people generally have a problem to understand. We will try out best to simplify it and understand it.Basically quick sort comprises of these steps:- Choose a pivot element (it can be any random element in array) In one iteration keep all the numbers smaller to it on the left side and larger to it on the right side.(smaller numbers)_ _ _[PIVOT]_ _ _(larger numbers) Now we have the left sub-array of (small numbers) and the right sub-array (large numbers) Repeat steps 1…

Merge Sort is one of the most popular methods of sorting an array and as offers a constant operating time of . And, as the name suggests it involves merging of several sorted arrays to combine and form a single sorted arrays in the end. The steps involved in merge sort are:- Divide the array in 2 parts left and right. Now recursively divide the left and right parts into more left and right sub parts. Keep doing step 2 , until the sub parts are no greater than a…