Category Archives: Arrays

View algorithms on Arrays

Binary Search

Let us consider the problem of searching a word in a dictionary, in general we directly go to some approximate page [say, middle page] start searching from that point. If the name that we are searching is same then we are done with the search. If the page is before the selected page then we apply the same… Read More »

Unordered Linear Search

Let us assume that given an array whose elements order is not known. That means the elements of the array are not sorted. In this case if we want to search for an element then we have to scan the complete array and see if the element is there in the given list or not. This requires to… Read More »

Write a program to reverse an array.

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]… Read More »

Radix Sort

Similar to Counting Sort and Bucket sort, this sorting algorithm also assumes some kind of information about the input elements. Suppose that the input values to be sorted are from base d. That means all numbers are d-digit numbers. In radix sort, first sort the elements based on last digit [least significant digit]. These results were again sorted… Read More »

Bucket sort.

As similar to Counting Sort, Bucket sort also imposes restrictions on the input to improve the performance. In other words, Bucket sort works well if the input is drawn from fixed set. Bucket sort is the generalization of counting sort. For example, suppose that all the input elements from [0, 1, ……, K-1] , i.e. the set of… Read More »

Counting Sort

Counting sort is not a comparison sort algorithm and gives O(n) complexity for sorting. To achieve O(n) complexity, counting sort assumes that each of the elements is an integer in the range of 1 to K, for some integer K. When K = O(n), the counting sort works in O(n) time. The basic idea of counting sort is… Read More »