Включить элемент в упорядоченный по убыванию массив, не нарушая упорядоченности - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Задан упорядоченный по убыванию массив F=F(i), i=1,2,...N. Включить число Z в массив F, не нарушая упорядоченности. Вывести полученный массив F=F(i), i=1,2,...,N+1

Решение задачи: «Включить элемент в упорядоченный по убыванию массив, не нарушая упорядоченности»

textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
//Задан упорядоченный по убыванию массив F=F(i), i=1,2,...N. Включить число Z
//в массив F, не нарушая упорядоченности. Вывести полученный массив F=F(i), i=1,2,...,N+1
void Sort_on_decrease(int *p, int N)//сортирует по убыванию,N-размер массива
{
    int i, j, max, x;
    for(i = 0; i < N - 1; ++i){
        max = i;
        for(j = i + 1; j < N; ++j){
        if(p[j] > p[max])
            max = j;
        }
        if(max != i){
            x = p[i]; p[i] = p[max];
            p[max] = x;
        }
    }
}
int binary_search(int *p, int R, int Z)//бинарный поиск,возвращает индекс элемента,на место
{ //которого нужно вставить введенный с клавиатуры элемент,R-размер массива,Z-введенное число
    --R;
    int L = 0, mid;
    while(L < R){
        mid = (L + R) / 2;
        if(p[mid] == Z){
            break;
        }
        else{
            if((p[mid] < Z))
                R = mid - 1;
            else
                L = mid + 1;
        }
        if(R - L <= 8){
            while(p[R] < Z)
                --R;
            mid = R + 1;
            break;
        }
    }
    return mid;
}
int main()
{
    int i, j, bs, N, Z, *p;
    puts("Input array size:");
    if(!scanf("%d", &N)){
        fprintf(stderr,"%s\n", "Incorrect input!");
        exit(1);
    }
    p = malloc((N + 1) * sizeof p);
    if(p == NULL){
        fprintf(stderr,"%s\n", "Memory allocation error!");
        exit(2);}
    for(i = 0; i < N; ++i)
        printf("%d ", p[i] = rand() % 1000);
    printf("\n");
    Sort_on_decrease(p, N);
    for(i = 0; i < N; ++i)
        printf("%d ", p[i]);
    printf("\n");
    puts("Input number Z:");
    if(!scanf("%d", &Z)){
        fprintf(stderr,"%s\n", "Incorrect input!");
        exit(3);
    }
    bs = binary_search(p, N, Z);
    for(i = N + 1, j = N; j >= bs; --i, --j)
        p[i] = p[j];
    p[bs] = Z;
    for(i = 0; i < N + 1; ++i)
        printf("%d ", p[i]);
    free(p);
    return 0;
}

Объяснение кода листинга программы

  1. В начале кода подключаются необходимые библиотеки: stdlib.h для работы с массивами и scanf/printf для взаимодействия с пользователем.
  2. Затем определены две функции: Sort_on_decrease() и binary_search().
  3. Функция Sort_on_decrease() сортирует массив по убыванию с помощью алгоритма сортировки пузырьком.
  4. Функция binary_search() выполняет бинарный поиск в отсортированном массиве для нахождения места, на которое нужно вставить новый элемент.
  5. В функции main() сперва запрашивается размер массива, который будет заполнен случайными числами.
  6. Затем массив заполняется случайными числами, сортируется по убыванию и выводится на экран.
  7. После этого пользователю предлагается ввести число, которое нужно вставить в массив.
  8. Функция binary_search() находит место для вставки этого числа в отсортированный массив.
  9. Затем, используя цикл, элементы массива сдвигаются вправо, чтобы освободить место для нового элемента.
  10. В конце новый элемент вставляется на найденное место, и весь массив выводится на экран.
  11. В конце программы освобождается память, выделенная под массив.

Оцени полезность:

14   голосов , оценка 4.214 из 5
Похожие ответы