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
Searching Algorithms : Linear SearchBinary SearchJump SearchInterpolation SearchExponential SearchSublist Search (Search a linked list in another list)Fibonacci SearchThe Ubiquitous Binary SearchRecursive program to linearly search an element in a given arrayRecursive function to do substring searchUnbounded Binary Search Example (Find the point where a monotonically increasing function becomes positive first time) Sorting Algorithms: Selection SortBubble … Continue reading Searching and Sorting Algorithms
Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element. What is Binary Heap?Let us first define a Complete Binary Tree. A … Continue reading Heap Sort
Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges … Continue reading Merge Sort
Python, Data structures, OOPS, Big O 