Data Structure 2번째 HW(내맘대로 분석 #2)

===================================================================================================
RankSort 분석
===================================================================================================

일단 Rank Sort 알고리즘의 소스를 보자.

교재 80p를 보면 대략
[code java]
   public static void rank(Comparable [] a, int [] r)
   {
       if(r.length < a.length)
           throw new IllegalArgumentException
                    ("length of rank array cannot" +
                      "be less than the number of object");
      
       for(int i = 0; i < a.length; i++)
           r[i] = 0;
      
       for(int i = 1; i < a.length; i++)
           for(int j = 0; j < i; j++)
               if(a[j].compareTo(a[i]) <= 0) r[i]++;
               else r[j]++;
   }
   private static void rearrange(Comparable [] a, int [] r)
   {
       Comparable [] u = new Comparable[a.length];
       for(int i = 0; i < a.length; i++)
           u[r[i]] = a[i];

       for(int i = 0; i < a.length; i++)
           a[i] = u[i];
   }
[/code]
요렇게 되어있는것을 알 수 있다.

소트는 1개인데 왜 함수가 2개냐하면
rank소트는 rank함수로 각 인덱스에 점수를 주고,
rearrange함수로 각 점수에 맞는 위치로 재정렬을 하기 때문이다.

다음으로 rank함수를 보자

rank함수에서 중요하게 봐야될것은
11~14번째 라인에
[code java]
for(int i = 1; i < a.length; i++)
   for(int j = 0; j < i; j++)
       if(a[j].compareTo(a[i]) <= 0) r[i]++;
               else r[j]++;
[/code]
이부분이다.

이중 for문을 돌리면서 각 항을 서로 비교하여
더 큰 인자에 r을 증가시키고 있다.
이렇게 하면 전부 값이 매겨지도록 된다.
예를 들면

a[] = 1 3 2 5 4           의 배열의 경우
r[]  = 0 2 1 4 3           의 랭크가 매겨지고
이정보가 rearrange함수로 넘어가게 된다.

마지막으로 rearrange함수를 보자

rearrange함수는 rank가 매겨진 배열을 rank순으로 배열하는것 뿐이다.
우선 35라인에서 크기가 같은 Comparable 오브젝트배열인 u를 생성한다.
그리고 37라인에서
[code java]
u[r[i]] = a[i];
[/code]
이것의 의미는 u라는 새로운 배열에 a의 i번째 인자를 자신의 랭크에 맞는곳에 넣으라는 뜻이다.
근데 이것만 하면 a에 값이 들어가는게 아닌, u라는 배열에 정렬되고, a는 그대로다.
그래서 그 아래 for문에서 하는일이
[code java]
a[i]=u[i];
[/code]
로 다시 a에 넣는것이다.