Reputation: 1

Bubblesort a 2-D Array - C

I am trying to use Bubblesort for a 2-D array, using a custom sized 2D Array with the max limit of [100][2]. I am a beginner at this, so i am not great at formatting code properly so shedding light would be great.

my input

How many items of data do you wish to enter? 4
Please enter in the X coordinate: 4
Please enter in the Y coordinate: 4
Please enter in the X coordinate: 3
Please enter in the Y coordinate: 3
Please enter in the X coordinate: 2
Please enter in the Y coordinate: 2
Please enter in the X coordinate: 1
Please enter in the Y coordinate: 1

So that prints out how many numbers you wish to enter from a custom array input.

output(Meant to compare each array and switch to ascending order).

Printing in Ascending Order:
[4][3]
[3][3]
[3][3]

It prints 3 arrays not 4, and doesn't print out any of the numbers i entered. so But could anybody shed some light on this? It is specifically the Bubblesort function.

int main()
{
    int arrayHeight, array[100][2];
    printf ("***** Bubble Sort ***** \n"); 
    InputArray(array, arrayHeight);
}

int InputArray(int array[100][2], int arrayHeight, int swap) 
{
    int i, xCoord, yCoord;
    printf("\n How many items of data do you wish to enter? ");
    scanf("%d",&arrayHeight);
    for(i=0; i<arrayHeight; i++)
    {
        printf("Please enter in the X coordinate: ");
        scanf("%d", &xCoord);
        printf("Please enter in the Y coordinate: ");
        scanf("%d", &yCoord);
        array[i][0] = xCoord;/* Name of XCoordinate and position within Array*/
        array[i][1] = yCoord;/*Name of YCoordinate and position within Array*/
    }
    DisplayArray(array, arrayHeight);
}

int DisplayArray(int array[100][2], int arrayHeight, int swap) 
{
    int i, j;
    printf("\n The 2-D Array contains : \n");
    for(i=0; i<arrayHeight; i++)
    {
        printf("[%d][%d]\n\r", array[i][1], array[i][0]);
    }
    BubbleSort(array, arrayHeight);
} 

int BubbleSort(int array[100][2], int arrayHeight)
{   
    int swap, i, j, k;
    printf("\n Printing in Asending Order: ");
    for (i = 0; i <arrayHeight-1; i++) 
    {
        if (array[i][0] > array[i][1 + 1]) 
        {
            array[1][i] = array[1][0+1];
            swap = array[1][i];
            array[i][1 + 1];
            printf("\n [%d][%d] ", array[i][0], array[1][i]);       
        }
    }
}

Upvotes: 0

Answers (2)

cooljake

Reputation: 696

There's a fair amount of things going on here.

Your Question

Your program is printing out strange parts of your array because of the way you're calling printf from within BubbleSort. While BubbleSort is still running, your array isn't fully sorted. However, the function calls printf after each attempt at swapping array elements. If you'd like to print your whole array after sorting, it would be better to allow the sorting function to run to completion, then print out the array in full afterwards.

Other Stuff

There are a lot of points tangential to your question that I'd like to raise to help you out from a style and correctness perspective. Also, some of these are rather interesting.

`#include` Statements

When compiling this, you should be getting several warnings. If you're using gcc, one of those warnings will be something like:

main.c: warning: incompatible implicit declaration of built-in function ‘printf’
    printf ("***** Bubble Sort ***** \n");

This states that the function printf has been implicitly declared when it was called. That is, the compiler inferred that a function printf exists because you called a function named printf. The problem is that it knows nothing about this function other than that it probably exists. This means the complier doesn't know what the function is supposed to return or what arguments it is supposed to accept, so it cannot help you if you use it inappropriately. To avoid this problem, you should include the standard C Input/Output headers in your program like so:

#include <stdio.h>

The stdio.h header file includes many functions besides just printf. Check out man 3 stdio for more information on it.

Define or Declare Functions Before Calling Them

One of the less-modern aspects of C is that it runs through your program from top to bottom. Many modern languages allow you to put your function declarations anywhere in your code and then it works things out on its own. Javascript's variable and function hoisting is an example of this.

Because C does not do this, you should define or declare your functions before you call them. If you call them without a declaration or definiton, the compiler will fall back to the default function signature extern int <function_name>(); That is, if you do not supply a declaration or definition for your function, C will assume that function is defined elsewhere, returns an int, and takes an unspecified number of arguments.

In this program, the function DisplayArray is defined with three arguments:

int DisplayArray(int array[100][2], int arrayHeight, int swap);

However, it is called with only two arguments:

DisplayArray(array, arrayHeight);

This can only happen because when the function is first called, it hasn't yet been defined, so the compiler, without knowing any better, assumes the call is made correctly.

When this is corrected (the definition is put above the first call), the compiler will throw an error stating that the function DisplayArray takes three arguments, but it was called with only two.

Calling Functions / Program Structure

The most oft-cited benefit of creating functions in your code is modularity. This is the idea that you can freely re-use code at different points in your program while knowing what that code is going to do. This program sacrifices this benefit by creating a sort of function-chain, where each function calls the other. InputArray calls DisplayArray, and DisplayArray calls BubbleSort.

This means any time you'd like to print an array, you must be okay with it being bubble-sorted as well. This is considered bad practice because it reduces the amount of times calling the function is useful. A more useful function would be one that displays the array but does not call BubbleSort or modify the array in any way.

Bubble Sorting

Your question doesn't specify exactly how you'd like to bubble sort, but the function here doesn't implement the BubbleSort algorithm. Generally, it's best to make sure you understand the algorithm before applying it to strange cases like 2-D arrays. I've included a working example below, which I hope helps get you on the right track.

Briefly, note that there two loops in a bubble sort: * an inner loop that runs through the array and swaps neighboring elements * an outer loop that runs the inner loop until the entire array is sorted

Minor Things

C programs generally prefer snake_case to CamelCase, but more generally, you should do what works best for you. If you're on a team, use a style consistent with that team.
All of the functions in this program return int, yet none of them actually use a return statement or return a useful value. If you have a function does not return a useful value, return void instead (e.g. - void DisplayArray(int array[100][2], int arrayHeight)).
Your displayArray function swaps the position of x and y. printf will display parameters in the order you specify unless directed otherwise. Check out man 3 printf for more on that function.

Working Example

#include <stdio.h>

void DisplayArray(int array[100][2], int arrayHeight)
{
  int i, j;
  printf("\n The 2-D Array contains : \n");
  for(i=0; i<arrayHeight; i++)
  {
    printf("[%d][%d]\n\r", array[i][0], array[i][1]);
  }
}

void BubbleSort(int array[100][2], int arrayHeight)
{
  int i;
  int swap[2];
  int swapHappened = 1;

  // the outer loop runs until no swaps need to be made
  // no swapping implies the array is fully sorted
  while (swapHappened) {
    swapHappened = 0;

    // the inner loop swaps neighboring elements
    // this is what 'bubbles' elements to the ends of the array
    for (i = 0; i < arrayHeight-1; i++)
    {
      if ((array[i][0] > array[i+1][0]) ||
          (array[i][0] == array[i+1][0]) && (array[i][1] > array[i+1][1]))
      {
        // if a swap happens, the array isn't sorted yet, set this variable
        // so the `while` loop continues sorting
        swapHappened = 1;

        // save the higher-value row to a swap variable
        swap[0] = array[i][0];
        swap[1] = array[i][1];

        // push the lower-valued row down one row
        array[i][0] = array[i+1][0];
        array[i][1] = array[i+1][1];

        // put the saved, higher-value row where the lower-valued one was
        array[i+1][0] = swap[0];
        array[i+1][1] = swap[1];
      }
    }
    DisplayArray(array, arrayHeight);
  }
}

int main()
{
  int arrayHeight, array[100][2];
  printf ("***** Bubble Sort ***** \n");

  int i, xCoord, yCoord;

  printf("\n How many items of data do you wish to enter? ");
  scanf("%d",&arrayHeight);
  for(i=0; i<arrayHeight; i++)
  {
    printf("Please enter in the X coordinate: ");
    scanf("%d", &xCoord);
    printf("Please enter in the Y coordinate: ");
    scanf("%d", &yCoord);
    array[i][0] = xCoord;/* Name of XCoordinate and position within Array*/
    array[i][1] = yCoord;/*Name of YCoordinate and position within Array*/
  }

  DisplayArray(array, arrayHeight);
  BubbleSort(array, arrayHeight);
  DisplayArray(array, arrayHeight);
  return 0;
}

Upvotes: 1

wookiekim

Reputation: 1176

I don't get what you are trying to do with your BubbleSort function.

But just to get a few things right :

if (array[i][0] > array[i][1 + 1])

this shouldn't work, your array was initialized as "int array [100][2]". Conventionally the highest number that should be in the second square bracket is 1. (1+1 =2, by the way)

array[1][i] = array[1][0+1];
swap = array[1][i];

C executes code in a sequential basis, so the array[1][i] is overwritten with array[1][0+1] even before the original value is saved in the 'swap' variable.

array[i][1 + 1];

This line of code does not seem do anything.

If you could tell whether you are trying to sort 'by element' or by 'line' (ie by each array in the 2D array), maybe we could help you approach the problem correctly.