CODEWITHSUNDEEP
carrayssorting2dbubble-sort
shaked
shaked

Reputation: 87

Sorting 2D array in C

I'm working on a project for a course in C.

I wrote this code based on bubble sort algorithm but it doesn't work if I try to sort many arrays:

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
            }
        }
    }
}

Description of copyTripleToArray():

The function copies the triple into the suitable index in sortedArray (buffer = 0), or in outputBuffer (buffer = 1) or in tempArray (buffer = 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 is the array to sort; it's a global array.

copyTripleToArray copies an array of integers to a specific index in sortedArray or to a temporary array.

What am I doing wrong?

Upvotes: 0

Views: 213

Answers (1)

Jonathan Leffler
Jonathan Leffler

Reputation: 753675

It was hard to disentangle this because it is sadly lacking the qualities of an MCVE (Minimal, Complete, Verifiable Example). Using a global variable for the array to be sorted is a bad idea; pass the array to the sort function.

You say:

… it doesn't work if I try to sort many arrays

You should explain in what way it doesn't work. One obvious problem is that you have to copy the data into the global array for each set of data to be sorted. It's one of the many reasons why you should pass the array to the sorting function and not rely on global variables. Treat global variables with caution. Use them only when the alternative (passing as arguments) is too excruciating (and 'excruciating' is the minimal level pain that should cause you to use global variables; don't be put off by mere 'discomfort' or even just 'agony').

Trivia: "Elements" has an m in it — your huge long NUM_OF_ELENENTS_IN_ARRAY doesn't have an M in the right place. However, the variable and constant names are too long for my comfort. Yes; it is good to choose meaningful names. No; it is not necessary to write a grammatically correct essay into the name. I used NUM_VALUES; NUM_COLUMNS would work too. They're long enough and meaningful.

More seriously, you have a global variable OutputBuffer for which there is no explanation — it is referenced in copyTripleToArray(), which is an odd name for a function that copies 6 elements. However, closer scrutiny shows that it is only used when buffer == 1, but you never call the function with buffer == 1, so that block of code can be removed (commented out).

Your copyTripleToArray() function is modestly bizarre. You should simply provide a pointer to the row to be copied out and the row to be copied to and let it get on with copying. It is peculiar that you need so many parameters. Two or three should be sufficient (depending on whether you pass NUM_VALUES to the function or not).

Mildly revised version of code from question

However, when all is said and done, it appears that the code works. At least, the revisions I made in the code below are supposed to be trivial. I created and populated an array, and ran the code on it, and it seems to produce the correct result.

#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;
}

Sample run:

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

So, it is not clear to me what your problem is.

Revised code

Here's a simplified version of the code, using a simpler copy_row() function, which could if desired be upgraded to use memmove() or memcpy() instead of a having a loop in the body.

#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;
}

With the same input data (and printing code, etc), it produces the same answer. I've not formally verified conservation properties — that all the rows that are present in the unsorted data are present in the sorted data.

It is not hard to revise this code further so that the array to be sorted is passed to the sorting function as a parameter instead of as a file scope variable. That is a much more powerful, and more easily reused, version of the code.

You can find the code in my SOQ (Stack Overflow Questions) repository on GitHub as files sort31.c (code from question), sort67.c (passing the array as argument to sort) and sort89.c (the code above) in the src/so-5380-3837 sub-directory.

Upvotes: 1

Related Questions