Insertion Sort Algorithm
Its a kind of incremental insertion technique, where the algorithm build up…
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.
Its a kind of incremental insertion technique, where the algorithm build up…
Problem Statement You are given an n x n 2D matrix representing an image, rotate…
Problem Implement an algorithm to determine if a string has all the characters…
Problem Statement Given two strings s and t , write a function to determine if t…
Problem Statement Given n non-negative integers a1, a2, …, an , where each…
Problem Statement Given a linked list, remove the n-th node from the end of list…
Introduction Strapi is a backend system provides basic crud operations with…
Introduction I had to create many repositories in an Github organization. I…
Introduction I was trying to download some youtube videos for my kids. As I have…
Introduction In this post, we will explore some useful command line options for…
Introduction In this post, we will see how we can apply a patch to Python and…
Introduction We will introduce a Package Manager for Windows: . In automations…