Sorting – Set 3

Sorting, Sorting Set 1, Sorting Set 2

  1. [Merge Sort] Sort array after converting elements to their squares Given a array of both positive and negative integers ‘arr[]’ which are sorted. Task is to sort square of the numbers of the Array. GFG
    Algo:
    1. Efficient solution is based on the fact that given array is already sorted.Divide the array into two part “Negative and positive “. Use merge function to merge two sorted arrays into a single sorted array.
    Time complexity: O(n) space complexity: O(n)
    2. Sort the array.  Time complexity : O(n log n)
  2. [Merge Sort] Sort an array when two halves are sorted Given an integer array of which both first half and second half are sorted. Task is to merge two sorted halves of array into single sorted array. GFG 
    Algo:
    1.Sort the complete array. Time Complexity O(nlogn)
    2.
     An efficient solution is to use an auxiliary array one half. Now whole process is same as the Merge Function of Merge sort.Time Complexity : O(n)
  3. ***** [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. Enhance Merge Sort. Time Complexity: O(nlogn)
    Similar: Find Surpasser Count of each element in array. GFG
  4. [Comparator] Sort an array of integer where the integer are very large and they need to be stored at string. Code
    Similar: 
    Given an array of dates, how to sort them.
    and Sort an array according to count of set bits
    Both of these make use of Comparator along with default built in sort method.

  5. *** Sort an array of 0s, 1s and 2s Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last. GFG
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s