*** 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 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)
- Bubble Sort – Graphic – 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)
- 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. Insertion Sort time complexity analysis
Question: Sort an array according to count of set bits. GFG
Question: k smallest elements in same order using O(1) extra space. GFG
Question: k smallest elements in same order using O(n) extra space. GFG
Question: Reorder the position of the words in alphabetical order. GFG
Question: Iterative selection sort for linked list GFG
- Merge Sort – Graphic – GFG – Code – 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]
- Quick Sort – Code – Graphic – Analysis
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
- *** Dutch national flag sorting problem/ Sort an array of 0s, 1s and 2s GFG
Similar: Segregate 0s and 1s in an array. GFG
Algo: we create 3 pointers – low, mid, high. low points to the next position where next 0 will come, high points to the position where next 2 will come.
Code –
(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.
- Sort elements by frequency.
Algo:
1. Using BST. O(nLogn) GFG
2. Use Hashing. Check code – very simple using Java 8 streams. O(n) + O(m Log m) where n is total number of elements and m is total number of distinct elements. GFG .
We insert all elements and their counts into a hash. This step takes O(n) time where n is number of elements.
We copy contents of hash to an array (or vector) and sort them by counts. This step takes O(m Log m) time where m is total number of distinct elements.
For maintaining the order of elements if the frequency is same, we use another hash which has the key as elements of the array and value as the index. If the frequency is same for two elements then sort elements according to the index
3. Sorting using comparator. GFG
- *** 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.
- Time complexity of Counting sort-
- *** Largest multiple of 3.
GFG 1 – Time Complexity: O(nLogn)
GFG 2 – Time Complexity : O(n)
The logic is same in both, it’s just that because of the constraint in the question on range of input number, we can use Counting Sort as it’s the only part that affects the complexity.
- 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.
- Sort and Queue – Sort a queue using quick sort
- You are given an array A of length N. For any given integer X, you need to find an integer Z strictly greater than X such that Z is not present in the array A. You need to minimise the value of Z. HE Code
Algo: Sort, Binary Search.
Arrays.binarySearch(arr, 1)* @return index of the search key, if it is contained in the array; * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The * <i>insertion point</i> is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or <tt>a.length</tt> if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found.
- Hacker Earth Sorting Problem, Code
- Sort an array according to count of set bits. GFG 1, GFG 2
Related: Check the most efficient way to count the number of set bit in a number. (Brian Kernighan’s Algorithm). GFG .
Time Complexity: O(logn)
The number of iteration to count the number of bits iterates equal to the number of set bit in any number.
There are floor(lg(N)) + 1 significant bits in N — that’s a base-2 logarithm.
The number of 1 bits in n is at most this. So the time will have asymptotic upper bound O(lg(N)) = O(log(N)).
So any algo to count the number of bit is O(log(N)) and not O(n).
Just for comprasion - Comparison among Bubble Sort, Selection Sort and Insertion Sort. GFG
- Flattening a Linked List. GFG
Lets Code 
Hi,
Awesome!! You got the best questions and answers for java interview. You’re doing a great job.
Thanks for sharing.
Cheers,
http://www.flowerbrackets.com/insertion-sort-in-java/
LikeLiked by 1 person