Home > OS >  My BubbleSort alghorithm doesn't seem to work and I don't know why
My BubbleSort alghorithm doesn't seem to work and I don't know why

Time:12-08

I'm trying to sort the specified column of the matrix in descending order , but my sorting algorithm doesn't seem to work and I don't know why.

void Prohod(float MAT[][4], int numberOfRows, int givenColumn) {
    float temp;
    for (int i = 0; i < numberOfRows; i  ) {
        if (MAT[i][givenColumn] < MAT[i   1][givenColumn]) {
            temp = MAT[i][givenColumn];
            MAT[i][givenColumn] = MAT[i   1][givenColumn];
            MAT[i   1][givenColumn] = temp;


        }
    }
    printf("Given column:%d\n",givenColumn);

}

I tried to apply the BubbleSort algorithm to batch the values , but for some reason it doesn't work.

CodePudding user response:

  1. You are going one element too far with MAT[i 1] in your for loop
  2. Your for loop does one full pass at the [column] array.
  3. So, at the end, the last element will be guaranteed to be in sort (i.e. largest).
  4. But, none of the others will.
  5. You have to have an outer for loop that repeats this N times (e.g. a "pass" counter).
  6. Or, until the [now] inner loop shows no swap.
  7. On each subsequent pass, the last element of the previous pass is guaranteed to be in the correct place, so we can decrease the number of elements we check by one

Here is the improved code:

void
Prohod(float MAT[][4], int numberOfRows, int givenColumn)
{
    float temp;

    for (int pass = 0; i < numberOfRows; pass  ) {
        int swap = 0;

        // after a single pass, the _last_ element is guaranteed to be correct
        // so we can look at one fewer element on each pass
        int curcount = (numberOfRows - 1) - pass;

        for (int i = 0; i < curcount; i  ) {
            if (MAT[i][givenColumn] < MAT[i   1][givenColumn]) {
                temp = MAT[i][givenColumn];
                MAT[i][givenColumn] = MAT[i   1][givenColumn];
                MAT[i   1][givenColumn] = temp;
                swap = 1;
            }
        }

        // early escape -- no swaps occurred -- all are in sort
        if (! swap)
            break;
    }

    printf("Given column:%d\n", givenColumn);
}

CodePudding user response:

I added another for loop for the following element like this:

for (int i = 0; i < numberOfRows; i  ) {
     for (int j = i   1; j < numberOfRows; j  ) {
                     if (MAT[i][givenColumn] < MAT[j][givenColumn]) {
                        temp = MAT[i][givenColumn];
                        MAT[i][givenColumn] = MAT[j][givenColumn];
                        MAT[j][givenColumn] = temp;
                     }
               }

}

And It works now.

  • Related