Author: Naveen

ShellSort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shellSort is to allow exchange of far items. In shellSort, we make the array h-sorted for a large value of h. … Continue reading Shell Sort

Comb Sort is mainly an improvement over Bubble Sort. Bubble sort always compares adjacent values. So all inversions are removed one by one. Comb Sort improves on Bubble Sort by using gap of size more than 1. The gap starts with a large value and shrinks by a factor of 1.3 in every iteration until … Continue reading Comb Sort

Tim Sort is a sorting algorithm based on Insertion Sort and Merge Sort. A stable sorting algorithm works in O(n Log n) timeUsed in Java’s Arrays.sort() as well as Python’s sorted() and sort().First sort small pieces using Insertion Sort, then merges the pieces using merge of merge sort. We divide the Array into blocks known … Continue reading Tim Sort

Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements and the number of possible key values are approximately the same.It requires O(n + Range) time where n is number of elements in input array and ‘Range’ is number of possible values in array. ALGORITHM: 1.Find … Continue reading Pigeonhole Sort

Cycle sort is an in-place sorting Algorithm, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array. It is optimal in terms of number of memory writes. It minimizes the number of memory writes to sort (Each value is either written zero times, … Continue reading Cycle Sort

Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the following problem.Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range. How do we sort the numbers efficiently? A simple way is to apply a … Continue reading Bucket Sort

The lower bound for Comparison based sorting algorithm (Merge Sort, Heap Sort, Quick-Sort .. etc) is Ω(nLogn), i.e., they cannot do better than nLogn.Counting sort is a linear time sorting algorithm that sort in O(n+k) time when elements are in range from 1 to k. What if the elements are in range from 1 to … Continue reading Radix Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence. Let us understand it with the help of an example. For simplicity, … Continue reading Counting Sort

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. Always pick first element as pivot.Always pick last element as pivot (implemented below)Pick a random element as pivot.Pick median as pivot. … Continue reading Quick Sort