nikoo28

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.…

There are 3 loops in C: for, while, do-while. Here is a bit detail about them:- A while loop will always evaluate the condition first. A do/while loop will always execute the code in the do{} block first and then evaluate the condition. A for loop allows you to initiate a counter variable, a check condition, and a way to increment your counter all in one line. At the end of the day, they are all still loops, but they offer some flexibility as to how they are executed. For…

Linear Search is probably the easiest searching technique that is available in computer programming. You simply need to iterate over each element in a list sequentially and compare if it matches the element to search. Searching is a prime concept, as it gives you a starting point to your code. Even in real life, if you plan to go to a movie, a vacation or a shopping mall, the first thing you do is search for a location. Similarly, in programming you could have a search for anything. Google has…

What is Searching? In computer science, searching is the process of finding an item with specified properties among a collection of items. The items may be sorted as records in a database, simple data elements in arrays, text in files, nodes in trees, vertices and edges in graphs or may be elements of other search space. Why Searching? Searching is one of core computer science algorithms. We know that today’s computers store lot of information. To retrieve this information efficiently we need very efficient searching algorithms. There are certain ways…

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…

In C, we declare an array as:- But by simply doing this declaration, the array is assigned all junk values. There can be many cases and situations when we need to initialize all the elements to ZERO (0) before we can make any further computations. The most naive technique to initialize is to loop through all the elements and make them 0. We have 3 other simple techniques as:- 1.>  Global variables and static variables are automatically initialized to zero. If we have an array at global scope it will…