Category: Sorting

Sorting Set 1  Sorting Set 2   ***** [Merge Sort]  Count Inversions in an array. GFG 1. For each element, count number of elements which are on right side of it and are smaller than it. Time Complexity: O(n^2) 2. [Pending] Enhance Merge Sort. Time Complexity: O(nlogn) Similar: Find Surpasser Count of each element in array. GFG… Continue reading Sorting | Set 3 →

Sorting Set 1  Sorting Set 3  We have algo for finding the largest and second largest and all. Like we can sort the array and take the last element O(nlog(n)). Or use quick select on unsorted array, but that has worst case O(n^2) complexity. So before such answer consider the situation that simple cases like largest… Continue reading Sorting | Set 2 →

Important Questions on this page - 4, 9, 10, 25, 26, 27, 28, 29 Sorting Set 2  Sorting Set 3 Given an array of n distinct elements. Check whether the given array is a k sorted array or not. A k sorted array is an array where each element is at most k distance away from… Continue reading Sorting | Set 1 →

Big O CheatSheet  *** https://en.wikipedia.org/wiki/External_sorting - used in questions like this - http://blog.gainlo.co/index.php/2016/05/10/duplicate-elements-of-an-array/ Geekforgeek.org - Problem set on sorting [Done] Selection Sort - Graphic - Code Algo: The idea is to move the smallest element to the front of the array in each iteration. We find the smallest element in the array and place it at the correct position… Continue reading Sorting | Set 0 →