프로그램을 만들다 보면 삽입하면서 정렬이 유지돼야 될 때가 많습니다!

한 번에 삽입을 다 하고 정렬을 한다면,
배열에 모두 저장하고(O(n)) 퀵 정렬(O(nlogn)을 하는 방식으로 해결이 가능합니다.
혹은 힙에 넣고(O(n)) 힙 정렬(O(nlog))을 하는 방식을 이용하면 최댓값 삭제도 용이할 것입니다!

그런데 동적으로 삽입을 해야 되는 경우도 있습니다.
이럴 때가 바로 삽입하면서 정렬이 유지돼야 될 때입니다.

예를 들어 게임 랭킹 시스템은 레벨 별로 내림차순을 유지해야 합니다!
어떤 한 유저가 레벨을 올려서 랭킹권에 추가되더라도 내림차순은 유지돼야 합니다.

이는 자료구조(Data Structure)의 리스트를 배웠다면 쉽게 구축할 수 있습니다.

아래에 해당 프로그램 C언어 소스를 제공합니다!
설명은 주석을 참조해주세요!

시간복잡도는 O(n)을 만족합니다!
만약 일반적인 삭제가 아니라 최대/최소값 삭제만 한다면 힙(Heap)을 이용하는 편이 훨씬 좋습니다!

#include <stdio.h>
#define max 100
typedef struct {
	int array[max];
	int size;
}ArrayListType;
typedef ArrayListType * ArrayList_ptr;


void init(ArrayList_ptr list) {
	list->size = 0;
}

int is_empty(ArrayListType list) {
	if (list.size == 0)
		return 1;
	else
		return 0;
}

int is_full(ArrayListType list) {
	if (list.size == max)
		return 1;
	else
		return 0;
}

// 이진탐색으로 item이 속한 idx찾기 
int search_idx(ArrayList_ptr list,int item) {
	int high = list->size-1;
	int low = 0;

	while (low <= high) {
		int mid = (low + high) / 2;

		if (list->array[mid] == item)
			return mid;
		else if (item > list->array[mid])
			low = mid + 1;
		else
			high = mid - 1;
	}
	if (low > high)
		return -1;
}

void insert(ArrayList_ptr list, int item) {
	if (!is_full(*list)) {
		// (pos: 삽입할 올바른 위치) 찾기
		int pos = 0;
		for (int i = 0; i < list->size; i++) {
			// 정렬이 필요한 경우
			// (=) 리스트 원소들 중 item보다 큰 것이 있는 경우 
			if (item <= list->array[i]) {
				pos = i;
				// list[pos]~list[size-1]까지 뒤로 보내기 
				for (int i = list->size - 1; i >= pos; i--)
					list->array[i + 1] = list->array[i];
				break;
			}
			// 정렬이 필요없는 경우 (insert_last)
			else if(i==list->size-1)
				pos = list->size;
		}
		// item 삽입 
		list->array[pos] = item;
		list->size++;
	}
	else
		printf("리스트가 꽉 차있습니다\n");
}

// 리스트 자료구조의 delete 함수를 변형 
int delete(ArrayList_ptr list, int item) {
	if (!is_empty(*list)) {
		int pos;
                // 배열에 해당 아이템이 있는 경우 
		if ((pos=search_idx(list,item)) != -1) {
			int tmp = list->array[pos];
			for (int i = pos + 1; i < list->size; i++)
				list->array[i - 1] = list->array[i];
			list->size--;
			return tmp;
		}
		else
			printf("해당 원소(%d)는 존재하지 않습니다.\n",item);
	}
	else
		printf("리스트가 비어 있습니다\n");
}


void print_list(ArrayListType list) {
	for (int i = 0; i < list.size; i++)
		printf("%d ", list.array[i]);
	printf("size:%d\n", list.size);
}

int main() {
	ArrayListType list;
	init(&list);

	printf("삽입:\n");
	insert(&list, 10);
	insert(&list, 9);
	insert(&list, 8);
	insert(&list, 11);
	insert(&list, 12);
	insert(&list, 16);
	insert(&list, 7);
	print_list(list);

	printf("\n삭제:\n");
	delete(&list, 10);
	delete(&list, 9);
	delete(&list, 8);
	delete(&list, 11);
	delete(&list, 100); // 리스트에 존재하지 않는 원소 삭제 
	print_list(list);
}

참고) 배열을 이용한 리스트 자료구조 소스: https://shacoding.com/2019/07/26/data-structure-list-by-array-c/