[ Arrays for search, insert, delete ] Unpacked unsorted & Unpacked sorted

Unpacked unsorted

• 빈 자리들이 흩어져 있음 - item 별로 사용중인지 아닌지 표시가 필요함
• free list head로 빈 칸들의 리스트를 만든다
  • 빈 칸인 인덱스를 계속 따라가면 다른 빈 칸인 인덱스를 알 수 있음
  • 실제 free block의 번호 > 다음 free block 의 번호
• search : O(n) - binary search
• insert : [search O(n)] O(n) (free list head 추가시 O(1))
• delete : [search O(n)] O(1)

Unpacked sorted

• 지울 때 값을 지우는 것이 아닌 다른 배열에 존재 하는지 하지 않는지 마킹함
• 지우지 않은 칸, 지운 칸 모두 유지해서 sorting order가 맞아야함

#include <stdio.h>

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

int arr_search(int a[], int n, int x){
    int s = 0;
    int e = n-1;
    while(s<=e){
        int m = (s+e)/2;
        if(a[m] == x){
            l = r = m;
            if(b[m] == 0) return -1;
            else 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){
    if(r == l) b[r] = 1;
    else if(l == -1) {
        int i, j;
        i = r;
        while(b[i] == 1 && i < size) i++;
        for(j = i-1; j >= r; j--) {
            a[j+1] = a[j];
            b[j+1] = b[j];
        }
        a[r] = x;
        b[r] = 1;
        if(i == size)size++;
        printf("%d has inserted in index %d\n", x, r);
    }
    else if(r == size){
        int i, j;
        i = l;
        while(b[i] == 1 && i >= 0) i--;
        if(i == -1) {
            a[size] = x;
            b[size] = 1;
            size++;
            printf("%d has inserted in index %d\n", x, r);
        }
        else{
            for(j = i; j < r; j++){
                a[j] = a[j+1];
                b[j] = b[j+1];
            }
            a[r-1] = x;
            b[r-1] = 1;
            printf("%d has inserted in index %d\n", x, r-1);
        }
    }
    else{
        int i, j;
        i = l;
        while(b[i] == 1 && i >= 0) i--;
        if(i != -1){
            for(j = i; j < r; j++){
                a[j] = a[j+1];
                b[j] = b[j+1];
            }
            a[l] = x;
            b[l] = 1;
            printf("%d has inserted in index %d\n", x, l);
        }
        else{
            i = r;
            while(b[i] == 1 && i <= size) i++;
            if(i != size){
                for (j = i-1; j >= r; j--){
                    a[j+1] = a[j];
                    b[j+1] = b[j];
                }
                a[r] = x;
                b[r] = 1;
                printf("%d has inserted in index %d\n", x, r);
            }
            else{
                for (j = i-1; j >= r; j--){
                    a[j+1] = a[j];
                    b[j+1] = b[j];
                }
                a[r] = x;
                b[r] = 1;
                size++;
                printf("%d has inserted in index %d\n", x, r);
            }
        }
    }
}

void arr_delete(int a[], int n, int x){
    if(r == l) b[r] = 0;
    else {
        for(int i = r; i < size; i++){
            a[i] = a[i+1];
            b[i] = b[i+1];
        }
    }
}
int main(int argc, const char * argv[]) {
    int x;
    char choose;
    while(1){
        // 배열 출력
        printf("s = %d\n", size);
        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");
        for(int i = 0; i < size; i++) printf("%2d ", b[i]);
        printf("\n");
        
        scanf(" %c", &choose);
        //search
        if (choose == 's'){
            scanf("%d", &x);
            int check = arr_search(a, size, x);
            if(check == -1 && r!=l ) printf("there is no data %d, it must be between %d and % d\n", x, l, r);
            else if(b[r] == 0 && check == -1) printf("%d data is stored but is deleted at index %d\n", x, r);
            else{
                printf("Data is at index %d\n", r);
            }
        }
            
        //insert
        if (choose == 'i'){
            scanf("%d", &x);
            if (arr_search(a, size, x) == 1) printf("%d already exists\n", x);
            else arr_insert(a, size, x);
        }
        //delete
        if (choose == 'd'){
            scanf("%d", &x);
            if(arr_search(a, size, x) == -1) printf("%d is not exists\n",x);
            else arr_delete(a, size, x);
        }
        //quit
        if (choose == 'q'){
            break;
        }
    }
}

실행결과

• search : O(log n)
• insert : O(n)
• delete : O(1)