Tuesday, August 31, 2010

JAVA : Sorting Animations

JAVA Sorting Animations:

Sorting animations is a Java application that shows how a sorting alogrithm works by graphical animations. In this Java application working of four sorting alogrithm are shown through animations. 




!!!!!!!!!!....Applet may take some time to load....!!!!!!!!!!
Selection Sort:

Selection Sort is a very simple algorithm but it is inefficent on large lists.
The Selection algorithm works as follows:
  1. Find the minimum value in the list
  2. Swap it with the value in the first position
  3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)
  JAVA Code for Selection Sort Algorithm
//Selection sort algorithm method 
  public List sort(List a) throws Exception {
int max,min,pos=0;
     boolean swapped=false;
     for(int i=0; i < a.size(); i++){
              swapped=false;
              max=min=a.get(i);
              for(int j=i+1; j < a.size() ; j++){
                                     if(min>a.get(j)){
                                                 min=a.get(j);
  pos=j;
 swapped=true;
                                     }
               }

  if(swapped){
                    a.set(i, min);
                    a.set(pos, max);    
              }
      }
return a;
}//end of sort method

Selection sort algorithm performance:-
  • Worst case performance -
  • Best case performance -
  • Average case performance-
Bubble Sort:

Bubble sort is a sorting algorithm that works by repeatedly traversing through the list and compares the current element with the next one and swap them if they appears in wrong order. Traversing through the list is repeated until no swaps are needed. To known that the list is sorted we need to have one traversing through the list with no swap that means we need to traverse the list one more time even if the list is already sorted.


  JAVA Code for Bubble Sort Algorithm
 //bubble sort algorithm method
 public List sort(List a) throws Exception {
      boolean swapped =false;
for (int i = a.size()-1; i >= 0; i--) {
                  swapped = false;
                 for (int j = 0; j < i; j++) {

    if (a.get(j) > a.get(j+1)) {
                                    int T = a.get(j);
                                    a.set(j, a.get(j+1));
                                     a.set(j+1, T);
   swapped = true;
}
                    }
                 if(!swapped){
                           break;
}
}
return a;
}//end of sort method


Bubble Sort Algorithm Performance:-
  • Worst case performance -
  • Best case performance - n
  • Average case performance-
Insertion sort:

Insertion sort is good only for sorting small arrays (usually less than 100 items). In fact, the smaller the array, the faster insertion sort is compared to any other more advance  sorting algorithm such as Qucik sort.

  JAVA Code for Insertion Sort Algorithm
//insertion sort algorithm method 
 public List sort(List a) throws Exception {
       boolean swapped =false;
       int i, j, temp;
        for (i = 1; i < a.size(); i++) {
                temp = a.get(i);
                j = i;
              while (j > 0 && a.get(j - 1) > temp) {
                    a.set(j, a.get(j - 1));
                     j--;
               }
             a.set(j, temp);
       }
     
return a;
}//end of sort method



Insertion Sort Algorithm Performance:-
  • Worst case performance -
  • Best case performance - n
  • Average case performance-
Quick Sort:

Quick sort is a faster in practice and more advance sorting alogrithm as compare to some other simple algorithm such as Selection sort or Bubble sort.
  JAVA Code for Quick Sort Algorithm
//Quick sort algorithm method 
 public List sort(List a, int left, int right) throws Exception {
int mid,tmp,i,j;
 
  mid = a.get((left + right)/2);
  
  do {
       while(a.get(i) < mid){
          i++;
          
       }
      while(mid < a.get(j)){
          j--;
          
      }
      if (i <= j) {
          tmp = a.get(i);
          a.set(i, a.get(j));
          a.set(j, tmp);
          i++;
          j--;
      }
  } while (i <= j);
  if (left < j){
  sort(a,left,j);
  }
  if (i < right){ 
  sort(a,i,right);
  }
 
     return a;
}//end of sort method


Quick Sort Algorithm Performance:-
  • Worst case performance   -
  • Best case performance -       nlogn
  • Average case performance- nlogn

Download Files Here:


6 comments:

  1. Good one It clearly shows the efficiency of each algorithm

    ReplyDelete
  2. Good Explanation..

    ReplyDelete
  3. Sir kindly tell me how you embed or upload java simulation here..
    I want to upload my processing sketch which run in Java Enviornment. How you do this in Blogger.

    Thanks in Advance.
    zareahmer89@gmail.com

    ReplyDelete