Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
0 / 0 / 1
Регистрация: 19.11.2017
Сообщений: 47
1

Вставить элемент в одномерный массив, не нарушая сортировку

01.04.2018, 17:33. Показов 2202. Ответов 14
Метки нет (Все метки)

Задача такая: Есть одномерный массив с числами, отсортированными по убыванию. Пользователь вводит два числа с клавиатуры и они должны вставиться в массив, не нарушая сортировку.

Надеюсь на вашу помощь
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.04.2018, 17:33
Ответы с готовыми решениями:

Удалить k-ый элемент массива А и вставить в массив число Р, не нарушая упорядоченности
Дано упорядоченный по возрастанию массив целых чисел А (n), натуральное число k <= N и целое число...

Удалить k-й элемент массива А и вставить в массив число Р, не нарушая упорядоченности
Дано упорядоченный по увеличению массив целых чисел А(n), натуральное число k<=N и целое число Р....

Вставить в массив строк новый элемент, не нарушая алфавитный порядок
Добрый день. Нужно вставить в массив строку не нарушая его алфавитный порядок. Пытался это...

Вставить в одномерный массив элемент
Вставить в одномерный массив элемент)

14
Эксперт по компьютерным сетям
4834 / 2732 / 833
Регистрация: 03.11.2009
Сообщений: 8,408
Записей в блоге: 3
01.04.2018, 17:50 2
То есть нужно добавить в массив и отсортировать еще раз? С чем именно из этого проблемы?
0
0 / 0 / 1
Регистрация: 19.11.2017
Сообщений: 47
01.04.2018, 22:15  [ТС] 3
Массивы только изучать начали, пока что ещё не сильно разбираюсь, не знаю как их сортировать(
0
Эксперт по компьютерным сетям
4834 / 2732 / 833
Регистрация: 03.11.2009
Сообщений: 8,408
Записей в блоге: 3
01.04.2018, 23:00 4
Можно и не сортировать - можно, например, создать новый массив, перенося по одному из начального, с условием, что если старый элемент больше или равен, тому, что нужно вставить, а следующий уже меньше - вот тут и нужно вставить добавленный.

Добавлено через 1 минуту
а можно не париться, и просто отсортировать заново. сортировать можно, например, используя встроенную функцию qsort, там реализовать нужно будет только функцию сравнения.
0
0 / 0 / 1
Регистрация: 19.11.2017
Сообщений: 47
04.04.2018, 21:17  [ТС] 5
Скажите, что здесь может быть неправильно. Я вставляю числа 15 и 13, но выводится:

11
12
13
14
15
15


А нужно, чтобы от 11 до 17 включительно

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
 
int main(void)
{
    int a[6]={17, 16, 14, 12, 11};
    int i, j, temp;
    
    printf("Input two numbers: \n");
    for (i = 0; i < 2; i++)
        scanf("%d", &a[i]);
    for (i = 1; i < 8; i++) {
        temp = a[i];
        for (j = i - 1; j >= 0; j--)
            if (temp < a[j]) {
                a[j + 1] = a[j];
                a[j] = temp;
            }
    }
    for (i = 1; i < 7; i++)
        printf("%d\n", a[i]);
    return 0;
}
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5961 / 3549 / 2493
Регистрация: 22.11.2013
Сообщений: 10,051
Записей в блоге: 1
05.04.2018, 15:49 6
Лучший ответ Сообщение было отмечено _MrJaycob_ как решение

Решение

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
int main(void)
{
#define SZ 7
  int a[SZ] = {17, 16, 14, 12, 11};
  int n, i, t;
  for (n=5; n<SZ; ++n)
  {
    scanf(" %d", &a[n]);
    for (i=n; i-->0;)
      if (a[i]<a[i+1])
      {
        t=a[i]; a[i]=a[i+1]; a[i+1]=t;
      }
  }
  for (i=0; i<SZ; ++i)
    printf(" %d", a[i]);
  return 0;
}
Добавлено через 4 минуты
Но лучше:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
int main(void)
{
#define SZ 7
  int a[SZ] = {17, 16, 14, 12, 11};
  int n, i, t;
  for (n=5; n<SZ; ++n)
  {
    scanf(" %d", &a[n]);
    for (i=n; i-->0 && a[i]<a[i+1];)
    {
      t=a[i]; a[i]=a[i+1]; a[i+1]=t;
    }
  }
  for (i=0; i<SZ; ++i)
    printf(" %d", a[i]);
  return 0;
}
Добавлено через 7 минут
А еще лучше:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
 
int main(void)
{
#define SZ 7
  int a[SZ] = {17, 16, 14, 12, 11};
  int n, i, t;
  for (n=5; n<SZ; ++n)
  {
    scanf(" %d", &t);
    for (i=n; i-->0 && a[i]<t;)
      a[i+1]=a[i];
    a[i+1]=t;
  }
  for (i=0; i<SZ; ++i)
    printf(" %d", a[i]);
  return 0;
}
Добавлено через 49 минут
Нужно понимать, что если речь идет об установке на место не пары чисел, а существенно большего количества, то оптимальной стратегией будет добавить числа в хвост массива и отсортировать его заново. Впрочем, выше этот совет уже давали.
0
Форумчанин
Эксперт CЭксперт С++
8170 / 5020 / 1436
Регистрация: 29.11.2010
Сообщений: 13,453
05.04.2018, 16:56 7
Цитата Сообщение от _MrJaycob_ Посмотреть сообщение
вставиться в массив
В си нельзя "расширять" массивы. Можно только создать новый большего размера и переписать туда данные в нужном порядке.
0
0 / 0 / 1
Регистрация: 19.11.2017
Сообщений: 47
05.04.2018, 19:24  [ТС] 8
Хорошо, спасибо за ответы)
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
29990 / 16467 / 3334
Регистрация: 12.02.2012
Сообщений: 27,402
Записей в блоге: 5
06.04.2018, 10:03 9
Цитата Сообщение от MrGluck Посмотреть сообщение
В си нельзя "расширять" массивы.
- почему же? А realloc? Конечно, лучше вставлять, чем сортировать заново (если число вставляемых много меньше размера массива). Я бы "дописывание в хвост и сортировку" просто не зачел бы...
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5961 / 3549 / 2493
Регистрация: 22.11.2013
Сообщений: 10,051
Записей в блоге: 1
06.04.2018, 10:11 10
Цитата Сообщение от Catstail Посмотреть сообщение
лучше вставлять, чем сортировать заново
... получив заведомо O(n2) вместо того, что в выбранной сортировке
Даже если поискать место вставки двоичным поиском, то это ничего не даст (точнее даст экономию сравнений, то есть выигрыш будет только на дорогих сравнениях, скажем, strcmp()) -- сдвигать "хвост" придется все равно.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
29990 / 16467 / 3334
Регистрация: 12.02.2012
Сообщений: 27,402
Записей в блоге: 5
06.04.2018, 10:18 11
Вставлять можно по-разному. Если с умом (предварительно отсортировав... небольшое количество вставляемых элементов, а не весь массив), то будет не O(n2), а O(n).
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5961 / 3549 / 2493
Регистрация: 22.11.2013
Сообщений: 10,051
Записей в блоге: 1
06.04.2018, 14:00 12
Цитата Сообщение от Catstail Посмотреть сообщение
Если с умом
Кстати, да, если для вставки n элементов делать не n шагов пузырька, а сортировку вставляемого массива и один шаг сортировки слиянием, будет довольно хорошо по скорости и пенальти по памяти для n элементов.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
29990 / 16467 / 3334
Регистрация: 12.02.2012
Сообщений: 27,402
Записей в блоге: 5
06.04.2018, 23:33 13
Как вариант:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <stdlib.h>
 
int *insInSortArr(int *B, int n, int *A, int k)
{
    int i,j,tmp;
    int i_from,i_to,i_a;
    
    B=(int *) realloc(B, (n+k)*sizeof(int));
    
    for(i=0; i<k-1; i++)
       for (j=i+1; j<k; j++)
           if (A[i]>A[j])
           {
              tmp=A[i];
              A[i]=A[j];
              A[j]=tmp;
           }           
 
    i_from=n-1;
    i_to=n+k-1;
    i_a=k-1; 
    
    while (1)
    {
       if (i_from < 0) break;
          
       if (i_a>=0)
       {
          if (B[i_from] <= A[i_a])
             B[i_to--]=A[i_a--]; 
          else
             B[i_to--]=B[i_from--];
       }
       else
          B[i_to--]=B[i_from--];
    }             
      
    while(i_to>=0) B[i_to--]=A[i_a--];
    
    return B; 
}     
 
int main(int argc, char *argv[])
{
 
  int *X,*Y;
  int i;
  
  X=(int *) calloc(20,sizeof(int));
  Y=(int *) calloc(5,sizeof(int)); 
  
  for (i=0; i<20; i++) X[i]=2*i+1;
  
  for (i=0; i<5; i++) Y[i]=i;
  
  X=insInSortArr(X,20,Y,5);
  
  for (i=0; i<25; i++) printf("%d %d\n",i,X[i]);
  printf("\n");
  
  free(X);
  free(Y);
  
  system("PAUSE");  
  return 0;
}
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5961 / 3549 / 2493
Регистрация: 22.11.2013
Сообщений: 10,051
Записей в блоге: 1
07.04.2018, 09:23 14
Catstail,
Ох, не стоит внутрь функции слияния realloc тянуть...
Не очень удачная декомпозиция получилась.
1) Много лучше, когда вызывающий предоставляет готовые буферы необходимого размера. Тогда это может быть не только динамика, но и стек, и статика.
2) Сортировка второго массива внутри — тоже не очень. Допустим, нужно добавлять одно и то же к нескольким массивам — лишние накладные расходы, проще наложить требование на одинаковую упорядоченность и передавать функцию сравнения, как в qsort. Заодно и унификацию получим по наименьшему удивлению.
3) Слияние можно остановить, как только в A не осталось элементов.

Сейчас с телефона, код позже.

Добавлено через 25 минут
Сама идея, без сортировок:
Кликните здесь для просмотра всего текста
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
void merge(int *a, int an, int *b, int bn);
 
int main(void)
{
#define SZ 7
    int a[SZ] = {6, 5, 3, 2};
    int b[] = {7, 4, 1};
    merge(a,4, b,3);
    for (int i=0; i<SZ; ++i) printf(" %d", a[i]);
    return 0;
}
 
void merge(int *a, int an, int *b, int bn)
{
    int n = --an + --bn + 1;
    while (bn>=0 && an>=0) a[n--] = b[bn] < a[an] ? b[bn--] : a[an--];
    while (bn>=0)          a[n--] =                 b[bn--];
}

Добавлено через 16 минут
Добавим сортировки:
Кликните здесь для просмотра всего текста
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdlib.h>
#include <stdio.h>
 
void merge(int *a, int an, int *b, int bn, int (*compare)(const int *, const int *));
int more(const int *a, const int *b);
 
int main(void)
{
#define SZ 7
    int a[SZ] = {6, 5, 2, 3};
    int b[] = {7, 1, 4};
    qsort(a, 4, sizeof(*a), more);
    qsort(b, 3, sizeof(*b), more);
    merge(a,4, b,3, more);
    for (int i=0; i<SZ; ++i) printf(" %d", a[i]);
    return 0;
}
 
void merge(int *a, int an, int *b, int bn, int (*compare)(const int *, const int *))
{
    int n = --an + --bn + 1;
    while (bn>=0 && an>=0) 
        a[n--] = compare(&a[an], &b[bn]) < 0 ? 
                 b[bn--] : a[an--];
    while (bn>=0)
        a[n--] = b[bn--];
}
 
int more(const int *a, const int *b)
{
    return *b - *a;
}

Добавлено через 9 минут
Вернемся к условию и добавим ввод с клавиатуры:
Кликните здесь для просмотра всего текста
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdlib.h>
#include <stdio.h>
 
void merge(int *a, int an, int *b, int bn, int (*compare)(const int *, const int *));
int desc(const int *a, const int *b);
 
int main(void)
{
#define SZ 7
    int a[SZ] = {17, 16, 14, 12, 11}, b[2];
    for (int i=0; i<sizeof(b)/sizeof(*b); ++i) scanf(" %d",&b[i]);
    qsort(b, sizeof(b)/sizeof(*b), sizeof(*b), desc);
    merge(a,5, b,sizeof(b)/sizeof(*b), desc);
    for (int i=0; i<SZ; ++i) printf(" %d", a[i]);
    return 0;
}
 
void merge(int *a, int an, int *b, int bn, int (*compare)(const int *, const int *))
{
    int n = --an + --bn + 1;
    while (bn>=0 && an>=0) 
        a[n--] = compare(&a[an], &b[bn]) < 0 ? 
                 b[bn--] : a[an--];
    while (bn>=0)
        a[n--] = b[bn--];
}
 
int desc(const int *a, const int *b)
{
    return *b - *a;
}
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
29990 / 16467 / 3334
Регистрация: 12.02.2012
Сообщений: 27,402
Записей в блоге: 5
07.04.2018, 09:48 15
Цитата Сообщение от bormant Посмотреть сообщение
Ох, не стоит внутрь функции слияния realloc тянуть...
Не очень удачная декомпозиция получилась.
- дело вкуса. realloc можно выпонить и за пределами слияния. Суть не меняется, ибо она состоит не в этом.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.04.2018, 09:48

Вставить элемент в одномерный массив
люди, помогите решить задачку...я недавно начал изучать паскаль и видимо чего-то не понял(даже...

Одномерный массив: вставить нулевой элемент в пятую позицию
вставить нулевой элемент в пятую позицию.при этом все элементы начиная с пятого должны сдвинуться...

Вставить числа в массив, не нарушая упорядоченности
В упорядоченный по возрастанию числовой массив из 15 элементов вставить числа -2 и 5, не нарушая...

Вставить в массив число, не нарушая упорядоченности
Сделать и подсчитать глубину рекурсии для задачи: Разработать функцию, которая вставляет в массив...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.