# Sorting

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: 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 max element at the start of the array.
Best – O(n^2)
Average – O(n^2)
Worst – O(n^2)
Space – O(1)

3. [Done] Bubble SortGraphic – O(n^2) – average case – basically move the largest to the end
see the optimization – Code
Best – O(n)
Average – O(n^2)
Worst – O(n^2)
Space – O(1)
With String – Code
The idea is to start moving the largest element one by one to the end of the array.
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. We keep repeating this from i=0, till all elements are sorted.
The best case for bubble sort is O(n). In the inner loop we can have a condition that keeps track whether any swap has been done or not. If not then we can conclude that the array is sorted and we stop further check.

4. [Done] Insertion Sort – Graphic – GFG Code
Best – O(n)
Average – O(n^2)
Worst – O(n^2)
Space – O(1)
Algo: The idea is to split the array into two part – sorted and unsorted.
In selection sort we picked the smallest element and inserted at the start. He we pick the next element in the array and insert it in the correct position so that the new list being generated is sorted.
We consider that the first element(i=0) alone forms sorted list. Then we select the next element i=1, and move it the sorted part. For this we might have to shift elements in the sorted list. Repeat this till the unsorted part is over.
Time taken by Insertion Sort is proportional to number of inversions in an array. Check this problem.
Another way to present the insertion sort – Given an array of positive and negative numbers, arrange them such that all negative integers appear before all the positive integers in the array without using any additional data structure like hash table, arrays, etc. The order of appearance should be maintained. GFG

5. Merge SortGraphic – GFGCode – Analysis – Time Complexity
Stable Sorting Algo
Divide and Conquer and Recursive
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.
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
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)