Arrays

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 …

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 to copy both the arrays into a new array and then apply some sorting technique on them. But this method will not utilize the fact that both the arrays are already sorted. …

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 arrange items from smallest to the largest at the end one by one in each iteration.The algorithm for bubble sort is as follows:- We start from the bottom of the array and …

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 the remaining array to find the smallest number Swap this smallest number with the number we selected in the first place. Repeat steps 2 and 3 with the next position. Let us …

Insertion sort 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:- This is a very common scenario and we must have used it. Suppose you get a hand of cards. Our general approach is that we start scanning the cards from starting and if we find a card out of place, we remove it from there and …

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. We can use sorting as a technique to reduce the search complexity. Great research went into this category of algorithms because of its importance. These algorithms are very much used in many …

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 analysis(Example:- You might have heard a saying “STOCKS AT 52 WEEK HIGH”). The span of a stocks price on certain day, i , is the maximum number of consecutive days (up-to the …

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 stack. If we want to push an element into the first stack then put the element at left index. Similarly, if we want to push an element into the second stack then …