Chèn X vào dãy sao cho dãy vẫn có thứ tự tăng dần

Yêu cầu:

Cho dãy a gồm n số nguyên có thứ tự tăng dần. Nhập vào một phần tử nguyên X, viết hàm chèn X vào dãy sao cho dãy vẫn có thứ tự tăng dần(không sắp xếp).

Thuật toán:

Code:

/************************************************************
* Author: VNCODING
* History 
* 2014/11/17 first create VNCODING
*************************************************************/
#include "stdio.h"
#include "conio.h"
#include "string.h"

void insert_at_i_pos(int A[], int* n, int pos, int x);
void insert_arr(int A[], int* n, int x);
void print_arr(int A[], int n);

void main( void )
{
    int A[] = {-2, 3, 4, 7, 8, 11, 90, 100};
    int n = sizeof(A)/sizeof(int);

    print_arr(A, n);
    insert_arr(A, &n, 30);
    print_arr(A, n);

    getch();
}

//insert x into array
void insert_arr(int A[], int* n, int x)
{
    int i;
    for(i = 0; i < *n; i++)
    {
        if(x <= A[i])
        {
            insert_at_i_pos(A, n, i, x);
            return;
        }
    }
    (*n)++;
    A[i] = x;
}

//insert x at i position in array
void insert_at_i_pos(int A[], int* n, int pos, int x)
{
    int i;
    (*n)++;
    for(i = *n - 1; i > pos; i--)
    {
        A[i] = A[i-1];
    }
    A[i] = x;
}

//Display array
void print_arr(int A[], int n)
{
    int i;
    printf("\n=============================");
    for(i = 0; i < n; i++)
    {
        printf("\nA[%d] = %d", i, A[i]);
    }
}

Kết quả:

=============================
A[0] = -2
A[1] = 3
A[2] = 4
A[3] = 7
A[4] = 8
A[5] = 11
A[6] = 90
A[7] = 100
=============================
A[0] = -2
A[1] = 3
A[2] = 4
A[3] = 7
A[4] = 8
A[5] = 11
A[6] = 30
A[7] = 90
A[8] = 100