To Sort an Interger Array using Shell Sort

To Sort an Interger Array using Shell Sort

class ShellSort {

    public static int[] shellSort(int[] array) {
  int N = array.length;
  
  // determine the initial h value
  int h = 1;
     while (h < N / 3) 
      h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
     
     while (h >= 1) {
      // h-sort the array
      for (int i = h; i < array.length; i++) {
       // do insertion sort for h-sized array
       for (int j = i; j >= h && array[j] < array[j - h]; j -= h)
        swap(array, j, j - h);
      }
      
      h = h / 3; // reverse the h-size
     }
     
     return array;
 }
 
 /*
  * swaps data elements between 2 indexes of an array
  */
 private static void swap(int[] array, int i, int j) {
  int temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 } 
    
    public static void  main(String args[]){
     ShellSort sSort = new ShellSort();
     int[] array = { 77, 99, 44, 55, 22, 88, 11, 0, 66, 33 };
     int[] sortedArray = sSort.shellSort(array);
     for (int i = 0; i < array.length; i++)
         System.out.println(sortedArray[i]);
     
    }
}

Output of the Program : 

0
11
22
33
44
55
66
77
88
99

Try it by yourself here : http://ideone.com/veRv5P

[ Read More ]

Sort an Integer array with Bucket Sort

Here is a java program to Sort an Integer array with Bucket Sort

class BucketSort {

    public int[] bucketSort(int[] array) {
        // create an array the size of the largest value + 1
        int[] bucket = new int[100];   

        // for every value in array, increment its corresponding bucket
        for (int i = 0; i < array.length; i++)
            bucket[array[i]]++;

        int outPos = 0;
        for (int i = 0; i < bucket.length; i++) { 
         if (bucket[i] > 0)
             array[outPos++] = i;
        }
        
        return array;
    }
    
    public static void  main(String args[]){
     BucketSort bSort = new BucketSort();
     int[] array = { 77, 99, 44, 55, 22, 88, 11, 0, 66, 33 };
     int[] sortedArray = bSort.bucketSort(array);
     for (int i = 0; i < array.length; i++)
         System.out.println(sortedArray[i]);
     
    }
}

Output of the Program :

0
11
22
33
44
55
66

Try By Yourself Here : http://ideone.com/OpHXmH

[ Read More ]

Merge-Sort Algorithm implementation in JAVA

Merge-Sort Function

void MergeSort(int low, int high)
   // a[low : high] is a global array to be sorted.
   // Small(P) is true if there is only one element to
   // sort. In this case the list is already sorted.
   {
       if (low < high) { // If there are more than one element
              // Divide P into subproblems.
              // Find where to split the set.
              int mid = (low + high)/2;
              // Solve the subproblems.
              MergeSort(low, mid);
              MergeSort(mid + 1, high);
              // Combine the solutions.
              Merge(low, mid, high);
       }
   }

   void Merge(int low, int mid, int high)
   // a[low:high] is a global array containing two sorted
   // subsets in a[low:mid] and in a[mid+1:high]. The goal
   // is to merge these two sets into a single set residing
   // in a[low:high]. b[] is an auxiliary global array.
   {
       int h = low, i = low, j = mid+1, k;
       while ((h <= mid) && (j <= high)) {
          if (a[h] <= a[j]) { b[i] = a[h]; h++; }
          else { b[i] = a[j]; j++; } i++;
       }
       if (h > mid) for (k=j; k<=high; k++) {
                       b[i] = a[k]; i++;
                    }
       else for (k=h; k<=mid; k++) {
               b[i] = a[k]; i++;
            }
       for (k=low; k<=high; k++) a[k] = b[k];
   }

Merge Sort Java Code :

import java.util.*;

public class MergeSort {
 public int a[] = new int[50];

 public void merge_sort(int low, int high) {
  int mid;
  if (low < high) {
   mid = (low + high) / 2;
   merge_sort(low, mid);
   merge_sort(mid + 1, high);
   merge(low, mid, high);
  }
 }

 public void merge(int low, int mid, int high) {
  int h, i, j, k;
  int b[] = new int[50];
  h = low;
  i = low;
  j = mid + 1;

  while ((h <= mid) && (j <= high)) {
   if (a[h] <= a[j]) {
    b[i] = a[h];
    h++;
   } else {
    b[i] = a[j];
    j++;
   }
   i++;
  }
  if (h > mid) {
   for (k = j; k <= high; k++) {
    b[i] = a[k];
    i++;
   }
  } else {
   for (k = h; k <= mid; k++) {
    b[i] = a[k];
    i++;
   }
  }
  for (k = low; k <= high; k++)
   a[k] = b[k];
 }

 public MergeSort() {
  int num, i;

  System.out.println("             MERGE SORT PROGRAM            ");

  System.out.println();
  System.out.println();
  System.out
    .println("Please Enter THE No. OF ELEMENTS you want to sort[THEN PRESS ENTER]:");
  num = new Scanner(System.in).nextInt();
  System.out.println();
  System.out.println("Now, Please Enter the (" + num
    + ") nos. [THEN PRESS ENTER]:");
  for (i = 1; i <= num; i++) {
   a[i] = new Scanner(System.in).nextInt();
  }
  merge_sort(1, num);
  System.out.println();
  System.out.println("So, the sorted list (using MERGE SORT) will be :");
  System.out.println();
  System.out.println();

  for (i = 1; i <= num; i++)
   System.out.print(a[i] + "    ");

 }

 public static void main(String[] args) {
  new MergeSort();
 }
}

[ Read More ]

Alphanumeric String Sorting using Java

Alphanumeric is a combination of alphabetic and numeric characters (sometimes shortened to alphameric).

In computing, the alphanumeric Strings can be seen very common to represent various codes etc. Sorting the alphanumeric strings can sometimes be a trouble by using regular sort techniques.

import java.util.Arrays;
import java.util.Comparator;
 
public class AlphanumericSorting implements Comparator {
    /**
     * The compare method that compares the alphanumeric strings
     */
    public int compare(Object firstObjToCompare, Object secondObjToCompare) {
        String firstString = firstObjToCompare.toString();
        String secondString = secondObjToCompare.toString();
 
        if (secondString == null || firstString == null) {
            return 0;
        }
 
        int lengthFirstStr = firstString.length();
        int lengthSecondStr = secondString.length();
 
        int index1 = 0;
        int index2 = 0;
 
        while (index1 < lengthFirstStr && index2 < lengthSecondStr) {
            char ch1 = firstString.charAt(index1);
            char ch2 = secondString.charAt(index2);
 
            char[] space1 = new char[lengthFirstStr];
            char[] space2 = new char[lengthSecondStr];
 
            int loc1 = 0;
            int loc2 = 0;
 
            do {
                space1[loc1++] = ch1;
                index1++;
 
                if (index1 < lengthFirstStr) {
                    ch1 = firstString.charAt(index1);
                } else {
                    break;
                }
            } while (Character.isDigit(ch1) == Character.isDigit(space1[0]));
 
            do {
                space2[loc2++] = ch2;
                index2++;
 
                if (index2 < lengthSecondStr) {
                    ch2 = secondString.charAt(index2);
                } else {
                    break;
                }
            } while (Character.isDigit(ch2) == Character.isDigit(space2[0]));
 
            String str1 = new String(space1);
            String str2 = new String(space2);
 
            int result;
 
            if (Character.isDigit(space1[0]) && Character.isDigit(space2[0])) {
                Integer firstNumberToCompare = new Integer(Integer
                        .parseInt(str1.trim()));
                Integer secondNumberToCompare = new Integer(Integer
                        .parseInt(str2.trim()));
                result = firstNumberToCompare.compareTo(secondNumberToCompare);
            } else {
                result = str1.compareTo(str2);
            }
 
            if (result != 0) {
                return result;
            }
        }
        return lengthFirstStr - lengthSecondStr;
    }
 
    /**
     * Testing the alphanumeric sorting
     */
    public static void main(String[] args) {
        String[] alphaNumericStringArray = new String[] { "NUM10071",
                "NUM9999", "9997", "9998", "9996", "9996F" };
 
        /*
         * Arrays.sort method can take an unsorted array and a comparator
         * to give a final sorted array.
         *
         * The sorting is done according to the comparator that we have
         * provided.
         */
        Arrays.sort(alphaNumericStringArray, new AlphanumericSorting());
 
        for (int i = 0; i < alphaNumericStringArray.length; i++) {
            System.out.println(alphaNumericStringArray[i]);
        }
 
    }
 
}

[ Read More ]

DataTable Sorting using wicket

Sorting a data table using apache wicket

//   DataTablePage.java

import org.apache.wicket.extensions.markup.html.repeater.data.table.DefaultDataTable;
import org.apache.wicket.extensions.markup.html.repeater.data.table.IColumn;
import org.apache.wicket.extensions.markup.html.repeater.data.table.PropertyColumn;
import org.apache.wicket.markup.html.WebPage;
import org.apache.wicket.model.Model;
import org.apache.wicket.model.StringResourceModel;

public class DataTablePage extends WebPage {
    
    public DataTablePage() {
        final DataTableUser user = new DataTableUser();
        
        IColumn[] columns = new IColumn[2];
        columns[0] = new PropertyColumn(new StringResourceModel("firstNameTableHeaderLabel", this, null), "name.first", "name.first");
        columns[1] = new PropertyColumn(new Model("Last Name"), "name.last", "name.last");
        
        DefaultDataTable table = new DefaultDataTable("datatable", columns, user, 10);
        
        add(table);
    }

}


// DataTableUser.java

import java.io.Serializable;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

import org.apache.wicket.extensions.markup.html.repeater.util.SortableDataProvider;
import org.apache.wicket.model.AbstractReadOnlyModel;
import org.apache.wicket.model.IModel;
import org.apache.wicket.model.PropertyModel;

public class DataTableUser extends SortableDataProvider {

 class SortableDataProviderComparator implements Comparator<Contact>, Serializable {
  public int compare(final Contact o1, final Contact o2) {
   PropertyModel<Comparable> model1 = new PropertyModel<Comparable>(o1, getSort().getProperty());
   PropertyModel<Comparable> model2 = new PropertyModel<Comparable>(o2, getSort().getProperty());

   int result = model1.getObject().compareTo(model2.getObject());

   if (!getSort().isAscending()) {
    result = -result;
   }

   return result;
  }

 }

 private List<Contact> list = new ArrayList<Contact>();
 private SortableDataProviderComparator comparator = new SortableDataProviderComparator();

 public DataTableUser() {
  // The default sorting
  setSort("name.first", true);

  list.add(new Contact(new Name("FN1", "LN1")));
  list.add(new Contact(new Name("FN2", "LN2")));
  list.add(new Contact(new Name("FN3", "LN3")));

 }

 public Iterator<Contact> iterator(final int first, final int count) {

  // Get the data
  List<Contact> newList = new ArrayList<Contact>(list);

  // Sort the data
  Collections.sort(newList, comparator);

  return newList.subList(first, first + count).iterator();
 }

 public IModel<Contact> model(final Object object) {
  return new AbstractReadOnlyModel<Contact>() {
   @Override
   public Contact getObject() {
    return (Contact) object;
   }
  };
 }

 public int size() {
  return list.size();
 }

}

class Contact implements Serializable {

 private final Name name;

 public Contact(final Name name) {
  this.name = name;
 }

 public Name getName() {
  return name;
 }
}

class Name implements Serializable {

 private String firstName;
 private String lastName;

 public Name(final String fName, final String lName) {
  firstName = fName;
  lastName = lName;
 }

 public String getFirst() {
  return firstName;
 }

 public String getLast() {
  return lastName;
 }

 public void setFirst(final String firstName) {
  this.firstName = firstName;
 }

 public void setLast(final String lastName) {
  this.lastName = lastName;
 }
}

// DataTablePage.html

<html>
<head>
 <title>DataTable</title>
</head>

<body>
<table wicket:id="datatable"></table>
</body>
</html>


// DataTablePage.properties

firstNameTableHeaderLabel=First Name

[ Read More ]

Sort Java Vector in descending order using comparator

Sort Java Vector in descending order using comparator example his java example shows how to sort elements of Java Vector in descending order using comparator and reverseOrder method of Collections class.

mport java.util.Vector;
mport java.util.Collections;
mport java.util.Comparator;
 
public class SortVectorInDescendingOrderExample {
 
  public static void main(String[] args) {
   
    //create a Vector object
    Vector v = new Vector();
   
    //Add elements to Vector
    v.add("1");
    v.add("2");
    v.add("3");
    v.add("4");
    v.add("5");
   
    /*
      To get comparator that imposes reverse order on a Collection use
      static Comparator reverseOrder() method of Collections class
    */
   
    Comparator comparator = Collections.reverseOrder();
   
    System.out.println("Before sorting Vector in descending order : " + v);
   
    /*
      To sort an Vector using comparator use,
      static void sort(List list, Comparator c) method of Collections class.
    */
   
    Collections.sort(v,comparator);
    System.out.println("After sorting Vector in descending order : " + v);
   
  }
}

[ Read More ]

To Apply Bubble Sort on Strings

Here is a Java Program to Bubble Sort for Strings

class SortString {
  static String arr[] = {
    "Now", "is", "the", "time", "for", "all", "good", "men",
    "to", "come", "to", "the", "aid", "of", "their", "country"
  };
  public static void main(String args[]) {
    for(int j = 0; j < arr.length; j++) {
      for(int i = j + 1; i < arr.length; i++) {
        if(arr[i].compareTo(arr[j]) < 0) {
          String t = arr[j];
          arr[j] = arr[i];
          arr[i] = t;
        }
      }
      System.out.println(arr[j]);
    }
  }
}

Output of Above Java Program
Now
aid
all
come
country
for
good
is
men
of
the
the
their
time
to
to

[ Read More ]