Category Archives: Arrays

View algorithms on Arrays

Shell sort

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

Quick Sort

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

Merge Sort

This is one of the most popular methods of sorting an array and it offers a constant operating time of O(n log(n)). 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:- We divide the array in 2 parts… Read More »

How to merge 2 sorted arrays?

Question: We have 2 sorted arrays and we want to combine them into a single sorted array. Input: arr1[] = 1, 4, 6, 8, 13, 25    ||     arr2[] = 2, 7, 10, 11, 19, 50 Output: 1, 2, 4, 6, 7, 8, 10, 11, 13, 19, 50 One of the simplest ways to solve this problem would be… Read More »

Bubble Sort

Bubble sort is one of the simplest sorting algorithms and it works on the principle of swapping two elements. Think of the bubble sort as a water bubble that arises from the bottom of the ocean. As it rises up, it grows in size and its the maximum when it reaches the surface. Similarly, in bubble sort, we… Read More »

Selection Sort

As the name suggests SELECTION SORT involves selecting an element. Now the question arises, as to how should we select this element. What is the criteria? Where should we put it? All these answers are given in the algorithm for SELECTION SORT. In selection sort, what we do is:- start from the first position in the array. traverse… Read More »

Insertion Sort

This is the most generic example of a sorting algorithm, and the one which is used by one of the most naive users. Often we must have also used this algorithm in our real life examples unknowingly. One of the favorite example is:- Sorting a hand of cards This is a very common scenario and we must have… Read More »

SORTING and its types

What is sorting? Sorting is an algorithm that arranges the elements of a list in a certain order (either ascending or descending, as per the requirement). The output is simply a permutation of the input data. Why sorting? Sorting is one of the most important categories of algorithms in computer science. Sometimes sorting significantly reduces the problem complexity.… Read More »

Finding spans in an array.

Question: Find spans in an array. Given an array arr[], the SPAN s[i] of arr[i] is the maximum number of consecutive elements arr[j] immediately before arr[i] such that arr[j] <= arr[i]. Let us try to understand the question once again. This is a very common problem in stock markets to find the peaks. Spans have applications to financial… Read More »

How will you implement 2 stacks using one array?

Question: How do we implement 2 stacks using only one array? Our stack routines should not indicate an exception unless every slot in the array is used? SOLUTION: Algorithm: Start with two indexes, one at the left end and other at the right end The left index simulates the first stack and the right index simulates the second… Read More »