Saturday, July 14, 2012

Sorting Alogirthm in Java - Quick , Insertion, Merge, Heap, Selection, and Shell

You can find Java based implementation for Quick , Insertion, Merge, Heap, Selection, and Shell sorting algorithm. All those are properly tested, I assume you have good understand on how each algorithm works that helps you to understand the implementation much better.

HeapSort

public class HeapSort {

    public int[] sort(int[] a) {
        sort(a, a.length-1);
        return a;
    }

    public void sort(int[] a, int end) {
        for (int i = end / 2; i >= 1; i--) {
            fixHeap(a, i, end, a[i]);
        }
        for (int i = end; i > 0; i--) {
            swap(a, 0, i);
            fixHeap(a, 0, i - 1, a[0]);
        }
    }

    private void fixHeap(int[] a, int root, int end,
                         int key) {
        int child = 2 * root; // left child
        if (child < end && a[child] < a[child + 1]) {
            child++;
        }
        if (child <= end && key < a[child]) {
            a[root] = a[child];
            fixHeap(a, child, end, key);
        } else {
            a[root] = key;
        }
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

InsertionSort


public class InsertionSort {

    public int[] sort(int[] input) {
        int size = input.length;
           for (int i = 1; i < size; i++) {
            int j = i;
            int x = input[i];
            while (j > 0 && input[j - 1] > x) {
                input[j] = input[j - 1];
                j--;
            }
            input[j] = x;
        }
        return input;
    }
}

MergeSort 

public class MergeSort {

    public int[] sort(int[] list) {
        mergeSort(list, 0, list.length-1);
        return list;
    }

    public void mergeSort(int list[], int first, int last) {
        if (first >= last) {
            return;
        }
        int middle = (first + last) / 2;
        mergeSort(list, first, middle);
        mergeSort(list, middle + 1, last);

        int size = (last - first) + 1;
        int[] results = new int[size];

        int start2 = middle + 1;
        int indexC = 0;
        int start1 = first;
        while ((start1 <= middle) && (start2 <= last)) {
            if (list[start1] < list[start2]) {
                results[indexC] = list[start1];
                start1++;
            } else {
                results[indexC] = list[start2];
                start2++;
            }
            indexC++;
        }
        if (start1 <= middle) {
            for (int i = start1; i <= middle; i++) {
                results[indexC] = list[i];
                indexC++;
            }
        } else {
            for (int j = start2; j <= last; j++) {
                results[indexC] = list[j];
                indexC++;
            }
        }

        int c = 0;
        for (int index = first; index <= last; index++) {
            list[index] = results[c];
            c++;
        }
    }
}

QuickSort

public class QuickSort {

    public int[] sort(int[] list) {
        quickSort(0, list.length - 1, list);
        return list;
    }

    public void quickSort(int start, int end, int[] list) {
        if (start >= end) return;
        int p = partition(start, end, list);
        quickSort(start, p, list);
        quickSort(p + 1, end, list);
    }

    private int partition(int start, int end, int[] list) {
        // First element
        int pivot = list[start];
        int pivotPoint = start;
        for (int index = start + 1; index <= end; index++) {
            if (list[index] < pivot) {
                pivotPoint = pivotPoint + 1;
                swap(pivotPoint, index, list);
            }
        }
        swap(start, pivotPoint, list);
        return pivotPoint;
    }

    private void swap(int i, int j, int[] list) {
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

SelectionSort

public class SelectionSort {
    public int[] sort(int[] input) {
        int size = input.length;
        for (int i = 0; i < size; i++) {
            int index = i;
            int currentMin = input[i];
            for (int j = i+1; j < size; j++) {
                int y = input[j];
                if (y < currentMin) {
                    currentMin = y;
                    index = j;
                }
            }
            int x = input[i];
            input[i] = input[index];
            input[index] = x;
        }
        return input;
    }
}

ShellSort 

public class ShellSort {
    public int[] sort(int[] a) {
        double passes = Math.floor(Math.log(a.length));
        while (passes > 1) {
            int increment = (int) (Math.pow(2, passes) - 1);
            for (int start = 0; start < increment; start++) {
                insertSort(start, increment, a);
            }
            passes = passes -1;
        }
        insertSort(0, 1, a);
        return a;
    }

    public void insertSort(int start, int increment, int[] a) {
        int j, k, temp;

        for (int i = start + increment; i < a.length; i += increment) {
            j = i;
            k = j - increment;
            if (a[j] < a[k]) {
                temp = a[j];
                do {
                    a[j] = a[k];
                    j = k;
                    k = j - increment;
                } while (j != start && a[k] > temp);
                a[j] = temp;
            }
        }
    }
}

Friday, July 13, 2012

Google Maps - Display points with different markers

If you want to display different points with different markers this is for you.  Say you want to display points with two markers, let's first create markers:

Let's get started:

function initialize() {
      if (GBrowserIsCompatible()) {
        var map = new GMap2(document.getElementById("map_canvas"));
        map.setCenter(new GLatLng(28.2,-89.6), 6);
        map.addControl(new GSmallMapControl());
        map.addControl(new GMapTypeControl());
   
        // Create our "tiny" marker icon
        var greenIcon= new GIcon(G_DEFAULT_ICON);
        greenIcon.image = "http://www.google.com/intl/en_us/mapfiles/ms/icons/green-dot.png";
        greenmarker = { icon:greenIcon };

        var redIcon= new GIcon(G_DEFAULT_ICON);
        redIcon.image = "http://www.google.com/intl/en_us/mapfiles/ms/icons/red-dot.png";
        redmarker = { icon:redIcon };

        var greenIcon= new GIcon(G_DEFAULT_ICON);
        greenIcon.image = "http://www.google.com/intl/en_us/mapfiles/ms/icons/green-dot.png";
        greenmarker = { icon:greenIcon };

        var redIcon= new GIcon(G_DEFAULT_ICON);
        redIcon.image = "http://www.google.com/intl/en_us/mapfiles/ms/icons/red-dot.png";
        redmarker = { icon:redIcon };


Now let's create a set of data points:

var locations = [['42001', 26.0, - 90.0,    1],
['42002',26.0, -94.0, 2],
['42007',30.1, -88.9, 3],
['42019',27.9, -95.0, 4],
['42020',27.0, -96.5, 5],
['42035',29.2, -94.4, 6],
['42036',28.5, -84.5, 7],
['42038',27.4, -92.6, 8],
['42039',28.8, -86.0, 9],
['42040',29.2, -88.3, 10],  ];

Now, let's create marker with the data point and marker options:

function createMarker(point, moption, id) {
      var marker = new GMarker(point, moption);


      GEvent.addListener(marker, "click", function() {
        marker.openInfoWindow("Point " + id + "");
      });
      return marker;
 }

Putting all together:

// Using first marker
for (i = 0; i < locations.length; i++) {
  var latlng = new GLatLng(locations[i][1], locations[i][2]);
   map.addOverlay(createMarker(latlng, greenmarker, locations[i][0]));
}

//Using second marker 
map.addOverlay(createMarker(new GLatLng(29.3, -90.0), redmarker, 'GDIL1'));
  }
 }