배열(array)은 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 대표적인 자료구조입니다. 이번 글에서는 그중에서도 항상 정렬된 상태를 유지하는 배열, 즉 정렬된 배열(sorted array)의 핵심 개념을 살펴보겠습니다.
일반적으로 배열을 사용하려면 데이터를 먼저 정렬해야 하는 경우가 많습니다. 하지만 애초에 정렬된 상태를 유지하도록 배열을 설계하면 매번 정렬 작업을 수행할 필요가 없습니다. 정렬된 배열은 탐색 속도가 빠르다는 장점 때문에 실무에서도 널리 활용됩니다.
삽입과 삭제의 핵심 아이디어
정렬된 배열에 요소를 삽입할 때는 새 요소가 자동으로 올바른 정렬 위치에 배치됩니다. 따라서 삽입 후에 다시 정렬할 필요가 없습니다. 반대로 삭제할 때는 해당 요소를 제거한 뒤, 그 뒤에 있는 요소들을 한 칸씩 앞으로 이동시켜 빈 공간을 채웁니다.
배열이 이미 정렬되어 있으므로, 삭제 전에 요소를 찾을 때는 선형 탐색보다 효율적인 이진 탐색(binary search) 알고리즘을 사용합니다. 이진 탐색의 시간 복잡도는 O(log n)으로, 배열 크기가 클수록 그 효과가 커집니다.
알고리즘
insertSorted(arr, n, key): Begin if n >= max size of the array, then return otherwise i := n – 1 while i >= 0 and arr[i] > key, do arr[i + 1] := arr[i] i := i - 1 done arr[i + 1] := key n := n + 1 End deleteSorted(arr, n, key): Begin pos := search key into arr if pos is -1, then item is not found, and return otherwise i := pos while i < n – 1, do arr[i] := arr[i + 1] i := i + 1 done n := n - 1 End
삽입 알고리즘은 배열 끝에서부터 시작해 key보다 큰 요소를 한 칸씩 뒤로 밀고, 빈자리에 key를 넣는 방식입니다. 삭제 알고리즘은 먼저 이진 탐색으로 key의 위치를 찾은 후, 그 위치부터 배열 끝까지 요소를 한 칸씩 앞으로 당겨 마무리합니다.
C++ 구현 예제
#include <iostream>
#define MAX 10
using namespace std;
void display(int arr[], int n){
for(int i = 0; i <n; i++){
cout << arr[i] << " ";
}
cout << endl;
}
int search(int arr[], int low, int high, int key){
if (high < low)
return -1;
int mid = (low + high) / 2; /*low + (high - low)/2;*/
if (key == arr[mid])
return mid;
if (key > arr[mid])
return search(arr, (mid + 1), high, key);
return search(arr, low, (mid - 1), key);
}
void insertSorted(int arr[], int &n, int key){
if (n >= MAX){
cout << "No place to insert";
return;
}
int i;
for (i = n - 1; (i >= 0 && arr[i] > key); i--)
arr[i + 1] = arr[i];
arr[i + 1] = key;
n = n + 1;
}
void deleteSorted(int arr[], int &n, int key){
int key_pos = search(arr, 0, n, key);
if(key_pos == -1){
cout << "Element is not present." << endl;
return;
}
int i;
for (i = key_pos; i < n - 1; i++)
arr[i] = arr[i + 1];
n = n - 1;
}
int main() {
int arr[MAX];
int n = 0;
insertSorted(arr, n, 10);
insertSorted(arr, n, 20);
insertSorted(arr, n, 30);
insertSorted(arr, n, 40);
insertSorted(arr, n, 50);
insertSorted(arr, n, 60);
insertSorted(arr, n, 70);
display(arr, n);
deleteSorted(arr, n, 35); // 존재하지 않는 요소
deleteSorted(arr, n, 40);
deleteSorted(arr, n, 60);
display(arr, n);
}실행 결과
10 20 30 40 50 60 70 Element is not present. 10 20 30 50 70
결과 분석
먼저 7개의 값을 차례로 삽입하면, 각 값이 항상 올바른 정렬 위치에 들어가므로 배열은 10 20 30 40 50 60 70 순서를 유지합니다. 이후 35를 삭제하려 했지만 배열에 존재하지 않아 "Element is not present."라는 안내 메시지가 출력됩니다. 마지막으로 40과 60을 삭제하면 뒤쪽 요소들이 한 칸씩 앞으로 이동하여 최종적으로 10 20 30 50 70이 됩니다.
성능 측면에서 보면, 삽입과 삭제 모두 최악의 경우 배열 전체를 이동시켜야 하므로 시간 복잡도는 O(n)입니다. 다만 삭제 시 요소를 찾는 과정은 이진 탐색 덕분에 O(log n)으로 처리됩니다. 잦은 조회와 함께 사용하는 정적 데이터 집합이라면 정렬된 배열은 여전히 훌륭한 선택지가 됩니다.