c быстрая сортировка не работает

Question

Обучение C, и это упражнение.

Пользователю предлагается ввести размерность двумерного массива.Затем пользователь вводит значения этого массива.Наконец, программа должна иметь возможность сортировать каждую строку от самой низкой до самой большой и печатать результат.

Например,

input:

2 2
13 11
13 11

Должно напечатать:

11 13
11 13

Но моя программа печатает:

11 13
13 11

Если в моем коде я объявляю фиксированный размер массива, допустим матрицу [2] [2] и изменим весь код наэто измерение массива, программа прекрасно работает, но если я объявлю матрицу [MAX] [MAX], так как я не знаю, какой будет размер массива, это даст мне вывод, который я выложил выше.

Это потому, что я не использую указатели и распределение памяти?(Помните, что я все еще изучаю C).

Вот код, который я сделал:

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000

/*Print the final two-dimensional array*/
void print( int a[MAX][MAX], int b[])
{
    int i,j;
    for (i=0; i<b[0]; i++)
    {
        for (j=0; j<b[1]; j++)
        {
            printf("%d", a[i][j]);
            if (j < b[1]-1)
            {
                printf(" ");
            }
        }
        printf("\n");
    }
}

/* Sort my array */
int Qsort (int v[MAX][MAX], int li, int ls)
{
    int j;
    if (li < ls)
    {
        j = order(v,li, ls);
        Qsort (v, li, j-1);
        Qsort (v, j+1, ls);
    }
    return v[MAX][MAX];
}


int order(int x[], int li, int ls)
{
    int a, down, up, temp;
    a=x[li]; down=li; up=ls;
    while (down<up)
    {
        while (x[down]<=a && down<ls)
            down ++;
        while (x[up]>a)
            up --;
        if (down < up)
        {
            temp=x[down];
            x[down]=x[up];
            x[up]=temp;
        }
    }
    x[li]=x[up];
    x[up]= a;
    return up;
}

int main()
{
    int i,j,size,jump,jump2;
    int tam[2];
    int matrix[MAX][MAX];

    /*Define rows and columms*/
    i=0;
    while (i<2)
    {
        scanf("%d", &tam[i]);
        i++;
    }

    /*Fill the array with the numbers the user inputs*/
    for (i=0; i<tam[0]; i++)
    {
        for (j=0; j<tam[1]; j++)
        {
            scanf("%d", &matrix[i][j]);
        }
    }

    size = tam[1];
    jump = 1;
    jump2 = 0;

    for(i=0;i<tam[0];i++)
    {
        Qsort (matrix,jump2, jump*size-1);
        jump++;
        jump2 = jump2 + size;

    }

    print (matrix,tam);

    return 0;
}

Спасибо,

Favolas

Answer 1

#define MAX 1000
int matrix[MAX][MAX];

/*Fill the array with the numbers the user inputs*/
for (i=0; i<tam[0]; i++)
{
    for (j=0; j<tam[1]; j++)
    {
        scanf("%d", &matrix[i][j]);
    }
}

Учитывая это определение матрицы, ваши данные 2x2 заканчиваются на matrix[0][0], matrix[0][1], matrix[1][0] и matrix[1][1].Ничего удивительного там нет, но если рассматривать их как линейный список ячеек, заполненные ячейки:

base_address + 0
base_address + 1
base_address + 1000
base_address + 1001

(где, конечно, base_address = &matrix[0][0])

Там нет никакого способа для вашегокод для проверки двух последних ячеек в коде Qsort().

Здесь можно сделать несколько выводов.

• Узнайте, как напечатать хорошую диагностику.
• Печать данных при входе в рутину.(Если вы напечатаете массив при вводе в Qsort(), вы увидите, что у вас нет значений, с которыми вы должны работать. Это гарантирует, что вы точно знаете, как получить доступ к данным.)
• Выберите хорошие тестовые данные.Не повторяйте числа в ваших тестовых данных (например, 11, 12, 13, 14 - лучший набор входных данных).
• Понимание двухмерных массивов и их срезов.

Рассмотрим следующую диаграмму: matrix[4][7]:

      0   1   2   3   4   5   6
    +---+---+---+---+---+---+---+
 0  |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+
 1  |   | A | B | C |   |   |   |
    +---+---+---+---+---+---+---+
 2  |   | D | E | F |   |   |   |
    +---+---+---+---+---+---+---+
 3  |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+

Если вы хотите передать 6-буквенные ячейки функции как субматрицу, вам нужно передать адрес ячейки, содержащей A,вам нужно знать, что есть 3 столбца и 2 строки, и вам также нужно знать, что ширина всей матрицы равна 7. Без этого 7 вы не найдете ячейки D, E, F. Этоконечно, миниатюрная версия массива 1000x1000.

Ваша подматрица - это верхний левый угол всей матрицы, но применяются те же правила: вам нужен начальный адрес, ширина и высота элемента.-матрица и общая ширина всей матрицы для доступа к нужным элементам.

(Между прочим, когда я впервые начал это объяснение, матрица выше была 4x6, а не 4x7. Затем объяснили, что 6 должно бытьпрошло ваs не имеет отношения к продукту 2x3 - размер подматрицы - стал хитрым, поэтому я изменил свой «контрольный пример», чтобы избежать проблемы - именно так, как предложено в разделе «выбрать хорошие тестовые данные».)

---

Как исправить свой код?

Есть много способов, в зависимости от того, что вы хотите сделать.Трудный путь обходит жизненно важный параметр matrix-width.Более простые способы, вероятно, выделяют одномерный массив ячеек, а затем вычисляют подписки вручную.Тем не менее, я не уверен, что вы хотите, учитывая входные значения 14, 13, 12, 11 (обратный порядок), выходная матрица должна быть ... что?

12  11
14  13

Это означает, что вынужно поменять местами целые строки матрицы.

Answer 2

Похоже, вы сортируете первый ряд снова и снова.Вы хотите передать только один столбец в Qsort, поэтому он должен быть объявлен:

Qsort(int v[MAX], int li, int ls)

В вашей основной функции просто вызовите Qsort для каждой последующей строки:

Qsort(matrix[i], 0, size-1);