정렬 된 배열 삽입

Question

다음은 Robert Lafore가 작성한 "데이터 구조 & 알고리즘"에서 발췌 한 것입니다. 배열에 항목을 삽입하려고하는 정렬 된 배열로 작업하고 있습니다. 나는 보통 코드를 이해하는 동안 코드를 이해하지만,이 코드는 나를 벗어나는 것처럼 보인다. 전반부가 무엇을하는지 이해합니다. 값을 넣을 위치를 검색합니다.

이제는 (int k = nElems; k> j; k--)에서 시작하는 두 번째 부분이 멈추는 곳입니다. 이것이 내가 말하고자하는 바라고 생각합니다. k를 원래 배열의 크기와 같게 설정하고 k가 크기 j가 될 때까지 감소시킵니다. 배열 위치 k를 k-1 (또는 아마도 j-1?)과 같게 설정하면 ... 그러면 [j] = 값;에 걸릴 것입니다.

누군가가 설명 할 수 있습니까? 일단 배열이 생성되면 불변이라고 생각했습니다. 새로운 배열이 만들어 질 것이라고 생각합니다.

public void insert(long value) // put element into array 
{ 
int j; 

for(j=0; j<nElems; j++)   // find where it goes 
if(a[j] > value) // (linear search) 
    break; 

for(int k=nElems; k>j; k--)  // move bigger ones up 
    a[k] = a[k-1]; 
a[j] = value;     // insert it 
nElems++;      // increment size 
} 

Answer 1

int k=nElems 

시작을위한 공간을 만들기 위해 삽입하기 전에 존재하지 않는 요소를 이동합니다. 우리가 목표 위치에 도달하지 않은 동안

k > j 

...

a[k] = a[k-1]; 

이동 오른쪽으로 한 위치까지 현재의 요소입니다.

k-- 

그리고 왼쪽으로 이동하십시오.

---

그래서 대상 위치와 끝 한 위치 사이의 모든 요소를 ​​오른쪽으로 이동하십시오.

일단 배열이 생성되면 불변이라고 생각했습니다.

배열 크기 한 번 만들어 고정 - 어떤 인덱스의 요소를 수정하거나 재 할당 그러나 당신이 맞는 볼 수 있습니다.

아마 여기에서 수행 된 작업 - 더 큰 배열이 만들어지고 채워진 값의 수를 나타 내기 위해 nElems이 사용되었습니다. 나머지 인덱스는 단지 null입니다. Wikipedia's article on dynamic arrays은 용량이 대 크기가 인 개념을 간단히 언급합니다. 용량은 a.length이고, 크기는 nElems입니다. 이는 ArrayList의 작동 방식과 동일합니다.

Answer 2

그것은 끝에 새 요소