Сортировка слиянием: Как отсортировать, если одно из чисел находится в 2 байта - PullRequest
Новая
       0

Сортировка слиянием: Как отсортировать, если одно из чисел находится в 2 байта

0 голосов
/ 18 октября 2010

Я пытаюсь выполнить сортировку слиянием, используя void*. Если я сохраняю числа, я хочу отсортировать их до 1 байта, это прекрасно работает. Однако, если число находится в больше чем 1 байте, это не работает хорошо. Я считаю, что он принимает это как 2 числа. Я проверил это с номером 500 и в конце у меня 256 и 244 не отсортированы .... 

#include "msort.h"
#include <iostream>

using namespace std;

void Mergesort( void* base, size_t nelem, size_t width,
                    int (*fcmp)( const void*, const void* ) )
{
    if (nelem <=1)
        return;

    int lhsnelem = nelem/2; 
    int rhsnelem = nelem - lhsnelem;
    char* midpoint = (char*)(base) + ((nelem/2)*width);

    cout << "width is: " << width << endl;

    Mergesort(base, lhsnelem, width, fcmp);
    Mergesort(midpoint, rhsnelem, width, fcmp);

    //ItemType* temp= new ItemType[nelem];
    int temp[20];
    char* lhs = (char*)(base);
    char* rhs = midpoint;
    char* end = rhs + (rhsnelem*width);        
    int count = 0;

    while ((lhs != midpoint) && (rhs != end))
    {
         int num = fcmp( lhs, rhs ); 
         if (num <= 0)
         {
             temp[count] = *lhs;
             lhs = lhs + width;
         }
         else
         {
             temp[count] = *rhs; 
             rhs = rhs + width;
         }
         count++; 
    }

    if (lhs == midpoint)
    {
        while (rhs != end)
        {
            temp[count] = *rhs;
            rhs = rhs + width;
            count++;
        }
    }
    else
    {

        while (lhs != midpoint) 
        {
            temp[count] = *lhs; 
            lhs = lhs + width;
            count++;
        }

    }

    for (int i=0; i<nelem; i++)
    {
        lhs = (char*)(base)+ (width*i);
        *lhs = temp[i];
        lhs = lhs + width;
    }
}

main.cpp 

/////// main.cpp ///////////////////////
// here is my comparison function in main.cpp

int compare(const void *one, const void *two)
{
    if (*(int*)one > *(int*)two) return 1;
    if (*(int*)one < *(int*)two) return -1;
    return 0;
}

Вывод для 1-байтовых чисел в порядке: 

In:    5 8 7 4 1 6 11 41 160 47 38 120 40 58 12 43 66 98 17 140
Out:   1 4 5 6 7 8 11 12 17 38 40 41 43 47 58 66 98 120 140 160

Вывод, если есть 2-байтовое число, не в порядке, сортировка не работает хорошо: 

In:    500 50 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Out:   256 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 50 244

1 Ответ

1 голос
/ 18 октября 2010

Ваша непосредственная проблема в том, что вы используете char *lhs для копирования целых чисел.Вам нужно преобразовать указатель обратно в int * перед копированием. 

#include <iostream>

using namespace std;

static void Mergesort(void *base, size_t nelem, size_t width,
                      int (*fcmp)(const void *, const void *))
{
    if (nelem <= 1)
        return;

    int lhsnelem = nelem/2; 
    int rhsnelem = nelem - lhsnelem;
    char* midpoint = (char*)(base) + ((nelem/2)*width);

    Mergesort(base, lhsnelem, width, fcmp);
    Mergesort(midpoint, rhsnelem, width, fcmp);

    int temp[20];
    char* lhs = (char*)(base);
    char* rhs = midpoint;
    char* end = rhs + (rhsnelem*width);        
    int count = 0;

    while ((lhs != midpoint) && (rhs != end))
    {
        int num = fcmp(lhs, rhs); 
        if (num <= 0)
        {
            temp[count] = *(int *)lhs;          // Here!
            lhs += width;
        }
        else
        {
            temp[count] = *(int *)rhs;          // Here!
            rhs += width;
        }
        count++; 
    }


    while (rhs != end)
    {
        temp[count] = *(int *)rhs;          // Here!
        rhs = rhs + width;
        count++;
    }
    while (lhs != midpoint) 
    {
        temp[count] = *(int *)lhs;          // Here!
        lhs = lhs + width;
        count++;
    }

    for (int i = 0; i < nelem; i++)
    {
        lhs = (char *)(base)+ (width*i);
        *(int *)lhs = temp[i];                  // Here!
        lhs = lhs + width;
    }
}

Тестовый код 

static int compare(const void *one, const void *two)
{
    if (*(int*)one > *(int*)two) return 1;
    if (*(int*)one < *(int*)two) return -1;
    return 0;
}

#define DIM(x) (sizeof(x)/sizeof(*(x)))

int array1[] = { 5, 8, 7, 4, 1, 6, 11, 41, 160, 47, 38, 120,
                 40, 58, 12, 43, 66, 98, 17, 140 };
int array2[] = { 500, 50, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                 0, 0, 0, 0, 0, 0, 0, 0 };

static void PrintArray(int *array, size_t n_items)
{
    const char *pad = "";
    for (size_t i = 0; i < n_items; i++)
    {
        cout << pad << array[i];
        pad = ", ";
    }
    cout << endl;
}

int main()
{
    PrintArray(array1, DIM(array1));
    Mergesort(array1, DIM(array1), sizeof(array1[0]), compare);
    PrintArray(array1, DIM(array1));

    PrintArray(array2, DIM(array2));
    Mergesort(array2, DIM(array2), sizeof(array2[0]), compare);
    PrintArray(array2, DIM(array2));

    return 0;
}

Вам не повезло, что вы используете младший порядок (Intel)машина;Если бы вы использовали машину с прямым порядком байтов (SPARC, PPC), вы бы получили массив нулей для теста с небольшим числом.

Существует и более серьезная, более глубокая проблема.На самом деле код может использоваться только для сортировки массивов до 20 целых чисел из-за int temp[20]; (который ограничивает размер до 20 и который ограничивает тип до int) и из-за «фиксированных» назначений.

Назначения должны быть заменены перемещениями памяти (возможно, вызовами memmove()), что, в свою очередь, означает, что код будет работать только для типов POD (обычные данные).Массив temp должен быть выделен как массив байтов соответствующего размера (nelem * width).И распределение памяти неприятно;это замедлит код.«Возможно, хорошая новость» заключается в том, что последний цикл, который копирует временный массив поверх исходного массива, может быть заменен на memmove().

Не ясно, что это хороший код C ++ - я думаю, что шаблонныйреализация была бы более разумной.Что касается кода C, с решением проблем с перемещением памяти все в порядке.

Общий код 

static void Mergesort(void *base, size_t nelem, size_t width,
                      int (*fcmp)(const void *, const void *))
{
    if (nelem <= 1)
        return;

    int lhsnelem = nelem/2; 
    int rhsnelem = nelem - lhsnelem;
    char* midpoint = (char*)(base) + ((nelem/2)*width);

    Mergesort(base, lhsnelem, width, fcmp);
    Mergesort(midpoint, rhsnelem, width, fcmp);

    char *temp = new char[nelem * width];
    char* lhs = (char*)(base);
    char* rhs = midpoint;
    char* end = rhs + (rhsnelem*width);        
    int count = 0;

    while ((lhs != midpoint) && (rhs != end))
    {
        int num = fcmp(lhs, rhs); 
        if (num <= 0)
        {
            memmove(&temp[count], lhs, width);
            lhs += width;
        }
        else
        {
            memmove(&temp[count], rhs, width);
            rhs += width;
        }
        count += width;
    }

    while (rhs != end)
    {
        memmove(&temp[count], rhs, width);
        rhs += width;
        count += width;
    }
    while (lhs != midpoint) 
    {
        memmove(&temp[count], lhs, width);
        lhs += width;
        count += width;
    }

    memmove(base, temp, nelem * width);
    delete[] temp;
}
...