Monday, October 13, 2014

Alogrithm to sort a huge list of numbers in O(n) complexity in Java

A large file of numbers can be sorted in O(n) complexity by using a large bit array of the size same as the largest number in the list of numbers to be sorted. It can be done in Java using BitSet.


package com.biplav.algorithms;

import java.util.Arrays;

import com.biplav.ds.BitArray;


public class SortMillionNumbersWithGivenMax { //n+m


public static int[] sort(int[] list, int max) {
int[] sortedList = new int[list.length];
//BitSet bitSet = new BitSet(max);
BitArray bitSet = new BitArray(max);
for(int n:list) bitSet.set(n); //n
int index=0;
for(int i =0 ; i<=  max; i++) { //m
if(bitSet.get(i)) {
sortedList[index++] = i;
}
}
return sortedList;
}

public static void main(String[] args) {
int[] list = new int[]{1,2,3,4,5,9,15,18,25,7,11};
System.out.println(Arrays.toString(sort(list, 27)));
}
}

I have used BitArray defined by me. Its implementation is:

package com.biplav.ds;

public class BitArray {
 private byte[] arrayOfSize8bit;

 public BitArray(int size) {
  arrayOfSize8bit = new byte[(size / 8) + (size % 8 == 0 ? 0 : 1)];
 }

 public boolean get(int location) {
  return (arrayOfSize8bit[location / 8] & 1 << location % 8) != 0;
 }

 public void set(int location, boolean value) {
  byte b8 = arrayOfSize8bit[location / 8];
  byte posBit = (byte) (1 << (location % 8));
  if (value) {
   b8 = (byte) (b8 | posBit);
  } else {
   b8 = (byte) (b8 & (255 - posBit));
  }
  arrayOfSize8bit[location / 8] = b8;
 }

 public void set(int location) {
  set(location, true);
 }

 public void unset(int location) {
  set(location, false);
 }
}

Instead of BitArray BitSet can also be used which uses long[] instead of Byte array to achieve something similar.