[자료구조] 정렬된 배열

정렬된 배열은 값이 항상 순서대로 있어야 하는 배열이다. 

 

[1,2,4,5]라는 배열이 있다고 가정하자. 3을 삽입한다고 예시를 들면 일반 배열과 정렬된 배열은 다음과 같다.

 

일반 배열

1. 5를 인덱스 4로 옮긴다.

2. 4를 인덱스 3으로 옮긴다.

3. 3을 인덱스 2에 넣는다.

정렬된 배열

1. 0번 인덱스를 확인한다. 1은 3보다 작다. 다음 인덱스로 넘어간다.

2. 1번 인덱스를 확인한다. 2는 3보다 작다. 다음 인덱스로 넘어간다.

3. 2번 인덱스를 확인한다. 4는 3보다 크다. 넣을 인덱스를 정한다.

4. 5를 인덱스 4로 옮긴다.

5. 4를 인덱스 3으로 옮긴다.

6. 3을 인덱스 2에 넣는다.

 

정렬된 배열이 일반 배열보다 삽입하는 데 걸리는 단계가 더 많음을 알 수 있다. 하지만 정렬된 배열의 검색 등의 활용이 더 유용하기 때문에 정렬된 배열을 사용한다.

 

그리고 정렬된 배열에 큰 값을 넣든 작은 값을 넣든 단계는 비슷하다. 검색이 줄어들면 삽입이 늘어나고 삽입이 줄어들면 검색이 늘어나기 때문이다.