My software development journey
Median of an array is defined as the middle element when it is sorted. The middle element is the one which divides the array into two equal halves if the array is of odd length. If the length is even, the average of two middle elements is median.For example the median of [4,3,2,5,1] is 3…
Insertion sort is also a comparison based sorting. It is also an in-place sorting algorithm i.e it does not require extra space. We can re-arrange the elements within the array itself.The algorithm works as follows. The array is divided into two parts one sorted and one un-sorted. Initially the sorted part will be empty and…
Given an array of numbers, how do you search for a number? The simplest method is to start at the first element and keep comparing until the end of the array. If it is found anywhere in the middle, return it. Otherwise we would reach the end of the array which indicates that the element in…
Fibonacci number in mathematics is defined as the sum of the two previous elements in the series. Formally this is represented as f(n) = f(n-1) + f(n-2) where f(1) = 1 and f(2) = 1. In this post we will see how to generate nth fibonacci number. The algorithm is self-explanatory from the program itself. So…
Let us consider an array of numbers sorted in ascending order which can possibly contain duplicates. How do we find the left most/first occurrence of a given number? The moment we read searching in a sorted array binary search should come to our mind. But Binary search has a limitation that it just finds out…
In some applications like card games, we need to shuffle an array of objects. In this post we will consider the problem of shuffling an array of numbers so that the same algorithm would be applicable for any type of arrays. We use the random number generator in this algorithm. Let us consider an array…
Like Bubble sort, Selection sort is also a comparison based sorting algorithm, but it uses lesser number of swappings. Selection sort works this way. In first iteration it selects the smallest element and keep it in the first place. In the second iteration it selects the next smallest element from the remaining elements and keep…
In this post we will see a simple example which explains the concept of recursion. Recursion is nothing but defining a problem in terms of itself. For example let us consider the problem of finding the sum of all the elements in an array. We can define the problem as follows. Let sum(array,n) denotes the…
Bubble sort is a comparison based sorting algorithm. It works like following. We perform series of iterations to ‘bubble up’ the elements one by one so that they form a sorted order. For example we have to sort an array [3,1,4,5,2] in ascending order, In the first iteration, the element 5 will be bubbled up…
In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder – from WikipediaFor example, the GCD of 8 and 12…