[ Arrays for search, insert, delete ] Packed sorted

Packed sorted

• 정렬이 되어있다는 것을 가정하므로 search 시 binary search를 사용할 수 있음
• item의 개수를 표시하는 변수가 필요함 (packed의 특징)
• insert : search를 통해 계속 좁혀오다가, 두 개의 리턴 값을 보낼 수 있음 (그 사이 혹은 그 곳에 insert)

#include <stdio.h>

int a[100] = {0};
int size = 0;
int r, l, m;

int arr_search(int a[], int n, int x){
    int s, e, m;
    s = 0;
    e = n-1;
    while(s <= e){
        m = (s+e)/2;
        if(a[m] == x){
            r = l = m;
            return 1;
        }
        else if(a[m] > x) e = m-1;
        else s = m+1;
    }
    l = e;
    r = s;
    return -1;
}

void arr_insert(int a[], int n, int x){
    for(int i = size; i >= r; i--){
        a[i+1] = a[i];
    }
    a[r] = x;
    size++;
}

void arr_delete(int a[], int n, int x){
    for(int i = r; i < size; i++){
        a[i] = a[i+1];
    }
    size--;
}


int main(int argc, const char * argv[]) {
    
    int x;
    char choose;
    while(1){
        // 배열 출력
        for(int i = 0; i < size; i++) printf("%2d ", i);
        printf("\n");
        for(int i = 0; i < size; i++) printf("%2d ", a[i]);
        printf("\n");
        
        scanf(" %c", &choose);
        //search
        if (choose == 's'){
            scanf("%d", &x);
            int check = arr_search(a, size, x);
            if(check == -1) printf("There is no %d\n", x);
            else printf("There is %d in index %d\n", x, m);
        }
        
        //insert
        if (choose == 'i'){
            scanf("%d", &x);
            if(arr_search(a,size,x) == -1) {
                arr_insert(a,size,x);
                printf("%d is inserted in index %d\n", x, r);
            }
            else printf("already exists %d\n", x);
        }
        
        //delete
        if (choose == 'd'){
            scanf("%d", &x);
            if(arr_search(a,size,x) != -1) {
                arr_delete(a,size,x);
                printf("%d is deleted\n", x);
            }
            else printf("There is no %d\n", x);
        }
        
        //quit
        if (choose == 'q'){
            break;
        }
    }
}

 

*이진 탐색을 코딩하면서 논리적 오류가 발생함 > 재귀함수로는 구현이 힘든지 다시 한번 확인해야할 듯함

 

실행결과

 

• 정렬이 되어있음을 가정하므로 이진 탐색을 사용하여 search 함수를 구현하였다
• insert : 입력받은 수보다 큰 수들을 한 칸씩 뒤로 미루고, 그 칸에 입력받은 수를 넣는다. 배열의 크기 +1
• delete : 입력받은 수보다 큰 수들은 앞으로 한칸씩 땡기고, 배열의 크기 -1

성능

• Search : O(log n) - binary search
• insert : [search O(log n)] O(n) - n개 만큼 뒤로 미루는 연산이 필요함
• delete : [search O(log n)] O(n) - n개 만큼 앞으로 땡기는 연산이 필요함