选择排序模式

Question

我得到了以下代码：

#include <stdio.h>
#include <stdlib.h> 
int ordsel[4][4]={ {3,10,12,7},
                   {33,22,13,21},
                   {15,6,3,30},
                   {16,20,27,2}};
void imprimir()
{
    for (int k=0;k<4;k++)
    {
        for (int m=0;m<4;m++)
          printf("%dt",ordsel[k][m]);
      printf("n");
    }    
}
void ordenar()
{
    int cmenor, aux, ia, fmenor;
    for (int k = 0 ; k < 4 ; k++)
    {
        for (int m = 0 ; m < 4 ; m++)
        {
            fmenor=k;
            cmenor=m;
            ia=m;
            for (int i=k;i<4;i++)
            {
                for (int j=ia;j<4;j++)
                {
                   if (ordsel[i][j]<ordsel[fmenor][cmenor])
                   {
                        cmenor=j;
                        fmenor=i;
                   }
                } 
                ia = 0;
            }
         } 
         aux = ordsel[k][m];
         ordsel[k][m] = ordsel[fmenor][cmenor];
         ordsel[fmenor][cmenor] = aux;
      }
}
// Pregunta 3 Parcial III 1415-1
main()
{
printf("Programa que Ordenada una Matriz 4 x 4 por el Metodo Selectivon");
printf("n");
printf("n       MATRIZ INICIALn");
imprimir();
printf("n");
ordenar(); 
printf("      MATRIZ ORDENADAn");
imprimir();
printf("n");
system("pause");
}

SelectionSort

我很难找到这种排序方法应该如何工作的模式。如果有人能解释的话，我会很感激的。还有，有没有办法只用2个"for"循环来实现这一点？我认为主要的问题是，我无法用3个"for"循环来浏览矩阵。非常感谢。

Answer 1

典型的选择排序适用于一维（即1D）数组。您发布的代码只是使用相同的排序原则对2D数组（即矩阵）进行排序。

我将首先解释SelectionSort如何在1D数组上工作，然后扩展它来解释代码如何在2D数组上工作。

选择排序

选择排序通过在N元素数组A中的每个元素上循环来工作。在迭代i，其中0<=i<N、 它找到最小的元素在A[i]和A[N-1]之间（即，从索引i开始），并将该元素交换到A[i]中。

当i＝0时，该算法将最小元素交换到A[0]，当i＝1时，它将第二小元素交换到A+1]（因为最小元素已经在A[0]中，并且它正在从A[1]搜索到A[N-1]）。对i＝0到N-1执行此操作对A.进行排序

void selection_sort(int A[], int N)
{
    // Loop over each element.
    for (int i = 0; i < N; i++)
    {
        // At each iteration, put the next smallest element
        // into the correct position.
        // Find the smallest element from A[i] onwards
        int min_element_index = i;
        for (int j = i + 1; j < N; j++)
        {
            if (A[j] < A[min_element_index])
                min_element_index = j;
        }
        // Swap the smallest element between A[i] and A[N-1] into A[i]
        int tmp = A[i];
        A[i] = A[min_element_index];
        A[min_element_index] = tmp;
    }
}

您可以在这里看到该算法如何工作的可视化。

选择排序（2D大小写）

您的代码基本上执行以下操作：

1） 在矩阵中的每个元素ordsel[k][m]上循环：

  for (int k=0;k<4;k++)
        for (int m=0;m<4;m++)
        {

这对应于1D情况下的最外层环路（如上）。

2） 在上面的嵌套循环中，考虑元素ordsel[k][m]，它找到从ordsel[k][m]开始的最小元素：

    fmenor=k;  // Row index of the smallest element
    cmenor=m;  // Col index of the smallest element
    ia=m;      // Starting position of the col index
    for (int i=k;i<4;i++)
    {
        for (int j=ia;j<4;j++) // Start at col ia := m.
        {
            if (ordsel[i][j]<ordsel[fmenor][cmenor])
            {
                cmenor=j;
                fmenor=i;
            }
        }
        ia=0;  // Reset col index to first col when we move to next row

这对应于1D情况下的内环（如上）。

选择排序（2D），循环使用2

这里的技巧是将4 x 4 2D阵列视为16个元素的1D阵列。这将问题减少到上面的1D排序情况。但是，为了使事情正常工作，我们必须能够使用在数组的"1D"视图上循环的索引来计算这个2D数组中的行和列索引。

二维阵列ordsel可以看作：

int A[] = {3, 10, 12, 7, 33, 22, 13, 21, 15, 6, 3, 30, 16, 20, 27, 2}

现在A[0] == ordsel[0][0]，A[1] == ordsel[0][1]。。。

特别是A[5] == ordsel[1][0]，A[6] == ordsel[1][2]，A[7] == ordsel[1][3]。。。，A[15] == ordsel[3][3]。

注意，您可以根据A[j]的索引计算ordsel[k][m]的行和列索引，如下所示：

int k = j / NUM_COLS;  // Row index
int m = j % NUM_COLS;  // Col index

其中我们使用整数截断来向下取整CCD_ 10，并使用模算子CCD_。

int NUM_ROWS = 4;
int NUM_COLS = 4;
void selection_sort_2D()
{
    // Loop over 2D array as a 1D array
    for (int i = 0; i < NUM_ROWS * NUM_COLS; i++)
    {
        // The trick is to compute the row and col indices
        // from the index i.
        int cur_row = i / NUM_COLS;  // Index of current row
        int cur_col = i % NUM_COLS;  // and col
        int min_row_idx = cur_row;
        int min_col_idx = cur_col;
        for (int j = i; j < NUM_ROWS * NUM_COLS; j++)
        {
            // Similar to how we compute cur_row, cur_col
            int k = j / NUM_COLS;  // Row index
            int m = j % NUM_COLS;  // Col index
            if (ordsel[k][m] < ordsel[min_row_idx][min_col_idx])
            {
                min_row_idx = k;
                min_col_idx = m;
            }
        }
        // Swap
        int tmp = ordsel[cur_row][cur_col];
        ordsel[cur_row][cur_col] = ordsel[min_row_idx][min_col_idx];
        ordsel[min_row_idx][min_col_idx] = tmp;
    }
}