Jeetu Alex - IT Software Professional specialized in developing high-end, customized business solutions using Coldfusion and Java.

Coldfusion
Java
JQuery

An online resource for latest web technologies like Coldfusion, JRun, Pro*C, JQuery, HTML5, PHP, W3C, Java, J2EE, C, C++, ORACLE, PL/SQL, MySql, Ajax, Coldbox, Fusebox, UNIX, JavaScript, NodeJS and much more...

Wednesday, February 26, 2014

Regex in java

Data Structure Tutorial #4 Sorting Techniques Session #3

Radix sort in java

Grouping of the items with their MSB and then compare and merge. The number of digits in each element should be made same. In the below example it is 2 ie, 3 = 03 or 8 = 08.


import java.util.ArrayList;

public class RadixSort {

public void radixSort(int arr[], int maxDigits){
int exp = 1;//10^0;
for(int i =0; i < maxDigits; i++){
ArrayList bucketList[] = new ArrayList[10];
for(int k=0; k < 10; k++){
bucketList[k] = new ArrayList();
}
for(int j =0; j < arr.length; j++){
int number = (arr[j]/exp)%10;
bucketList[number].add(arr[j]);
}
exp *= 10;
int index =0;
for(int k=0; k < 10; k++){
for(int num: bucketList[k]){
arr[index] = num;
index++;
}
}
}

System.out.println("Sorted numbers");
for(int i =0; i < arr.length; i++){
System.out.print(arr[i] +", ");
}
}

public static void main(String[] argv){
int n = 5;
int arr[] = {1,4,2,3,5,10,8};
new RadixSort().radixSort(arr, 2);
}
}

Merge sort in java

Splitting the array into sets and compare / merge them during iterations. The time complexity is O(n log n) 
import java.util.*;

public class MergeSort {
public static void main(String[] args) {
int[] list = {14, 32, 67, 76, 23, 41, 58, 85};
System.out.println("before: " + Arrays.toString(list));
mergeSort(list);
System.out.println("after: " + Arrays.toString(list));
}

// Places the elements of the given array into sorted order
// using the merge sort algorithm.
// post: array is in sorted (nondecreasing) order
public static void mergeSort(int[] array) {
if (array.length > 1) {
// split array into two halves
int[] left = leftHalf(array);
int[] right = rightHalf(array);

// recursively sort the two halves
mergeSort(left);
mergeSort(right);

// merge the sorted halves into a sorted whole
merge(array, left, right);
}
}

// Returns the first half of the given array.
public static int[] leftHalf(int[] array) {
int size1 = array.length / 2;
int[] left = new int[size1];
for (int i = 0; i < size1; i++) {
left[i] = array[i];
}
return left;
}

// Returns the second half of the given array.
public static int[] rightHalf(int[] array) {
int size1 = array.length / 2;
int size2 = array.length - size1;
int[] right = new int[size2];
for (int i = 0; i < size2; i++) {
right[i] = array[i + size1];
}
return right;
}

// Merges the given left and right arrays into the given
// result array. Second, working version.
// pre : result is empty; left/right are sorted
// post: result contains result of merging sorted lists;
public static void merge(int[] result,
int[] left, int[] right) {
int i1 = 0; // index into left array
int i2 = 0; // index into right array

for (int i = 0; i < result.length; i++) {
if (i2 >= right.length || (i1 < left.length &&
left[i1] <= right[i2])) {
result[i] = left[i1]; // take from left
i1++;
} else {
result[i] = right[i2]; // take from right
i2++;
}
}
}
}

Data Structure Tutorial #3 - Sorting Techniques Session #2

Quick sort in java

Input must be a list of distinct integers. Time complexity is O(n2
import java.io.*;
import java.util.*;

public class QuickSort
{
public static void swap (int A[], int x, int y)
{
int temp = A[x];
A[x] = A[y];
A[y] = temp;
}

// Reorganizes the given list so all elements less than the first are
// before it and all greater elements are after it.
public static int partition(int A[], int f, int l)
{
int pivot = A[f];
while (f < l)
{
if (A[f] == pivot || A[l] == pivot)
{
System.out.println("Only distinct integers allowed - C321");
System.out.println("students should ignore this if statement");
System.out.exit(0);
}
while (A[f] < pivot) f++;
while (A[l] > pivot) l--;
swap (A, f, l);
}
return f;
}

public static void Quicksort(int A[], int f, int l)
{
if (f >= l) return;
int pivot_index = partition(A, f, l);
Quicksort(A, f, pivot_index);
Quicksort(A, pivot_index+1, l);
}

// Usage: java QuickSort [integer] ...
// All integers must be distinct
public static void main(String argv[])
{
int A[] = new int[argv.length];
for (int i=0 ; i < argv.length ; i++)
A[i] = Integer.parseInt(argv[i]);

Quicksort(A, 0, argv.length-1);

for (int i=0 ; i < argv.length ; i++) System.out.print(A[i] + " ");
System.out.println();
}
}

Selection sort in java

The  first iteration will give the smallest number at the first end of the list. The elements starting from the first is compared / swapped with the rest of the positions.

N-1 iterations for N items. Time complexity is O(n2)

public class MySelectionSort {

public static int[] doSelectionSort(int[] arr){

for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;

int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return arr;
}

public static void main(String a[]){

int[] arr1 = {10,34,2,56,7,67,88,42};
int[] arr2 = doSelectionSort(arr1);
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}


Output will be like



2, 7, 10, 34, 42, 56, 67, 88, 

Insertion sort in java

Time complexity is O(n2)
public class MyInsertionSort {

public static void main(String[] args) {

int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
insertionSort(input);
}

private static void printNumbers(int[] input) {

for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + ", ");
}
System.out.println("\n");
}

public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
printNumbers(array);
}
}
}


Output will be like:



2, 4, 9, 6, 23, 12, 34, 0, 1, 

2, 4, 9, 6, 23, 12, 34, 0, 1,

2, 4, 6, 9, 23, 12, 34, 0, 1,

2, 4, 6, 9, 23, 12, 34, 0, 1,

2, 4, 6, 9, 12, 23, 34, 0, 1,

2, 4, 6, 9, 12, 23, 34, 0, 1,

0, 2, 4, 6, 9, 12, 23, 34, 1,

0, 1, 2, 4, 6, 9, 12, 23, 34,

Data Structure Tutorial #2 - Sorting Techniques Session #1

Bubble sort in java

The logic is to swap the 2 items in the list during iterations. At the end of first iteration the list will have the largest no. at the end.

n-1 iterations for n items. Time complexity is O(n2)

import java.util.Scanner;

class BubbleSort {
public static void main(String []args) {
int n, c, d, swap;
Scanner in = new Scanner(System.in);

System.out.println("Input number of integers to sort");
n = in.nextInt();

int array[] = new int[n];

System.out.println("Enter " + n + " integers");

for (c = 0; c < n; c++)
array[c] = in.nextInt();

for (c = 0; c < ( n - 1 ); c++) {
for (d = 0; d < n - c - 1; d++) {
if (array[d] > array[d+1]) /* For descending order use < */
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}

System.out.println("Sorted list of numbers");

for (c = 0; c < n; c++)
System.out.println(array[c]);
}
}


Output will be like:



op

Friday, February 21, 2014

IndexOf Logic in Java

Logic of the following function:

IndexOf(String,Sub String) – Gives the position of the first occurrence of the substring.

Please check and comment.

import java.io.IOException;
import javax.servlet.http.*;

@SuppressWarnings("serial")
public class TestIndexOf extends HttpServlet {
public void doGet(HttpServletRequest req, HttpServletResponse resp)
throws IOException {
resp.setContentType("text/plain");
resp.getWriter().println("String IndexOf Implementation...");

resp.getWriter().println("Pos = " + IndexOf("Hello Jeetu", "llo"));

}

public int IndexOf(String main, String sub) {

char[] mainc = main.toCharArray();
char[] subc = sub.toCharArray();

for (int i = 0; i < mainc.length; i++) {
if (mainc[i] == subc[0]) {
for (int j = 0; j < subc.length; j++) {
if (mainc[i + j] != subc[j])
break;
else if (j == subc.length - 1)
return i + 1;
}

}
}
return -1;
}
}