Arrays

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 integers in the interval [0, K-1]. That means, K is the number of elements in the input. Bucket sort uses K counters. The ith counter keeps track of the number of the…

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 to determine, for each input elements X, the number of elements less than X. This information can be used to place directly into its correct position. For example, if there are 10…

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 _____(small numbers)_______ and the right sub array ______(large numbers)________ Repeat the…

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 left and right Now we recursively divide the left and right parts into more left and right sub parts. This is done till the sub parts are no greater than a single…

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 form the bottom of the array…

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 this process, from position 2. Let us try to understand…

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

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…