Page 22 -

3단계: "cucumbers"를 오른쪽으로 옮긴다.

그림 1-14
ˮfigsˮ

ˮapplesˮ ˮbananasˮ ˮcucumbersˮ ˮdatesˮ ˮelderberriesˮ

4단계: "figs"를 인덱스 2에 삽입한다.

그림 1-15

ˮapplesˮ ˮbananasˮ ˮfigsˮ ˮcucumbersˮ ˮdatesˮ ˮelderberriesˮ

예제를 통해 4단계가 필요함을 알았다. 데이터를 오른쪽으로 옮기는 3단계와
실제로 새 값을 삽입하는 1단계다.

배열 삽입에서 최악의 시나리오, 즉 삽입에 가장 많은 단계가 걸리는 시나리오
는 데이터를 배열의 맨 앞에 삽입할 때다. 배열의 앞에 삽입하면 배열 내 모든
값을 한 셀씩 오른쪽으로 옮겨야 하기 때문이다.

다시 말해 원소 N개를 포함하는 배열에서 최악의 시나리오일 때 삽입에는
N+1단계가 걸린다. 최악의 시나리오에서는 N번의 이동(배열의 모든 데이터
원소)과 1번의 삽입으로 배열의 맨 앞에 값을 삽입하기 때문이다.

마지막으로 알아볼 연산인 삭제는 삽입과 비슷하나 순서가 반대다.

1장 자료 구조가 중요한 까닭 033

algorith06.indd 33 2018-06-25 오전 10:32:04