[자료구조] 정렬된 배열

  정렬된 배열(ordered array)은 배열과 거의 같다. 단지 그 값이 항상 순서대로 있어야 한다는 점이다. 값을 추가할 때마다 배열의 값이 정렬된 상태가 되도록 한다. 하지만 이런 순서를 지키기 위해서는 여러 단계가 필요하다. 항상 실제 삽입 전에 검색을 먼저 수행해서 삽입할 정확한 위치를 알아내야 한다. 이것은 삽입에 있어서 효율을 많이 떨어트리게 된다. 하지만 정렬된 배열의 강력함은 검색 연산에서 드러난다.

 

  배열과 정렬된 배열을 선형 검색으로 검색을 시도하면 정렬된 배열의 장점은 값이 없을 경우 더 빨리 멈출 수 있다는 점 밖에는 없다. 찾으려는 데이터가 발견되지 않고 더 큰 데이터가 나타날 때 정렬된 배열은 바로 멈출 수 있기 때문이다. 대단한 차이가 없어 보인다.

 

  하지만 정렬된 배열에는 알고리즘의 능력을 더할 수 있다.

---

이진 검색

  이진 검색은 데이터의 절반을 가르며 찾아가는 방법이다. 원소 9개를 포함하는 정렬된 배열이 있다고 하자.

  정렬된 배열에서 값 7을 찾는다고 하면 다음과 같은 순서로 동작하게 된다.

  이진 검색은 4 단계 만에 7을 성공적으로 찾았다. 간단한 예제여서 선형 검색과 같은 수의 단계가 걸렸지만 데이터의 수가 급격하게 늘어날수록 그 강력함이 드러난다.

---

이진 검색 vs 선형 검색

  100개의 값을 갖는 배열에서 각 검색에 필요한 최대 단계 수는 다음과 같다.

• 선형 검색 : 100단계
• 이진 검색 : 7단계

  선형 검색에서는 찾고 있는 값이 마지막 셀에 있다면 모든 원소를 조사해야 한다. 반면에 이진 검색은 추측할 때마다 검색해야 할 셀 중 절반을 제거함으로 그 단계를 줄일 수 있다.

  선형 검색은 원소의 개수가 늘어나는 만큼의 단계가 필요하지만 이진 검색은 원소의 개수의 두 배로 늘 때 한 단계가 더 필요하게 되는 것이다. 정렬된 배열은 삽입에서 다소 느려지지만 검색에서는 훨씬 빠르게 된다. 데이터의 목적에 따라 알고리즘을 정확하게 선택해야 한다.