CODEWITHSUNDEEP
csortingmemcmp
machine_1
machine_1

Reputation: 4454

Why are negative numbers greater than positive numbers?

I made my bubble sort program generic. I went on testing it and it was working well until I placed a negative number in the array, and I was surprised that it was pushed to the end, making it bigger than positive numbers.

Obviously memcmp is the reason, so why does memcmp() regard negative numbers greater than positive numbers?

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

void bubblesortA(void *_Buf, size_t bufSize, size_t bytes);

int main(void)
{
    size_t n, bufsize = 5;
    int buf[5] = { 5, 1, 2, -1, 10 };
    bubblesortA(buf, 5, sizeof(int));

    for (n = 0; n < bufsize; n++)
    {
        printf("%d ", buf[n]);
    }
    putchar('\n');

    char str[] = "bzqacd";
    size_t len = strlen(str);
    bubblesortA(str, len, sizeof(char));

    for (n = 0; n < len; n++)
    {
        printf("%c ", str[n]);
    }
    putchar('\n');
    return 0;
}

void bubblesortA(void *buf, size_t bufSize, size_t bytes)
{
    size_t x, y;
    char *ptr = (char*)buf;
    void *tmp = malloc(bytes);
    for (x = 0; x < bufSize; x++)
    {
        ptr = (char *)buf;
        for (y = 0; y < (bufSize - x - 1); y++)
        {
            if (memcmp(ptr, ptr + bytes, bytes) > 0)
            {
                memcpy(tmp, ptr, bytes);
                memcpy(ptr, ptr + bytes, bytes);
                memcpy(ptr + bytes, tmp, bytes);
            }
            ptr += bytes;
        }
    }
    free(tmp);
}

Edit:
So, How do I modify the program to make it compare correctly?

Upvotes: 3

Views: 3394

Answers (4)

chux
chux

Reputation: 154070

Answering OP's appended edit

How can i modify the program to make it compare correctly?

To compare two types as an anonymous bit pattern, memcmp() works fine. To compare two values of some type, code needs a compare function for that type. Following qsort() style:

void bubblesortA2(void *_Buf,size_t bufSize,size_t bytes, 
    int (*compar)(const void *, const void *)))
{
   ....
        // if(memcmp(ptr,ptr+bytes,bytes) > 0)
        if((*compar)(ptr,ptr+bytes) > 0)
   ....

To compare int, pass in a compare int function. Notice that a, b are the addresses to the objects.

int compar_int(const void *a, const void *b) {
  const int *ai = (const int *)a;
  const int *bi = (const int *)b;
  return (*ai > *bi) - (*ai < *bi);
}

To compare char, pass in a compare char function

int compar_int(const void *a, const void *b) {
  const char *ac = (const char *)a;
  const char *bc = (const char *)b;
  return (*ac > *bc) - (*ac < *bc);
}

Upvotes: 5

Magisch
Magisch

Reputation: 7352

In the notation that numbers and negative numbers are counted, the first bit is used as signbit, a bit that indicates wether a number is negative or positive.

It becomes clear if we look at the binary representations of 2 numbers. Its worth noting that memcmp just compares 2 numbers as if they were both unsigned numbers of the lenght specified.

-27 in binary notation (8 bit notation, twos complement): 1110 0101

+56 in binary notation : 0011 1000

If you compare the two as if they were positive, you'll note that the -27 representation is actually bigger.

Upvotes: 0

Vlad from Moscow
Vlad from Moscow

Reputation: 311048

Negative numbers have sign bit (the most significant bit) set to 1. Function memcmp compares bytes as unsigned values. So it considers the sign bit as a value bit. As result sometimes negative numbers are greater than positive numbers.

Upvotes: 0

alain
alain

Reputation: 12047

memcmp compares bytes, it does not know if the bytes represent ints, doubles, strings, ...

So it can not do any better that treat the bytes as unsigned numbers. Because a negative integer is normally represented using two's-complement, the highest bit of a negative integer is set, making it bigger than any positive signed integer.

Upvotes: 7

Related Questions