重构三维数组的排序算法

Question

我已经能够将该算法转换为对三维数组进行排序。它应该“通过”整个数组按列对 P 个二维矩阵进行排序，而不是单独对每一列进行排序。

整个程序代码不适合放在这里，所以我附上了一个小演示版本。向量的算法正在运行，没有错误。

有人可以帮助我吗？我真诚地不明白错误可能是什么。

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

clock_t Select8_3D(int*** A, int P, int M, int N) {
    int Li, Ri, Lj, Rj, imin, imax, jmin, jmax, temp;

    clock_t time_start, time_stop;
    time_start = clock();

    for (int k = 0; k < P; k++) {

        Lj = 0;
        Rj = N - 1;

        while (Lj < Rj) {

            jmin = Lj;
            jmax = Lj;

            Li = 0;
            Ri = M - 1;

            while (Li < M) {
                imin = Li;
                imax = Li;

                // search for minimum and maximum for the leftmost column 
                for (int i = Li + 1; i < M; i++) {
                    if (A[k][i][jmin] < A[k][imin][jmin]) {
                        imin = i;
                    }
                    else if (A[k][i][jmin] > A[k][imax][jmin]) {
                        imax = i;
                    }
                }

                // search for minimum and maximum for rectangular area
                for (int j = Lj + 1; j < Rj; j++) {
                    for (int i = 0; i < M; i++) {
                        if (A[k][i][j] < A[k][imin][jmin]) {
                            imin = i;
                            jmin = j;
                        }
                        else if (A[k][i][j] > A[k][imax][jmax]) {
                            imax = i;
                            jmax = j;
                        }
                    }
                }


                // search for minimum and maximum for the rightmost column 
                for (int i = 0; i <= Ri; i++) {
                    if (A[k][i][Rj] < A[k][imin][jmin]) {
                        imin = i;
                        jmin = Rj;
                    }
                    else if (A[k][i][Rj] > A[k][imax][jmax]) {
                        imax = i;
                        jmax = Rj;
                    }
                }

                // repositioning of elements
                if (imin != Li && jmin != Lj) {
                    temp = A[k][imin][jmin];
                    A[k][imin][jmin] = A[k][Li][Lj];
                    A[k][Li][Lj] = temp;
                }

                if (imax != Ri && jmax != Rj) {
                    if (imax == Li && jmax == Lj) {
                        temp = A[k][imin][jmin];
                        A[k][imin][jmin] = A[k][Ri][Rj];
                        A[k][Ri][Rj] = temp;
                    }
                    else {
                        temp = A[k][imax][jmax];
                        A[k][imax][jmax] = A[k][Ri][Rj];
                        A[k][Ri][Rj] = temp;
                    }
                }

                Li += 1;
                Ri -= 1;
            }
            Lj += 1;
            Rj -= 1;
        }

    }

    time_stop = clock();
    return (time_stop - time_start);
}


void printMatrix(int*** A, int P, int M, int N) {
    for (int k = 0; k < P; ++k) {
        printf("matrix %d:\n", k + 1);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                printf("%d ", A[k][i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
}

int main() {
    int P = 2; // number of “matrices”
    int M = 10; // number of lines
    int N = 10; // number of columns

    // Memory allocation and matrix initialization
    int*** A = (int***)malloc(P * sizeof(int**));
    for (int i = 0; i < P; ++i) {
        A[i] = (int**)malloc(M * sizeof(int*));
        for (int j = 0; j < M; ++j) {
            A[i][j] = (int*)malloc(N * sizeof(int));
            for (int k = 0; k < N; ++k) {
                A[i][j][k] = rand() % 100; // случайные значения
            }
        }
    }

    // Output of initial matrices
    printf("Matrix before sorting:\n");
    printMatrix(A, P, M, N);

    // Algorithm call
    clock_t execution_time = Select8_3D(A, P, M, N);


    // Output of sorted matrices
    printf("\nSorted matrix:\n");
    printMatrix(A, P, M, N);

    // Memory release
    for (int i = 0; i < P; ++i) {
        for (int j = 0; j < M; ++j) {
            free(A[i][j]);
        }
        free(A[i]);
    }
    free(A);

    return 0;
}

它在我的程序中的工作方式：

它应该如何工作：

矢量算法：

clock_t Select8_1D(int* A, int N, int P) {
    int L, R, imin, imax, tmp;

    clock_t time_start, time_stop;
    time_start = clock();

    L = 0; R = N - 1;

    while (L < R) {
        imin = L; imax = L;

        for (int i = L + 1; i < R + 1; i++) {
            if (A[i] < A[imin]) {
                imin = i;
            }
            else if (A[i] > A[imax]) {
                imax = i;
            }
        }

        if (imin != L) {
            tmp = A[imin];
            A[imin] = A[L];
            A[L] = tmp;
        }

        if (imax != R) {
            if (imax == L) {
                tmp = A[imin];
                A[imin] = A[R];
                A[R] = tmp;
            }
            else {
                tmp = A[imax];
                A[imax] = A[R];
                A[R] = tmp;
            }
        }

        L = L + 1;
        R = R - 1;
    }
    time_stop = clock();
    return (time_stop - time_start) * P;
}

它在我的程序中的工作方式：

如上所述，但我已经没有想法了。

Answer 1

对我来说，展示如何使用标准快速排序按任意规则对任意数据进行排序比弄清楚你认为你的逻辑如何工作更容易。

请注意，通过指针进行间接寻址对于速度来说并不是很好。但它确实让我更容易思考。

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

// All of our real work.
// Hiding data in context, and layout in compare/swap makes the algorithm easy.
void _qsort_any (int start, int end, void * context,
            int (*compare) (const void*, int, int),
            void (*swap) (const void*, int, int)) {
    int pivots_end, smalls_end, larges_start, mid_end;
    int last_compare;

    // Only need to sort if 2+ elements.
    if (1 < end - start) {
        if (3 < end - start) {
            // Use midpoint as pivot.
            (swap)(context, start, start + (end-start)/2);
        }

        // Start with 1 pivot, no smalls, lots of unsorted, nothing large.
        pivots_end = start + 1;
        smalls_end = pivots_end;
        larges_start = end;

        // Keep moving first unsorted into pivots, smalls, and larges.
        while (smalls_end < larges_start) {
            last_compare = (compare)(context, start, smalls_end);
            if (0 == last_compare) {
                // Add new pivot by swapping first small with this.
                (swap)(context, pivots_end, smalls_end);
                pivots_end++;
                smalls_end++;
            } else if (0 < last_compare) {
                // Found new large.
                larges_start--;
                (swap)(context, smalls_end, larges_start);
            } else {
                // Found new small.
                smalls_end++;
            }
        }

        // If we have smalls.
        if (pivots_end < smalls_end) {
            // We now have pivots, smalls, and larges. Move pivots to middle.
            mid_end = smalls_end;
            while (start < pivots_end) {
                pivots_end--;
                smalls_end--;
                (swap)(context, pivots_end, smalls_end);
            }
            // And now sort smalls.
            _qsort_any(start, smalls_end, context, compare, swap);
        }

        // Sort larges.
        if (1 < end - larges_start) {
            _qsort_any(larges_start, end, context, compare, swap);
        }
    }
}

// Where we enter the quicksort.
void qsort_any (int memb, void * context,
                int (*compare) (const void*, int, int),
                void (*swap) (const void*, int, int)) {
    _qsort_any(0, memb, context, compare, swap);
}

// The context we will use.
struct MatricesContext {
    int*** A;
    int P;
    int M;
    int N;
};

// Our comparison function.
int MatricesValueCompare(const void * raw_context, int i, int j) {
    int P, M, N, Mi, Ni, Mj, Nj, vi, vj;
    // Should always, always, always be the right type.
    const struct MatricesContext * context = (const struct MatricesContext *) raw_context;

    P = context->P;
    M = context->M;
    N = context->N;

    // Column first, then row, then matrix.
    Mi = i % M;
    i = (i - Mi) / M;
    Ni = i % N;
    i = (i - Ni) / N;
    vi = context->A[i][Mi][Ni];

    Mj = j % M;
    j = (j - Mj) / M;
    Nj = j % N;
    j = (j - Nj) / N;
    vj = context->A[j][Mj][Nj];

    if (vi < vj) {
        return 1;
    } else if (vj < vi) {
        return -1;
    } else {
        return 0;
    }
}

// Our swap function.
void MatricesValueSwap(const void * raw_context, int i, int j) {
    int P, M, N, Pi, Mi, Ni, Pj, Mj, Nj, tmp;
    const struct MatricesContext * context = (const struct MatricesContext *) raw_context;

    if (i != j) {
        P = context->P;
        M = context->M;
        N = context->N;

        // Column first, then row, then matrix.
        Mi = i % M;
        i = (i - Mi) / M;
        Ni = i % N;
        i = (i - Ni) / N;
        Pi = i;

        Mj = j % M;
        j = (j - Mj) / M;
        Nj = j % N;
        j = (j - Nj) / N;
        Pj = j;

        // Now we can swap them.
        tmp = context->A[Pi][Mi][Ni];
        context->A[Pi][Mi][Ni] = context->A[Pj][Mj][Nj];
        context->A[Pj][Mj][Nj] = tmp;
    }
}

// This was your Select8_3D.
clock_t Sort_3D(int*** A, int P, int M, int N) {
    struct MatricesContext context = {A, P, M, N};

    clock_t time_start, time_stop;
    time_start = clock();

    // And do the work.
    qsort_any(P*M*N, &context, MatricesValueCompare, MatricesValueSwap);

    time_stop = clock();
    return (time_stop - time_start);
}

void printMatrix(int*** A, int P, int M, int N) {
    for (int k = 0; k < P; ++k) {
        printf("matrix %d:\n", k + 1);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                printf("%3d ", A[k][i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
}



int main() {
    int P = 2; // number of “matrices”
    int M = 10; // number of lines
    int N = 10; // number of columns

    // Memory allocation and matrix initialization
    int*** A = (int***)malloc(P * sizeof(int**));
    for (int i = 0; i < P; ++i) {
        A[i] = (int**)malloc(M * sizeof(int*));
        for (int j = 0; j < M; ++j) {
            A[i][j] = (int*)malloc(N * sizeof(int));
            for (int k = 0; k < N; ++k) {
                A[i][j][k] = rand() % 100; // случайные значения
            }
        }
    }

    // Output of initial matrices
    printf("Matrix before sorting:\n");
    printMatrix(A, P, M, N);

    // Algorithm call
    clock_t execution_time = Sort_3D(A, P, M, N);


    // Output of sorted matrices
    printf("\nSorted matrix:\n");
    printMatrix(A, P, M, N);

    // Memory release
    for (int i = 0; i < P; ++i) {
        for (int j = 0; j < M; ++j) {
            free(A[i][j]);
        }
        free(A[i]);
    }
    free(A);

    return 0;
}