Radix Sort is a sorting algorithm that processes digit-by-digit sort.
The idea is to perform the sorting from Least Significant Bit(LSD) to Most Significant Bit(MSD) with Auxillary Stable sort, where stable sort means that while sorting a particular range of numbers preserve the order of numbers which are equal
for more understanding on the topic, refer to http://en.wikipedia.org/wiki/Radix_sort
what is count sort?
a.) It is a sorting algorithm that sorts in linear time.
b.) It makes no comparisons between the elements
c.) It works as follows :
Input : A[1...n], where A[j]€ {1,2,…k}
Output : B[1...n], sorted
Auxillary Storage : C[1...k]
The algorithm
for i <– 1 to k
do C[i] <– 0
for j <– 1 to n
do C[A[j]] <– C[A[j]] + 1
for i <– 2 to k
do C[A[i]] <– C[i] + C[i-1]
for j <– n downto 1
do B[C[A[j]]] <– A[j]
C[A[j]] <– C[A[j]] -1
Analysis of algorithm
| Data structure: | Array |
| Worst case performance: | O(n + k) |
| Best case performance: | O(n + k) |
| Average case performance: | O(n + k) |
Program
package com.bundle.algos;
public class CountingSort {
public static void main(String args[]){
//int[] _array = new int[]{2,5,3,0,2,3,0,3};
//int[] _array = new int[]{2,5,3,6,1,3,0,3};
int[] _array = new int[]{4,1,3,4,3};
//int[] _array = new int[]{};
if(_array.length == 0){
System.out.println(“Array is empty”);
}else if(_array.length == 1){
System.out.println(“Just one element, array is already sorted”);
}else{
int min = _array[0];
int max = _array[0];
for(int i=1;i<_array.length;i++){
if(_array[i] <= min){
min = _array[i];
}else if(_array[i] > max){
max = _array[i];
}
}
System.out.println(“minimum = ” + min + “, maximum = ” + max + “, No. of elements = ” + _array.length + “, Range = ” + min + “-” + max);
countSort(_array,min,max);
}
}
public static void countSort(int[] A,int low,int high){
int cRange = high-low+1;
int[] C = new int[cRange+1];
int[] B = new int[A.length+1];
for(int i=0;i<=high;i++){
C[i]=0;
}
for(int j=0;j<=A.length-1;j++){
C[A[j]] = C[A[j]] + 1;
}
for(int i=low;i<= high;i++){
System.out.println(“C["+i+"] = ” + C[i]);
}
for(int j=1;j<=high;j++){
C[j] = C[j] + C[j-1];
}
for(int j=0;j<A.length;j++){
B[C[A[j]]] = A[j];
C[A[j]] = C[A[j]] -1;
}
for(int i=1;i<B.length;i++){
System.out.println(“B["+i+"] = ” + B[i]);
}
}
}
What is QuickSort?
1.) It is divide-and-conquer algorithm
2.) It sorts “in place”(like insertion sort, but not like merge-sort).
How to apply QuickSort on an array of n-emelents?
a.)Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray.
b.)Conquer: Recursively sort the two subarrays.
c.)Combine: This is a trivial step.
Key : Linear-time partitioning subroutine.
Lets check out how the partitioning subroutine works
Partitioning Subroutine
Partition(A,p,q) … A[p...q]
x <– A[p] ..here we assume pivot = A[p]
i <– p
for j <– p+1 to q
do if A[j] ≤ x
then i <– i+1
exchange A[i] <–> A[j]
exchange A[p] <–> A[i]
return i
Running time of Partitioning subroutine : θ(n) for n elements.
Now as we know the partitioning subroutine, we will write the pseudocode for Quicksort
Pseudocode
QuickSort(A,p,r)
if(p<r)
then q <– Partition(A,p,r)
QuickSort(A,p,q-1)
QuickSort(A,q+1,r)
Initial Call : QuickSort(A,1,n)
Running time of QuickSort
| Worst case performances | Θ(n2) |
| Best case performance: | Θ(nlogn) |
| Average case performance: | Θ(nlogn) comparisons |
Program
I tried to implement this in Java, feel free to use the code and let me know your inputs if this program can be improved.
package com.bundle.algos;
public class QuickSort {
public static void main(String args[]){
//int[] _array = new int[]{6,10,13,5,8,3,2,11};
int[] _array = new int[]{2,6,5,7,8,9,3,4};
if(_array.length == 0){
System.out.println(“Empty Array”);
System.exit(0);
}else if(_array.length == 1){
System.out.println(“Only one element, Array already sorted”);
}else{
quickSort(_array,0,_array.length -1);
}
for(int i=0;i<=_array.length-1;i++){
System.out.println(_array[i]);
}
}
public static void quickSort(int[] input, int p,int r){
if(p < r){
int q = partition(input,p,r);
//System.out.println(“i=” + q);
//System.out.println(“Value=” + input[q]);
quickSort(input,p,q-1);
quickSort(input,q+1,r);
}
}
public static int partition(int[] input,int p, int q){
int x = input[p];
int i = p;
for(int j = (p+1);j <= q;j++){
if(input[j]<= x){
i = i + 1;
int temp = input[j];
input[j] = input[i];
input[i] = temp;
}
}
int temp1 = input[p];
input[p] = input[i];
input[i] = temp1;
return i;
}
}
Worst cases
a.) Input sorted or reverse sorted
b.) Partition around min or max element.
c.) One side of partition always has no elements
Best cases(intuition only)
a.) Partition splits the array evenly(same as merge sort).
This was an interesting problem given to me by Dada since I am new to puzzles and algos. I am sure you would like this.
Problem
Given an unsorted array A[1...n]. There is one duplicate number in the array which you need to find out.
Solution
We already know that there are n element and there is only one duplicate number.
Lets solve this, we will take the n = 8, means there are 8 elements in array with range of 1…8. Now since there is one duplicate number the actual range of numbers will be 1….[n-1] i.e. 1..7
I assume here that many people would be aware of XOR operators, so we are going to use XOR operators to find the duplicate numbers. But just to take a quick re-cap XOR has the following property
| p | q | p + q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
What next we will do that we will calculate the XOR of the range 1…[n-1] which is 1…7 here. Lets call the result as XOR(range). Now the next thing is to calculate the XOR if the range calculated just now i.e. XOR(range) with the array elements given in the problem. Why we are doing this is because when we will caculate this the number with even occurences will go out and the the only element remaining will be the duplicate which we have to find out. Lets’ check the program now.
Program
package com.bundle.algos;
//In this kind of problems you know the range of the elements
// in this example range is 1-7 and total number of elements is 8
public class FindDuplicateInArray {
static int xorArray,dup;
public static void main(String args[]){
int[] _array = new int[]{1,2,6,3,4,5,6,7};
//int[] _array = new int[]{11,12,13,14,14,15,16};
int duplicate = findWithXOR(_array);
System.out.println(“Duplicate : ” + duplicate);
}
public static int findWithXOR(int[] input){
int xorArray=1;//,dup=0;
for(int i=2; i<=(input.length-1);i++){
xorArray = xorArray ^ i;
//System.out.println(“XOR : ” + xorArray);
}
System.out.println(“XOR Array : ” + xorArray);
for(int k=0;k<=input.length-1;k++){
xorArray = xorArray ^ input[k];
System.out.println(xorArray);
}
//System.out.println(“Duplicate : ” + dup);
return xorArray;
}
}
Complexity of the problem
This will be θ(n) which is the best part of the solution.
This solution is for a known range of 1..n. I will come up with some more generic solutions soon. 
What are Fibonacci Numbers?
Fibonacci numbers are a sequesnce of numbers in which the first number of the sequence is 0,the second number is 1, and each subsequent number is equal to the sum of previous two numbers, yielding the sequence 0,1,1,2,3,5,8,….
Recurrence Relation
Program
package com.bundle.algos;
public class FibonacciSeries {
public static void main(String args[]){
// enter the number n
int number = 20;
for(int i = 0;i<=number;i++){
int fibonacci = fibonacciSeries(i);
System.out.println(“fibonacci of ” + i + “: ” + fibonacci);
}
}
public static int fibonacciSeries(int n){
if(n == 0){
return 0;
}
else if(n==1){
return 1;
}else{
return (fibonacciSeries(n-1) + fibonacciSeries(n-2));
}
}
}
Reference : you can read more about Fibonacci series from here
package com.bundle.algos;
//Usage : binarySearch(int[] array,int array_start, int array_end,int num_to find);
public class BinarySearch {
public static void main(String args[]){
int[] _array = new int[]{1,2,3,4,5,6,7,8,9,10,11,13,14,15,17};
int number = 9;
//int[] _array = new int[]{0};
int length = _array.length;
//System.out.println("Main length :" + length);
if(number == _array[0]){
System.out.println("Number found as first element of array");
}else if(number == _array[length -1]){
System.out.println("Number found as last element of aray");
}else if(number < _array[0]){
System.out.println("Number is not in array,even less than the first element");
}else if(number > _array[length-1]){
System.out.println("Number is not in array, greater than the greatest element");
}else{
binarySearch(_array,0,(length-1),number);
}
}
public static void binarySearch(int[] input,int start,int end,int num){
if(input.length == 1){
if(num !=input[0]){
System.out.println("Only one element and number is not found");
}else if(num ==input[0]){
System.out.println("Only one element and number found at index 0 ");
}
}else{
if(end == start){
System.out.println("Here End == Start : " + end);
if(num == input[start]){
System.out.println("Number : " + num + " found when end == start at index : " + start);
System.exit(0);
}else{
System.out.println("Number : " + num + " not in array");
}
}else if(end - start == 1){
if(num == input[start]){
System.out.println("Number : " + num + " found in start when diff is 1 at index : " + start);
}else if(num == input[end]){
System.out.println("Number : " + num + " found in end when diff is 1 at index : " + end);
}else{
System.out.println("Number : " + num + " not in array");
}
}else{
int middle = ((end-start)/2) + start;
System.out.println("Start="+start+"|End="+end+"|Middle="+middle);
if(num == input[middle]){
System.out.println("Number : " + num + " found as middle element at index : " + middle );
}else if(num > input[middle]){
System.out.println("Number greater|| binarySearch(input," + (middle+1) + "," + end + "," + num + ")");
binarySearch(input,middle+1,end,num);
}else if(num < input[middle]){
System.out.println("Number lesser|| binarySearch(input," + (start) + "," + (middle-1) + "," + num + ")");
binarySearch(input,start,middle-1,num);
}
}
}
}
}
package com.bundle.algos;
public class PoweringNumber {
public static void main(String args[]){
int result = power(2,11);
System.out.println(“Result : ” + result);
}
public static int power(int number,int exp){
if(exp <0){
System.out.println(“Enter a >=0 value for exponent”);
System.exit(-1);
}
int product = 1;
if(exp == 0){
return 1;
}
if(exp == 1){
return (number*exp);
}
if(exp%2 !=0){
//product = power(number,((exp-1)/2))*power(number,((exp-1)/2))* (number*1);
product = power(number,((exp-1)/2))*power(number,((exp+1)/2));
}else{
product = power(number,(exp/2))*power(number,(exp/2));
}
return product;
}
}
Last time when I posted the mergesort program,it was almost correct but I missed the boundary value check when there is only one element in the array. I have made the neccesary changes. It is working well now.
Code:
package com.bundle.algos;
public class MergeSort {
public static void main(String args[]){
int[] _array = {7,1,4,7,8,5,4,3};
//int[] _array = {9};
if(_array.length == 1){
System.out.println(“Array already sorted “);
}
mergeSort(_array,0,_array.length-1);
}
public static int[] mergeSort(int[] array,int lo,int hi){
int low = lo;
int high = hi;
if(low == high){
int[] x= new int[]{array[high]};
return x;
}
int middle = (low+high)/2;
//System.out.println(“Low : ” + low + “High : ” + high + “Middle : ” + middle);
int[] array1 = mergeSort(array,low,middle);
int[] array2 = mergeSort(array,middle+1,high);
int[] mergeResult = merge(array1,array2);
return mergeResult;
}
public static int[] merge(int[] a1,int[] a2){
int k=0,i=0,j=0,n = a1.length+a2.length;
int[] result= new int[n];
//for(int i=0,j=0;;){
while( i<=a1.length-1 || j <=a2.length-1 && k<= n){
System.out.println(“i=” + i + ” and j=” + j + ” and k=” + k);
if(i== a1.length){
System.out.println(“i=”+i+”,i reaches end”);
while(j<=a2.length-1){
result[k]=a2[j];
j++;
k++;
}
}else if(j==a2.length){
System.out.println(“j=”+j+”,j reahces end”);
while(i<=a1.length-1){
result[k]=a1[i];
i++;
k++;
}
}
else if(a1[i] <= a2[j]){
//System.out.println(“I am in in first : a1[i]= ” + a1[i] + ” and a2[j]= ” + a2[j]);
result[k] = a1[i];
k=k+1;
i=i+1;
}else if(a1[i]> a2[j]){
//System.out.println(“I am in in second : a1[i]= ” + a1[i] + ” and a2[j]= ” + a2[j]);
result[k] = a2[j];
j = j+1;
k = k+1;
}
}
System.out.println(“After Merge : “);
for(int m=0;m<result.length;m++){
System.out.println(result[m]);
}
return result;
}
}
package com.bundle.algos;
public class MergeSort {
public static void main(String args[]){
int[] _array = {7,1,4,7,8,5,4,3};
//int n = _array.length;
//mergeSort(_array,0,_array.length – 1);
int[] a1 = {0,3,4,5,6,7,8,9};
int[] a2 = {1,2,10,11,12,13,14};
//System.out.println(“a1 length=”+a1.length+” and a2 length=”+a2.length);
//merge(a1,a2);
mergeSort(_array,0,_array.length-1);
/*for(int m=0;m<sorted.length;m++){
System.out.println(“=> ” + sorted[m]);
}*/
}
public static int[] mergeSort(int[] array,int lo,int hi){
int low = lo;
int high = hi;
if(low == high){
int[] x= new int[]{array[high]};
return x;
}
int middle = (low+high)/2;
//System.out.println(“Low : ” + low + “High : ” + high + “Middle : ” + middle);
int[] array1 = mergeSort(array,low,middle);
int[] array2 = mergeSort(array,middle+1,high);
int[] mergeResult = merge(array1,array2);
return mergeResult;
}
public static int[] merge(int[] a1,int[] a2){
int k=0,i=0,j=0,n = a1.length+a2.length;
int[] result= new int[n];
//for(int i=0,j=0;;){
while( i<=a1.length-1 || j <=a2.length-1 && k<= n){
System.out.println(“i=” + i + ” and j=” + j + ” and k=” + k);
if(i== a1.length){
System.out.println(“i=”+i+”,i reaches end”);
while(j<=a2.length-1){
result[k]=a2[j];
j++;
k++;
}
}else if(j==a2.length){
System.out.println(“j=”+j+”,j reahces end”);
while(i<=a1.length-1){
result[k]=a1[i];
i++;
k++;
}
}
else if(a1[i] <= a2[j]){
//System.out.println(“I am in in first : a1[i]= ” + a1[i] + ” and a2[j]= ” + a2[j]);
result[k] = a1[i];
k=k+1;
i=i+1;
}else if(a1[i]> a2[j]){
//System.out.println(“I am in in second : a1[i]= ” + a1[i] + ” and a2[j]= ” + a2[j]);
result[k] = a2[j];
j = j+1;
k = k+1;
}
}
System.out.println(“After Merge : “);
for(int m=0;m<result.length;m++){
System.out.println(result[m]);
}
return result;
}
}
I am learning algorithm these days and trying to inplement them in Java at the same time to get them clear from implementation aspect as well. Feel free to use the code and let me know in case any changes can make the program better.
Code:
package com.bundle.algos;
import java.util.*;
public class InsertionSort {
public static void main(String args[]){
//int[]_array = {4,3,2,1};
int[]_array = {4,5,8,7,9,0,6,3,2,1};
for(int i=0;i<_array.length;i++){
System.out.println(“Array at ” + i + “: ” + _array[i]);
}
//int[] _insertionSortedArray = insertionSort(_array);
insertionSort(_array);
}
public static int[] insertionSort(int[] _inputArray){
//int[] resultSort;
int key = 0,i=0;
for(int j=1;j<_inputArray.length;j++){
key = _inputArray[j];
i = j – 1;
while(i>=0 && _inputArray[i] > key){
_inputArray[i + 1] = _inputArray[i];
i = i – 1;
}
_inputArray[i + 1] = key;
}
for(int k=0;k<_inputArray.length;k++){
System.out.println(“After insertion sort : ” + _inputArray[k]);
}
return _inputArray;
}
}
