Merge Sort Algorithm
This algorithm is very efficient one, and is classic example of Divide and…
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.
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 algorithm is very efficient one, and is classic example of Divide and…
Problem Statement Given an array, rotate the array to the right by k steps…
Problem Statement You are given an array prices where prices[i] is the price of…
Max Priority Queue is a data structure which manage a list of keys(values). And…
Problem Statement Given a string, find the length of the longest substring…
Problem Statement Given a sorted array nums, remove the duplicates in-place such…
Introduction So you have a Django project, and want to run it using docker image…
Introduction It is very important to introduce few process so that your code and…
Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…
Introduction We often require to execute in timed manner, i.e. to specify a max…
Introduction In some of the cases, we need to specify namespace name along with…
Introduction In most of cases, you are not pulling images from docker hub public…