Sorting

Screen Shot 2017-06-25 at 6.57.43 PM

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

  1. Topological Sort / Topological Graph – In a tennis tournament of N players every player plays with every other player. The following condition always hold –
    If player P1 has won the match with P2 and player P2 has won from P3, then Player P1 has also defeated P3. Find winner of tournament in O(N) time and O(1) space. Find rank of players in O(NlogN) time. Link. – Adobe, Amazon


  2. [Done] Selection SortGraphic – 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 and keep repeating the same thing.  We first find the smallest element in the array and place it at i=0, then search for the second smallest and then place it i=1 and so on…Since we need to find the smallest element at each step complexity is O(n^2).
    In case the array is already sorted complexity will be O(n^2).
    So at the end of the first iteration we will have the min element at the start of the array. It moves the smallest element to the front on the given array.
    Best – O(n^2)
    Average – O(n^2)
    Worst – O(n^2)
    Space – O(1)


  3. [Done] Bubble SortGraphic Code
    The idea is to start moving the largest element to the end of the array in each iteration.
    We start with i=0, then start comparing i with i+1, if i > i+1, we swap these values.
    So at the end of the first iteration we will have the max element at the end of the array.  It moves the largest element to the front on the given array.
    We keep repeating this from i=0, till all elements are sorted.
    The best case for bubble sort is O(n) when the array is already sorted.
    In the inner loop we can have a condition that keeps track whether any swap has been done or not. If no swap has been done then we can conclude that the array is sorted and we stop further check.


  4. [Done] Insertion Sort – Graphic – GFG Code
    Algo: The idea is to split the array into two part – sorted and unsorted.  To start with the first element is always sorted so we begin checking from i = 1. Now to want to move the elements from  i > 0 to this sorted part(which in the beginning has only 1 element).
    So we begin from i = 1 (i=0 has has single element), and start moving elements one by one to the correct position in the sorted part. Now while moving we will have to shift the elements to accommodate the new element. So the sorted part will grow and unsorted part will shrink by 1 in each iteration.
    Best – O(n)
    Average – O(n^2)
    Worst – O(n^2)
    Space – O(1)
    Time taken by Insertion Sort is proportional to number of inversions in an array. Check this problem. 



  5. [Done] Merge SortGraphic – GFGCode – Analysis – Time Complexity
    Stable Sorting Algo
    Divide and Conquer and Recursive
    Not in place sorting algo. Required extra space which is proportional to n.
    Best:        Θ(n log(n))
    Average: Θ(n log(n))
    Worst:     O(n log(n))
    Space:     O(n)


  6. [Done] Quick SortCodeGraphicExplanation 
    Best:        Θ(n log(n))
    Average: Θ(n log(n))
    Worst:     O(n^2)
    Space:     O(1)
    Create a pivot(we select the last element) and a partition index(start). Start the loop and move all elements smaller than the pivot to the left of partition index.
    At the end of loop swap the pivot and element at the partition index.
    So all elements to the left of pivot are smaller to it and all to the right are larger then it. Return the partition index. Now Repeat it recursively.
    [Related] *** QuickSelect
  7. [Pending] Topological sorting
    Application – Build Order
  8. Dutch national flag sorting problemSort an array of 0s, 1s and 2s.
  9. Pancake sorting: Given an an unsorted array, sort the given array. You are allowed to do only following operation on array.
    flip(arr, i): Reverse array from 0 to i
    Youtube GeeksforGeeks – O(n^2)
  10. Sort elements by frequency | Set 1  – PENDING
  11. Sort elements by frequency | Set 2 – PENDING
  12. Permute two arrays such that sum of every pair is greater or equal to K
  13. [Done] *** Counting Sort GFG Code
    Steps:
    1. We should know the range of values in the array to sort like if we are sorting a character array we will can take range as 0 – 256(there are 256 ascii characters) or in case of numbers we shd know that maximum value range. We create an array to store that count of each character at the specific index corresponding to the element in input array.
    2. To start with initialize the count of each array index as 0.
    3. Then start looping through the given array and update the count of each element in the count array created in step 1.
    4. Now we need to update the value of each index of count to that each element corresponds a position instead of count. it’s done like a[i] = a[i] + a[i-1].
    Now each element represents either the last position in the array if they exists or the position in which they would have existed.
    5. Now create an output array of size same as the input array to sort.

             output[count[arr[i]]-1] = arr[i];
                --count[arr[i]];

    These lines are should be sufficient explanation.
    6. Output  can be either the output array or overwrite the value of given array with output array.
    Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
    Auxiliary Space: O(n+k)


    Performance Analysis of Counting sort

    • Time complexity of Counting sort-
      Complexity of Counting sort for initializing the occurrence of each element in array+ Complexity for calculating sum of indexes.O(n)+O(k)=O(n+k)
      Where n will be the array length to be sorted and k will be the range i.e. the difference between the largest and the smallest element. So if the range is large then the time performance of counting sort will not be good.
    • Space complexity of Counting sort-
      As we saw counting sort generates an array of the size range. So if suppose the range is 10000. Then these many buckets would be required. So an incredible amount of memory will need to be spent if the range is large.Count sort is an integer sorting algorithm which works on keys between a given range. It is best suited for small integers set as it results into O(n+k), n being the numbers in the set and k it’s range.
  14. Find the largest multiple of 3 from array of digits  –
    Simple implementation using sorting. We know the a number is divisible by 3 if  the sum of all the digits of the number is divisible by 3. We sort all the given    number in the array and find the sum and the remainder when the sum is % by 3.
    If rem = 0, then this is the maximum number, we display the number in reverse order from sorted array(we need the maximum number).
    if rem= 1, (suppose the sum was 19), then we need to remove 1 number whose remainder was 1 or 2 number whose remainder was 2. So that the sum becomes 15 or 18. So we start looping through the sorted array one by one, finding that either of the number. If we get then we know the index of the number that shd be removed from the array to form the largest number. We loop through the sorted array from end and display the number except the index that we found shd be removed.
    if rem = 2, (suppose the sum was 20),  then we need to make sum 18 and we remove 2 no. with remainder = 1 or 1 no with remainder = 2. Rest is same.
  15. Find the largest multiple of 2, 3 and 5 – An array of size n is given. The array contains digits from 0 to 9. Generate the largest number using the digits in the array such that the number is divisible by 2, 3 and 5.
    Since the number has to be divisible by 2 and 5, it has to have last digit as 0. So if the given array doesn’t contain any zero, then no solution exists. Once a 0 is available, extract 0 from the given array. Only thing left is, the number should be is divisible by 3 and the largest of all. Which has been discussed in the above question.
  16. Sort and Queue – Sort a queue using quick sort
  17. Median in a stream of integers (running integers)
  18. **** K’th Smallest/Largest Element in Unsorted Array | Set 1 http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/
  19. Find a pair with the given difference Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n.  GFG.
    Algo:
    Hashing is an obvious solution – O(n) – time and space.
    Another way is to use sorting and then search with two pointer. Overall complexity will be O(nLogn)
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