Сортировка 2D массива в C - PullRequest
Новая
       12

Сортировка 2D массива в C

0 голосов
/ 16 декабря 2018

Я работаю над проектом для курса на C.

  • Мне нужно отсортировать массив массивов из шести целых чисел: {a, b, c, n, m, v}.
  • Мне нужно отсортировать его в порядке возрастания значения n, и если оно имеет два или более массивов с одинаковым n, мне нужно отсортировать его в порядке возрастания m.

Я написал этот код на основе алгоритма пузырьковой сортировки, но он не работает, если я пытаюсь отсортировать много массивов: 

void bubbleSort(int arraySize)
{
    int tempEntry[6];
    for (int i = 0; i < arraySize - 1; i++) //Loop for ascending ordering
    {
        for (int j = 0; j < arraySize - 1 - i; j++) //Loop for comparing other values
        {
            if (sortedArray[j][3] > sortedArray[j + 1][3]) //Comparing other array elements . n1>n2
            {
                copyTripleToArray(sortedArray[j], 0, 2, tempEntry); //Using temporary variable for storing last value
                copyTripleToArray(sortedArray[j + 1], j, 0, NULL); //replacing value
                copyTripleToArray(tempEntry, j + 1, 0, NULL);  //storing last value
            }
            if (sortedArray[j][3] == sortedArray[j + 1][3] && sortedArray[j][4] > sortedArray[j + 1][4]) //Comparing other array elements. n1=n2, m1>m2
            {
                copyTripleToArray(sortedArray[j], 0, 2, tempEntry); //Using temporary variable for storing last value
                copyTripleToArray(sortedArray[j + 1], j, 0, NULL); //replacing value
                copyTripleToArray(tempEntry, j + 1, 0, NULL);  //storing last value
            }
        }
    }
}

Описание copyTripleToArray():

Функция копирует тройку в подходящий индекс в sortedArray (буфер = 0) или в outputBuffer (буфер = 1) или в tempArray (буфер = 2). 

void copyTripleToArray(int PrimitivePythagoreanTriple[], int index, int buffer, int tempArray[])
{
    if (buffer == 1) //the array is outputBuffer
    {
        for (int i = 0; i < NUM_OF_ELENENTS_IN_ARRAY; i++) //first case: loop to copy all the entries
            outputBuffer[index][i] = PrimitivePythagoreanTriple[i]; // copy the array to buffer.
        return;
    }
    else if (buffer == 0) //the array is outputBuffer
    {
        for (int i = 0; i < NUM_OF_ELENENTS_IN_ARRAY; i++) //secound case: loop to copy all the entries into sortedArray
            sortedArray[index][i] = PrimitivePythagoreanTriple[i]; // copy the array to sortedArray.
        return;
    }
    for (int i = 0; i < NUM_OF_ELENENTS_IN_ARRAY; i++) //third case: loop to copy all the entries into tempArray
        tempArray[i] = PrimitivePythagoreanTriple[i]; // copy the array to tempArray.
}

sortedArray - массив для сортировки;это глобальный массив.

copyTripleToArray копирует массив целых чисел в определенный индекс в sortedArray или во временный массив.

Что я делаю не так?

1 Ответ

0 голосов
/ 16 декабря 2018

Было трудно распутать это, потому что ему, к сожалению, не хватает качеств MCVE ( Минимальный, полный, проверяемый пример ).Использование глобальной переменной для сортировки массива - плохая идея;передать массив в функцию сортировки.

Вы говорите:

... это не сработает, если я попытаюсь отсортировать много массивов

Вы должныобъясните, как это не работает.Одна очевидная проблема заключается в том, что вам нужно скопировать данные в глобальный массив для каждого набора данных, которые будут отсортированы.Это одна из многих причин, почему вы должны передавать массив в функцию сортировки, а не полагаться на глобальные переменные.Обращайтесь с глобальными переменными с осторожностью.Используйте их только тогда, когда альтернатива (передавая в качестве аргументов) слишком мучительна (а «мучительная» - это боль минимального уровня, которая должна заставить вас использовать глобальные переменные, не отталкивайтесь простым «дискомфортом» или даже просто «агонией»).).

Общая информация: у "Элементов" есть буква m - у вашего огромного длинного NUM_OF_ELENENTS_IN_ARRAY нет буквы M в нужном месте.Однако имена переменных и констант слишком длинные для моего удобства.Да;хорошо выбирать значимые имена.Нет;нет необходимости писать грамматически правильное эссе в название.Я использовал NUM_VALUES;NUM_COLUMNS тоже подойдет.Они достаточно длинные и значимые.

Если серьезно, у вас есть глобальная переменная OutputBuffer, для которой нет объяснения - на нее ссылается copyTripleToArray(), что является нечетным именем для функции, которая копирует6 элементов.Однако более тщательное изучение показывает, что оно используется только при buffer == 1, но вы никогда не вызываете функцию с buffer == 1, так что блок кода можно удалить (закомментировать).

Ваша copyTripleToArray() функцияскромно странно.Вы должны просто предоставить указатель на строку, которую нужно скопировать, и строку, на которую нужно скопировать, и позволить этому начать копирование.Странно, что вам нужно так много параметров.Два или три должно быть достаточно (в зависимости от того, передаете ли вы NUM_VALUES в функцию или нет).

Слегка пересмотренная версия кода из вопроса

Однако, когда все сказано и сделано,похоже, что код работает.По крайней мере, изменения, которые я сделал в приведенном ниже коде, должны быть тривиальными.Я создал и заполнил массив, и запустил код на нем, и он, кажется, дает правильный результат. 

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

enum { NUM_VALUES = 6 };
enum { NUM_OF_ELEMENTS_IN_ARRAY = NUM_VALUES };

static int sortedArray[][NUM_VALUES];   // Forward declaration

static void copyTripleToArray(int PrimitivePythagoreanTriple[], int index, int buffer, int tempArray[])
{
    //if (buffer == 1)
    //{
        //for (int i = 0; i < NUM_OF_ELEMENTS_IN_ARRAY; i++)
            //outputBuffer[index][i] = PrimitivePythagoreanTriple[i];
    //}
    //else if (buffer == 0)
    if (buffer == 0)
    {
        for (int i = 0; i < NUM_OF_ELEMENTS_IN_ARRAY; i++)
            sortedArray[index][i] = PrimitivePythagoreanTriple[i];
    }
    else
    {
        for (int i = 0; i < NUM_OF_ELEMENTS_IN_ARRAY; i++)
            tempArray[i] = PrimitivePythagoreanTriple[i];
    }
}

static void bubbleSort(int arraySize)
{
    int tempEntry[NUM_VALUES];
    for (int i = 0; i < arraySize - 1; i++)
    {
        for (int j = 0; j < arraySize - 1 - i; j++)
        {
            if (sortedArray[j][3] > sortedArray[j + 1][3])
            {
                copyTripleToArray(sortedArray[j], 0, 2, tempEntry);
                copyTripleToArray(sortedArray[j + 1], j, 0, NULL);
                copyTripleToArray(tempEntry, j + 1, 0, NULL);
            }
            if (sortedArray[j][3] == sortedArray[j + 1][3] &&
                sortedArray[j][4] >  sortedArray[j + 1][4])
            {
                copyTripleToArray(sortedArray[j], 0, 2, tempEntry);
                copyTripleToArray(sortedArray[j + 1], j, 0, NULL);
                copyTripleToArray(tempEntry, j + 1, 0, NULL);
            }
        }
    }
}

static void print_array(const char *tag, size_t size, int data[size][NUM_VALUES])
{
    printf("%s (%zux%d):\n", tag, size, NUM_VALUES);
    for (size_t i = 0; i < size; i++)
    {
        printf("%3zu:", i);
        for (int j = 0; j < NUM_VALUES; j++)
            printf(" %3d", data[i][j]);
        putchar('\n');
    }
}

static int sortedArray[][NUM_VALUES] =
{
    // random -n 30 -T '%d %d %d %d %d %d' 10 29 |
    // commalist -n 6 -B 4 -b '{ ' -w -W 3 -T ' },'
    {  25,  18,  29,  25,  12,  18, },
    {  29,  29,  24,  23,  26,  28, },
    {  16,  22,  10,  15,  23,  29, },
    {  27,  22,  16,  27,  19,  24, },
    {  17,  18,  10,  20,  15,  24, },
    {  21,  11,  19,  15,  13,  15, },
    {  16,  11,  19,  13,  10,  25, },
    {  17,  17,  15,  27,  26,  24, },
    {  12,  23,  24,  28,  24,  15, },
    {  11,  21,  25,  15,  18,  25, },
    {  12,  14,  25,  11,  13,  29, },
    {  16,  12,  11,  21,  19,  28, },
    {  18,  16,  20,  17,  15,  11, },
    {  13,  18,  11,  23,  23,  18, },
    {  29,  16,  29,  10,  22,  28, },
    {  13,  15,  24,  24,  28,  26, },
    {  28,  26,  13,  27,  18,  27, },
    {  10,  29,  18,  15,  24,  29, },
    {  24,  24,  27,  24,  21,  12, },
    {  10,  28,  12,  11,  27,  25, },
    {  12,  21,  28,  27,  11,  14, },
    {  19,  17,  11,  18,  25,  23, },
    {  19,  21,  10,  21,  20,  22, },
    {  18,  29,  12,  15,  28,  22, },
    {  25,  16,  15,  23,  27,  21, },
    {  28,  16,  11,  10,  24,  23, },
    {  29,  19,  22,  20,  28,  27, },
    {  16,  21,  17,  16,  25,  15, },
    {  11,  23,  17,  19,  27,  13, },
    {  12,  15,  18,  16,  26,  14, },
};

enum { NUM_ROWS = sizeof(sortedArray) / sizeof(sortedArray[0]) };

int main(void)
{
    print_array("Before", NUM_ROWS, sortedArray);
    bubbleSort(NUM_ROWS);
    print_array("After", NUM_ROWS, sortedArray);
    return 0;
}

Пример запуска: 

Before (30x6):
  0:  25  18  29  25  12  18
  1:  29  29  24  23  26  28
  2:  16  22  10  15  23  29
  3:  27  22  16  27  19  24
  4:  17  18  10  20  15  24
  5:  21  11  19  15  13  15
  6:  16  11  19  13  10  25
  7:  17  17  15  27  26  24
  8:  12  23  24  28  24  15
  9:  11  21  25  15  18  25
 10:  12  14  25  11  13  29
 11:  16  12  11  21  19  28
 12:  18  16  20  17  15  11
 13:  13  18  11  23  23  18
 14:  29  16  29  10  22  28
 15:  13  15  24  24  28  26
 16:  28  26  13  27  18  27
 17:  10  29  18  15  24  29
 18:  24  24  27  24  21  12
 19:  10  28  12  11  27  25
 20:  12  21  28  27  11  14
 21:  19  17  11  18  25  23
 22:  19  21  10  21  20  22
 23:  18  29  12  15  28  22
 24:  25  16  15  23  27  21
 25:  28  16  11  10  24  23
 26:  29  19  22  20  28  27
 27:  16  21  17  16  25  15
 28:  11  23  17  19  27  13
 29:  12  15  18  16  26  14
After (30x6):
  0:  29  16  29  10  22  28
  1:  28  16  11  10  24  23
  2:  12  14  25  11  13  29
  3:  10  28  12  11  27  25
  4:  16  11  19  13  10  25
  5:  21  11  19  15  13  15
  6:  11  21  25  15  18  25
  7:  16  22  10  15  23  29
  8:  10  29  18  15  24  29
  9:  18  29  12  15  28  22
 10:  16  21  17  16  25  15
 11:  12  15  18  16  26  14
 12:  18  16  20  17  15  11
 13:  19  17  11  18  25  23
 14:  11  23  17  19  27  13
 15:  17  18  10  20  15  24
 16:  29  19  22  20  28  27
 17:  16  12  11  21  19  28
 18:  19  21  10  21  20  22
 19:  13  18  11  23  23  18
 20:  29  29  24  23  26  28
 21:  25  16  15  23  27  21
 22:  24  24  27  24  21  12
 23:  13  15  24  24  28  26
 24:  25  18  29  25  12  18
 25:  12  21  28  27  11  14
 26:  28  26  13  27  18  27
 27:  27  22  16  27  19  24
 28:  17  17  15  27  26  24
 29:  12  23  24  28  24  15

Итак, это не яснодля меня в чем ваша проблема.

Пересмотренный код

Вот упрощенная версия кода, использующая более простую функцию copy_row(), которую можно при желании обновить до memmove() или memcpy() вместо наличия в теле цикла. 

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

enum { NUM_VALUES = 6 };

static int sortedArray[][NUM_VALUES];    // Forward declaration

static void copy_row(int source[NUM_VALUES], int target[NUM_VALUES])
{
    for (int i = 0; i < NUM_VALUES; i++)
        target[i] = source[i];
}

static void bubbleSort(int arraySize)
{
    int tempEntry[6];
    for (int i = 0; i < arraySize - 1; i++)
    {
        for (int j = 0; j < arraySize - 1 - i; j++)
        {
            if ((sortedArray[j][3] > sortedArray[j + 1][3]) ||
                (sortedArray[j][3] == sortedArray[j + 1][3] &&
                 sortedArray[j][4] >  sortedArray[j + 1][4]))
            {
                copy_row(sortedArray[j], tempEntry);
                copy_row(sortedArray[j+1], sortedArray[j]);
                copy_row(tempEntry, sortedArray[j+1]);
            }
        }
    }
}

static void print_array(const char *tag, size_t size, int data[size][NUM_VALUES])
{
    printf("%s (%zux%d):\n", tag, size, NUM_VALUES);
    for (size_t i = 0; i < size; i++)
    {
        printf("%3zu:", i);
        for (int j = 0; j < NUM_VALUES; j++)
            printf(" %3d", data[i][j]);
        putchar('\n');
    }
}

static int sortedArray[][NUM_VALUES] =
{
    // random -n 30 -T '%d %d %d %d %d %d' 10 29 |
    // commalist -n 6 -B 4 -b '{ ' -w -W 3 -T ' },'
    {  25,  18,  29,  25,  12,  18, },
    {  29,  29,  24,  23,  26,  28, },
    {  16,  22,  10,  15,  23,  29, },
    {  27,  22,  16,  27,  19,  24, },
    {  17,  18,  10,  20,  15,  24, },
    {  21,  11,  19,  15,  13,  15, },
    {  16,  11,  19,  13,  10,  25, },
    {  17,  17,  15,  27,  26,  24, },
    {  12,  23,  24,  28,  24,  15, },
    {  11,  21,  25,  15,  18,  25, },
    {  12,  14,  25,  11,  13,  29, },
    {  16,  12,  11,  21,  19,  28, },
    {  18,  16,  20,  17,  15,  11, },
    {  13,  18,  11,  23,  23,  18, },
    {  29,  16,  29,  10,  22,  28, },
    {  13,  15,  24,  24,  28,  26, },
    {  28,  26,  13,  27,  18,  27, },
    {  10,  29,  18,  15,  24,  29, },
    {  24,  24,  27,  24,  21,  12, },
    {  10,  28,  12,  11,  27,  25, },
    {  12,  21,  28,  27,  11,  14, },
    {  19,  17,  11,  18,  25,  23, },
    {  19,  21,  10,  21,  20,  22, },
    {  18,  29,  12,  15,  28,  22, },
    {  25,  16,  15,  23,  27,  21, },
    {  28,  16,  11,  10,  24,  23, },
    {  29,  19,  22,  20,  28,  27, },
    {  16,  21,  17,  16,  25,  15, },
    {  11,  23,  17,  19,  27,  13, },
    {  12,  15,  18,  16,  26,  14, },
};

enum { NUM_ROWS = sizeof(sortedArray) / sizeof(sortedArray[0]) };

int main(void)
{
    print_array("Before", NUM_ROWS, sortedArray);
    bubbleSort(NUM_ROWS);
    print_array("After", NUM_ROWS, sortedArray);
    return 0;
}

При одинаковых входных данных (и коде печати и т. Д.) Он дает тот же ответ.Я не проверял формально свойства сохранения - все строки, которые присутствуют в несортированных данных, присутствуют в отсортированных данных.

Нетрудно пересмотреть этот код, чтобы отсортировать массивпередается в функцию сортировки как параметр, а не как переменная области видимости файла.Это гораздо более мощная и более легкая в использовании версия кода.

Вы можете найти код в моем репозитории SOQ (Stack Overflow Questions) на GitHub в виде файлов sort31.c(код из вопроса), sort67.c (передача массива в качестве аргумента для сортировки) и sort89.c (код выше) в подкаталоге src / so-5380-3837 .

...