Bubble Sort Algorithm
This is kind of preliminary technique of sorting. And, this is the first…
July 16, 2019
Counting sort runs on relatively smaller set of input. Counting sort calculates, for every element in array - X, the number of elements which are lesser than - X. It then use this information to put X directly into its position in sorted array.
Selection sort takes two additional array.
Its interesting to note that this algorithm is not a comparison sort. You will not see any comparison in code. This algorithm uses elements values to index into array.
Now iterate equal to length of original array (from last index to 0):
See the code here:
public class CountSort {
private int[] arr;
public CountSort(int[] arr) {
this.arr = arr;
}
/**
* Count sort, max value-k
* @param k, the max value in array
*/
public int[] doSort(int k) {
int[] c = new int[k+1];
//count number of occurence
for (int i=0; i<this.arr.length; i++) {
c[this.arr[i]] ++;
}
//accumulate
for (int i=1; i<c.length; i++) {
c[i] += c[i-1];
}
int[] result = new int[this.arr.length];
//put the number to its designated place
for (int i=this.arr.length-1; i>=0; i--) {
result[c[this.arr[i]]-1] = this.arr[i];
c[this.arr[i]] --;
}
return result;
}
}
The algorithm runs on time complexity of O(n + k) ~= O(n) in worst/average case.
This is kind of preliminary technique of sorting. And, this is the first…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement The string “PAYPALISHIRING” is written in a zigzag pattern on…
Here are some tips while preparing for your coding interviews. 1. Do study or…
Problem Statement Given a non-empty array of integers, every element appears…
Problem Statement Given a linked list, remove the n-th node from the end of list…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…