IT &amp; Mobile

Quck Sort (using Java Generic)

algorithm & type 2016. 2. 1. 11:08

Quick Sort using java Generic.

==> <T extends Comparable> working. <T implements Comparable> not working.

(Java Generic을 이용해서 Quick Sort를 구현하여보았는데..

==> <T extends Comparable> 이건 동작하는데 <T implements Comparable>은 동작하지 않음)

public class QSortGen<T extends Comparable> {  


    void swap(T data[], int i, int j){
        T tmp = data[i];
        data[i]=data[j];
        data[j]=tmp;
    }

    public void qSort( T[] data, int st, int end){
        if (st == end || end < 0) return;

        T pivot=data[end];  //Pivot is End (temporary)

        int j=end-1;
        int i=0;
        while (i<j) {
            while ( i<j && data[i].compareTo(pivot) < 0 ) i++;
            while ( j>i && data[j].compareTo(pivot) > 0) j--;
            if (i < j)
                swap(data, i, j);
        };

        System.out.println( "new Pivot:" +i + ","+j);

        //IF pivot Largest ?
        if ( j == end-1 && data[j].compareTo(pivot) < 0 )  // (j == end-1) =>sometimes wrong. when only 3 data.
            qSort(data, 0, end-1);

        //General pivot
        else {
            swap(data, i ,end);  //i is real Pivot
            qSort(data, 0,   i-1); //left divide and conquer:recursive
            qSort(data, j+1, end); //right divide and comquer:recursive
        }
    }

    /////////MAIN /////////////////
    public static String datas[]={"adf", "kk", "bb", "aa", "dd", "cc", "ff" };

    public static void main(String args[]){
        QSortGen<String> q = new QSortGen<String>();
        q.qSort(datas, 0, datas.length-1);

        for( String a : datas)
            System.out.println(a);
    }
}

저작자표시

Posted by yongary

,

Scala OO Example

scala 2016. 2. 1. 10:52

Scala를 이용해서 OO를 TEST.

(OO Test using Scala)

object Seminar{


  class Dog(a:Int, n:String){
    var age:Int = a
    var name:String = n

    def feed()={
      println(this.name+ ":eating dog food")
    }
  }


  class Cat(a:Int, n:String) extends Dog(a:Int, n:String){
    override def feed()={
      println(this.name+ ":eating Cat food")
    }
  }


  ////////  MAIN  ////////////////////////////////////////////////
  def main(args:Array[String]) = {
   var allDog:Array[Dog]   = Array( new Dog(1,"dogA"),
     new Dog(2,"dogB"),
     new Dog(3,"dogC"),
     new Dog(4,"dogD"),
     new Cat(5,"catA"))


    for( dog<- allDog)
      dog.feed()

  }
} //end

저작자표시

Posted by yongary

,

Quick Sort (java)

algorithm & type 2016. 1. 31. 00:34

[int Array기반 간단한 QuickSort]
- http://www.algolist.net/Algorithms/Sorting/Quicksort  참고. 
=>c++ 코드 참조하면.. 한번소트 후에, 끝나면 i가 j보다 크군요..
 (j=2, i=3) 이때, j포함 왼쪽.  i포함 오른쪽 돌려야 함.
	
	public void quickSort(int arr[], int left, int right) {
	      int i = left, j = right;
	      int tmp;
	      int pivotValue = arr[(left + right) / 2];
	 
	      /* partition */
	      while (i <= j) {
	            while (arr[i] < pivotValue)
	                  i++;
	            while (arr[j] > pivotValue)
	                  j--;
	            if (i <= j) {
	                  tmp = arr[i];
	                  arr[i] = arr[j];
	                  arr[j] = tmp;
	                  i++;
	                  j--;
	            }
	      };
	 
	      /* recursion */
	      if (left < j)
	            quickSort(arr, left, j);
	      if (i < right)
	            quickSort(arr, i, right);
	}
	
	public static void main(String args[]){
	
		SortSearch s = new SortSearch();
		
		int A[] = new int[] {9,8,7,6,5,4,3,2,1};
		s.quickSort(A, 0, A.length-1);
		
		for (int a : A){
			System.out.println(a);
		}
         }



-----------아래 건은 연습용------------------ 
[Simple Quick Sort Example.. with String Array]
  - using End element as a temporary Pivot.

 
public class QuickSort {


    void swap(String data[], int i, int j){
        String tmp = data[i];
        data[i]=data[j];
        data[j]=tmp;
    }

    public void qSort( String[] data, int st, int end){
        if (st == end || end < 0) return;
        
        String pivot=data[end];  //Pivot is End (temporary)

        int j=end-1;
        int i=0;
        while (i<j) {
            while ( i<j && data[i].compareTo(pivot) < 0 ) i++;
            while ( j>i && data[j].compareTo(pivot) > 0) j--;
            if (i < j)
                swap(data, i, j);
        };

        System.out.println( "new Pivot:" +i + ","+j);
        
        //IF pivot Largest ?
        if ( j == end-1 && data[j].compareTo(pivot) < 0 )  // (j == end-1) =>sometimes wrong. when only 3 data.
            qSort(data, 0, end-1);
            
        //General pivot
        else {
            swap(data, i ,end);  //i is real Pivot
            qSort(data, 0,   i-1); //left divide and conquer:recursive
            qSort(data, j+1, end); //right divide and comquer:recursive
        }
    }

    /////////main
    public static String datas[]={"adf", "kk", "bb", "aa", "dd", "cc", "ff" };
    public static void main(String args[]){
        QuickSort q = new QuickSort();
        q.qSort(datas, 0, datas.length-1);

        for( String a : datas)
            System.out.println(a);
    }
}

저작자표시

Posted by yongary

,

버킷 정렬(bin sort)

algorithm & type 2016. 1. 27. 16:20

일반적으로 정렬 중에 가장 빠른 알고리듬은 quick sort로서 O(N*logN)의 평균속도를 가지고 있다.

하지만, 분포가 어느정도 균등한 자료의 경우

버킷 소트를 하게 되면 O(n)으로 정렬을 할 수 있다.

Hash의 개념을 사용하게 되며.. 그림은 REF-SITE 참조.

단점: 버킷을 미리 만들어 둬야 하므로 메모리 소비가 좀 있고

그 외 최악의 속도는 O(n)*버킷내 정렬시간 이 되므로 O(n**2)까지도 갈 수 있다.

(어차피 quick sort도 O(n**2)까지 갈 수 있으므로. 자료가 적당하다면 일반적으로 quick sort보다 속도는 좋은 것 같다 ).

저작자표시

Posted by yongary

,

GPL vs LGPL

IT 2016. 1. 20. 16:43

GPL (General Public License) source를 사용하거나 binary를 사용하더라도 본인의 프로그램을 오픈해야함
LGPL (Lesser GPL) : source를 사용하면 오픈, Library형태의 binary를 사용하면 오픈안해도됨 REF-SITE

BSD: 무제한 사용.