# Sorting Set – 0

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. [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)

2. [Done] Bubble SortGraphic Code
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order ( it swaps each time the elements are not in order in the inner loop, not like selection sort, which swap at the end of the inner loop).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 end 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.
Best – O(n)
Average – O(n^2)
Worst – O(n^2)
Space – O(1)

3. [Done] Insertion Sort – Graphic – GFG Code
Algo: The idea is to split the array into two part – sorted and unsorted.  When we start the sorted part has just one element, the first one. Single element will always be 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.

4. [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)

```start 0 mid  1 end 2
[1, 10, 5, 2, 11, 7]```

5. [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

6. *** Dutch national flag sorting problemSort an array of 0s, 1s and 2s.
(1) Create a low pointer at the beginning of the array and a high pointer at the end of the array.
(2) Create a mid pointer that starts at the beginning of the array and iterates through each element.
(3) If the element at arr[mid] is a 2, then swap arr[mid] and arr[high] and decrease the high pointer by 1.
(4) If the element at arr[mid] is a 0, then swap arr[mid] and arr[low] and increase the low and mid pointers by 1.
(5) If the element at arr[mid] is a 1, don’t swap anything and just increase the mid pointer by 1.

7. Sort elements by frequency | Set 1

8. [PENDING] Sort elements by frequency | Set 2

9. [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.

10. *** 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.

11. Sort and Queue – Sort a queue using quick sort

12. [Heap] Median in a stream of integers (running integers)

13. [Heap] [Quick Select] **** K’th Smallest/Largest Element in Unsorted Array | Set 1 http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

Advertisements