fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5.  
  6. #define countof(array) (sizeof(array) / sizeof((array)[0]))
  7.  
  8. // Фтыкает value в нужное место массива array с текущим размером из length.
  9. // Кладет в length новый размер массива, возвращает индекс нового элемента.
  10. // Никаких реаллокаций не делает, подразумевая, что памяти хватит, чтобы
  11. // увеличить массив хотя бы на один элемент.
  12. static int insert(int value, int *array, int *length)
  13. {
  14.     int first = 0;
  15.     int last = *length - 1;
  16.     int pos = -1;
  17.  
  18.     // Специальный случай bsearch. Скукоживаем диапазон в поисках правильной
  19.     // позиции, в которую нужно записать значение.
  20.     while (first <= last) {
  21.         // Вычисляем индекс элемента в середине диапазона.
  22.         int i = first + (last - first) / 2;
  23.  
  24.         if (value < array[i]) {
  25.             // Фтыкаемое значение меньше текущего элемента. Ограничиваем
  26.             // диапазон сверху предыдущим элементом.
  27.             last = i - 1;
  28.         } else if (value > array[i]) {
  29.             // Фтыкаемое значение больше текущего элемента. Ограничиваем
  30.             // диапазон снизу.
  31.             first = i + 1;
  32.         } else {
  33.             // В массиве нашелся элемент с точно таким же значением.
  34.             pos = i;
  35.             break;
  36.         }
  37.     }
  38.  
  39.     if (pos < 0) {
  40.         // Если мы не нашли такой же элемент в массиве, тогда first равен
  41.         // позиции, где мы ожидали этот элемент увидеть.
  42.         pos = first;
  43.     }
  44.  
  45.     // Подвигаем хвост массива, чтобы освободить место под элемент.
  46.     memmove(array + pos + 1, array + pos, (size_t) (*length - pos) * sizeof(array[0]));
  47.  
  48.     // Фтыкаем элемент на его законное место.
  49.     array[pos] = value;
  50.  
  51.     // Обновляем length.
  52.     ++(*length);
  53.  
  54.     return pos;
  55. }
  56.  
  57. int main(void)
  58. {
  59.     srand((unsigned) time(NULL));
  60.  
  61.     int array[128];
  62.     int length = 0;
  63.  
  64.     // Зополняем массиф.
  65.     while (length < (int) countof(array))
  66.     {
  67.         int value = rand() % 300;
  68.         int pos = insert(value, array, &length);
  69.         printf("Inserted %d at %d\n", value, pos);
  70.     }
  71.  
  72.     // Выводем массиф.
  73.     for (int i = 0; i < length; ++i) {
  74.         printf("%3d: %-11d\n", i, array[i]);
  75.  
  76.         if (i + 1 < length && array[i] > array[i + 1]) {
  77.             printf("Pizdariki!\n");
  78.             exit(1);
  79.         }
  80.     }
  81. }
  82.  
Success #stdin #stdout 0s 9432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inserted 128 at 0
Inserted 195 at 1
Inserted 201 at 2
Inserted 207 at 3
Inserted 118 at 0
Inserted 161 at 2
Inserted 248 at 6
Inserted 167 at 3
Inserted 236 at 7
Inserted 148 at 2
Inserted 265 at 10
Inserted 290 at 11
Inserted 265 at 10
Inserted 138 at 2
Inserted 41 at 0
Inserted 189 at 7
Inserted 158 at 5
Inserted 64 at 1
Inserted 121 at 3
Inserted 211 at 14
Inserted 34 at 0
Inserted 272 at 20
Inserted 178 at 11
Inserted 17 at 0
Inserted 51 at 3
Inserted 86 at 5
Inserted 211 at 19
Inserted 141 at 10
Inserted 133 at 9
Inserted 229 at 23
Inserted 193 at 18
Inserted 262 at 27
Inserted 176 at 16
Inserted 146 at 12
Inserted 221 at 26
Inserted 295 at 35
Inserted 8 at 0
Inserted 170 at 18
Inserted 162 at 17
Inserted 296 at 39
Inserted 18 at 2
Inserted 179 at 23
Inserted 286 at 39
Inserted 36 at 4
Inserted 18 at 2
Inserted 28 at 4
Inserted 225 at 35
Inserted 228 at 36
Inserted 92 at 11
Inserted 98 at 12
Inserted 139 at 18
Inserted 179 at 29
Inserted 71 at 10
Inserted 69 at 10
Inserted 196 at 36
Inserted 174 at 29
Inserted 155 at 24
Inserted 159 at 26
Inserted 15 at 1
Inserted 289 at 56
Inserted 140 at 22
Inserted 208 at 44
Inserted 3 at 0
Inserted 17 at 3
Inserted 55 at 12
Inserted 224 at 51
Inserted 64 at 13
Inserted 63 at 13
Inserted 146 at 29
Inserted 226 at 56
Inserted 59 at 13
Inserted 217 at 54
Inserted 157 at 34
Inserted 46 at 11
Inserted 253 at 65
Inserted 227 at 61
Inserted 126 at 25
Inserted 230 at 65
Inserted 156 at 36
Inserted 218 at 59
Inserted 80 at 20
Inserted 295 at 79
Inserted 149 at 36
Inserted 151 at 37
Inserted 117 at 24
Inserted 45 at 11
Inserted 78 at 21
Inserted 272 at 80
Inserted 256 at 77
Inserted 93 at 25
Inserted 13 at 2
Inserted 97 at 27
Inserted 54 at 15
Inserted 16 at 4
Inserted 114 at 31
Inserted 109 at 31
Inserted 293 at 93
Inserted 178 at 59
Inserted 224 at 75
Inserted 139 at 40
Inserted 156 at 50
Inserted 35 at 11
Inserted 108 at 32
Inserted 65 at 23
Inserted 133 at 41
Inserted 113 at 35
Inserted 293 at 102
Inserted 259 at 94
Inserted 43 at 14
Inserted 149 at 53
Inserted 230 at 91
Inserted 124 at 41
Inserted 196 at 76
Inserted 79 at 28
Inserted 27 at 9
Inserted 13 at 2
Inserted 177 at 72
Inserted 105 at 37
Inserted 286 at 110
Inserted 133 at 49
Inserted 251 at 103
Inserted 51 at 19
Inserted 282 at 113
Inserted 5 at 1
Inserted 68 at 29
Inserted 96 at 38
Inserted 166 at 74
Inserted 113 at 44
  0: 3          
  1: 5          
  2: 8          
  3: 13         
  4: 13         
  5: 15         
  6: 16         
  7: 17         
  8: 17         
  9: 18         
 10: 18         
 11: 27         
 12: 28         
 13: 34         
 14: 35         
 15: 36         
 16: 41         
 17: 43         
 18: 45         
 19: 46         
 20: 51         
 21: 51         
 22: 54         
 23: 55         
 24: 59         
 25: 63         
 26: 64         
 27: 64         
 28: 65         
 29: 68         
 30: 69         
 31: 71         
 32: 78         
 33: 79         
 34: 80         
 35: 86         
 36: 92         
 37: 93         
 38: 96         
 39: 97         
 40: 98         
 41: 105        
 42: 108        
 43: 109        
 44: 113        
 45: 113        
 46: 114        
 47: 117        
 48: 118        
 49: 121        
 50: 124        
 51: 126        
 52: 128        
 53: 133        
 54: 133        
 55: 133        
 56: 138        
 57: 139        
 58: 139        
 59: 140        
 60: 141        
 61: 146        
 62: 146        
 63: 148        
 64: 149        
 65: 149        
 66: 151        
 67: 155        
 68: 156        
 69: 156        
 70: 157        
 71: 158        
 72: 159        
 73: 161        
 74: 162        
 75: 166        
 76: 167        
 77: 170        
 78: 174        
 79: 176        
 80: 177        
 81: 178        
 82: 178        
 83: 179        
 84: 179        
 85: 189        
 86: 193        
 87: 195        
 88: 196        
 89: 196        
 90: 201        
 91: 207        
 92: 208        
 93: 211        
 94: 211        
 95: 217        
 96: 218        
 97: 221        
 98: 224        
 99: 224        
100: 225        
101: 226        
102: 227        
103: 228        
104: 229        
105: 230        
106: 230        
107: 236        
108: 248        
109: 251        
110: 253        
111: 256        
112: 259        
113: 262        
114: 265        
115: 265        
116: 272        
117: 272        
118: 282        
119: 286        
120: 286        
121: 289        
122: 290        
123: 293        
124: 293        
125: 295        
126: 295        
127: 296
https://ideone.com/wp3PL0
language:
C99 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!