=================================================================================================== RankSort 분석 ===================================================================================================
교재 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함수로 각 점수에 맞는 위치로 재정렬을 하기 때문이다.
이중 for문을 돌리면서 각 항을 서로 비교하여
더 큰 인자에 r을 증가시키고 있다.
이렇게 하면 전부 값이 매겨지도록 된다.
예를 들면
a[] = 1 3 2 5 4 의 배열의 경우
r[] = 0 2 1 4 3 의 랭크가 매겨지고
이정보가 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에 넣는것이다.
RECENT COMMENT