배열이 주어진 순서대로 요소를 삽입하는 방법은 무엇입니까?

Question

배열에 다음과 같은 숫자가 있다고 가정 해 봅시다. 1, 3, 6, 15 사용자가 숫자 5와 같은 특정 정수를 입력하면 위 배열에서 올바른 순서로 삽입 할 수있는 방법보다 다음과 같은 새 배열을 인쇄 할 수 있습니다. 1, 3, 5, 6, 15. 사용할 배열은 가변 길이 배열이며 사용자가 배열의 숫자를 정렬 된 비 - 정렬 순서가 필요하지 않으므로 정렬 할 필요가 없으며 사용자가 입력 한 요소를 올바른 위치에 삽입하기 만하면됩니다. 아래 코드는 배열에 x를 삽입하는 데 어떤 명령을 사용해야할지 모르기 때문에 내가 얼마나 멀리 있는지에 대한 코드를 가지고 있으며 C 프로그래밍의 초보자입니다.

#include <stdio.h> 

int insertion_array (int n, int ary[*]); 

int main (void) 
{ 

    int n; // size  
    int x; // The element to be inserted in the array  
    int i, j; 
    printf("Enter size of array: "); 

    scanf("%d", &n); 
    printf("Enter the value of x: "); 

    scanf("%d", &x); 

    int ary[n];  
    for(i = 0; i < n; i++) 
    { 
     printf("Enter number %d: ", i + 1); 
     scanf("%d", &ary[i]); 
    } // for 

    return 0; 
} // main 

Answer 1

나는 간단한 O (n)이 알고리즘으로 올 수 :

1. 사용 이진 검색 삽입 할 수있는 장소를 찾을 수는 위치 5
2. 변화 모든 숫자 위치 (5) 바로
후 말 새로운 정수
3. 할당 위치 5

그러나 등 O (LGN) 삽입 알고리즘 말할 AVL 트리, RB 트리 및 거기 그러나 훨씬 더 복잡합니다.

#include <stdio.h> 
#include <stdlib.h> 

int binsearch(int *arr, int size, int key) 
{ 
    int low = 0, high = size - 1; 

    if (key > arr[high]) return size; 

    while (high > low) { 
    int mid = (low + high)/2; 
    if (arr[mid] > key) high = mid; 
    else low = mid + 1; 
    } 

    return low; 
} 

int main() 
{ 
    int size = 10; 
    int *arr = (int *)malloc(size * sizeof(int)); 

    int elem, len = 0; 
    arr[len++] = 0; 

    while (scanf("%d", &elem) != EOF) { 

    int pos = binsearch(arr, len, elem); 

    printf("%d\n", pos); 

    int i; 
    for (i = len-1; i >= pos; --i) 
     arr[i+1] = arr[i]; 
    arr[pos] = elem; 

    ++len; 

    for (i = 0; i < len; ++i) 
     printf("%d ", arr[i]); 
    printf("\n"); 
    } 

    free(arr); 

    return 0; 
}