C shellsorting random int array

Question

I've run into a problem when writing simple program to shellsort array of random numbers. Program doesn't sort it, just prints 1,1,1,1,1 or 0,0,0,0,0 even though shellsort algorithm is from rosettacode so it should be correct.

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

void shell_sort (int *a, int n) {
    int h, i, j, t;
    for (h = n; h /= 2;) {
        for (i = h; i < n; i++) {
            t = a[i];
            for (j = i; j >= h && t < a[j - h]; j -= h) {
                a[j] = a[j - h];
            }
            a[j] = t;
        }
    }
}

int main ()
{
    int i;
    int array[100000];
    srand(time(NULL));

    for (i = 0; i < 100000; i++)
    {
        array[i] = rand() % 1000 + 1;
    }

    for (i = 0; i < 5; i++)
        printf("%d%\n", array[i]);

    shell_sort(array, 100000);

    for (i = 0; i < 5; i++)
        printf("%d%\n", array[i]);

    return 0;
}

You're generating 100,000 random numbers in the range 1 - 1000, then only looking at the first five. The first 100 of them are probably all 1. Try your code with a list of 10 numbers first. — Bill the Lizard, Jun 21 '15 at 13:52
@koper I have illustrated what Bill the Lizard said. Should be useful :) — adrian008, Jun 21 '15 at 14:49

adrian008 · Accepted Answer · 2015-06-21T14:53:37.297

The output of your program in my system is :

94 76 444 792 967 1 1 1 1 1

Another instance gives output:

665 777 481 269 215 1 1 1 1 1

So, you could guess that the random numbers generated must have a lot of ones.

However, if I change this piece of your code:

for (i = 10; i < 10005; i++)
    printf("%d\n", array[i]);

shell_sort(array, 100000);

for (i = 10; i < 1005; i++)
    printf("%d\n", array[i]);

The output is:

8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

The problem is not in the algo but the way you generate the random numbers.

I just change this line further,

 for (i = 0; i < 100000; i++)
    {
        array[i] = rand() + 1;  // Removed the modulus
    }

And the output is:

228 228 228 229 229 229 229 229 229 230 230 230 232 232 232 233 233 234 234 236 236 236 236 237 237 237 237 237 237 238 238 238 238 239 239 239 240 240 241 241 241 241 241 242 242 242 243 244 245 245 245 245 245 245 245 246 246 248 248 248 249 249 249 249 250 250 250 250 250 250 251 251 252 253 253 253 253 253 254 254 255 256 256 257 257 257 257 259 259 260 260 261 261 261 261 262 262 262 262 263 264 264 264 265 265 265 266 266 266 266 266 266 267 267 267 267 267 267 268 268 269 269 269 269 270 270 270 270 271 272 272 272 273 273 273 274 275 275 275 275 276 276 277 277 277 277 277 277 279 279 279 279 279 280 280 280 280 280 280 280 280 280 281 281 281 281 282 282 283 283 284 284 284 285 285 285 286 286 287 287 287 287 287 288 289 289 289 289 289 290 290 291 291 292 292 292 293 293 293 294 294 294 295 295 295 295 295 296 296 297 297 298 298 298 298 298 299 299 299 299 300 300 300 300 300 301 301 303 303 303 304 304 304 305 305 305 305 306 306 307 308 308 309 310 310 310 311 311 311 311 312 312 312 313 314 314 314 314 316 316 316 316 316 316 317 317 317 317 317 317 318 319 319 319 319 320 320 321 321 321 322 322 322 322 326 326 326 326 326 327 327 327 328 328 329 329

So, everything is fine. Just use the random numbers in a better way.

If `RAND_MAX == INT_MAX`, which is likely, the addition of `1` to a signed integer generates overflow if `RAND_MAX` is returned. That is _undefined behaviour_. See [here](http://stackoverflow.com/questions/30821406/why-does-rand-rand-produce-negative-numbers/30821874#30821874). — too honest for this site, Jun 21 '15 at 17:03

C shellsorting random int array

1 Answers1