알고리즘 : 왜 배열 요소를 변수에 재 할당해야합니까?

Question

여기 알고리즘이 새롭습니다.

public void union(int p, int q){ 

int pid = id[p]; 
int qid = id[q]; 

for(int i = 0; i <id.length; i++){ 
if (id[i] = pid) 
    id[i] = qid; 
} 

그는 먼저 PID에 ID [P]를 할당 할 필요가 있다고 말했다 교수는이 코드를 주었을 때 나는 프린스턴의 알고리즘과 데이터 구조 클래스를보고하기 시작했다. 왜 그런가요? 왜 당신은 단지 id [p]를 사용할 수 없습니까? 또한 알고리즘 소개 (Introduction to Algorithms)를 읽기 시작했고이 삽입 유형 구현을 보았습니다. 나는 A [j]를 사용하는 대신에 'key'에 할당했다. 위의 이유와 동일한 이유입니까? 감사!

INSERTION-SORT.A/ 
1 for j = 2 to A.length 
2 key = A[j] 
4 i = j - 1 
5 while i>0 and A(i) > key{ 
6 A(i+1) = A(i) 
7 i=i-1} 
8 A[i+1] = key 

Answer 1

알고리즘의 나중 단계에서 값을 덮어 쓰게되므로 해당 요소를 임시 변수에 복사해야합니다.

for(int i = 0; i <id.length; i++){ 
    if (id[i] == id[p]) { 
     id[i] = id[q]; 
    } 
} 

i이 p 같다, 다음 id[p]이 id[q]의 값을 덮어 씁니다 :

은 제안 된 버전을 고려하십시오. 원래 id[p]은 이제 잊어 버리고 나머지 알고리즘은 잘못된 결과를 산출합니다. 그것을 밖으로 시도하십시오!

그렇습니다. 삽입 정렬에서 동일한 이유로 A [j]의 원래 값을 저장해야합니다. 요소 값을 덮어 쓰면 다른 경우 원래 값이 손실됩니다.