Сортировка столбцов (сравнительная лексикография) в матрице | C

Question

Я застреваю во второй части этой миссии. Я думаю, что у меня проблема с моим алгоритмом. Сообщите мне, пожалуйста, если мой код находится в хорошем направлении. Это мой mession Учитывая множество двумерных целых чисел. Массив состоит из 5 строк и 10 столбцов. Каждое значение в системе представляет собой случайное число между 0 и 20. Необходимо написать программу, которая выполняет сортировку значений массива следующим образом: сначала располагайте значения в каждом столбце, чтобы они сортировались в порядке возрастания (сверху вниз), тогда - так что сортировка столбцов вправо «подходит» путем сравнения пар значений в разных столбцах одной и той же строки («сравнительная лексикография»): сравнение двух значений в двух столбцах в первой строке, если они совпадают по сравнению со значениями во второй строке и т. д. и соответственно изменяют порядок столбцов (см. пример в третьей печати массива ниже). Чтобы отобразить массив перед сортировкой и после каждой из двух фаз чрезвычайной ситуации. например:

#include "stdio.h" 
#include "conio.h" 
#include "malloc.h" 
#include "stdlib.h" 

#define N 5 
#define M 10 
#define LOW 0 
#define HIGH 20 

void initRandomArray(int arr[N][M]); 
void printArray(int arr[N][M]); 
void SortInColumn(int arr[N][M],int m); 
void SortColumns(int arr[][M]); 
int compareColumns(int arr[][M], int col1, int col2); 
void swapColumns(int col1, int col2); 

int main() 
{ 
    int arr[N][M]; 
    int m; 
    m=M; 

    srand((unsigned)time(NULL)); //To clear the stack of Random Number 
    initRandomArray(arr); 
    printf("Before sorting:\n"); 
    printArray(arr); 
    printf("Sorting elements in each column:\n"); 
    SortInColumn(arr,M); 
    printf("Sorting columns:\n"); 
    SortColumns(arr); 

    system("pause"); 
    return 0; 
} 
void initRandomArray(int arr[N][M]) 
{ 

    int i,j; 
    for (i=0 ; i<N ; i++) 
     for (j=0 ; j<M ; j++) 
     { 
     arr[i][j]=LOW+rand()%(HIGH-LOW+1); 
     } 

} 
void printArray(int arr[N][M]) 
{ 
    int i,j; 
    for (i=0 ; i<N ; i++) 
    { 
     for (j=0 ; j<M ; j++) 
      printf("%d ", arr[i][j]); 
     printf("\n"); 
    } 
} 
void SortInColumn(int arr[][M],int m) 
{ 

    int i,j,k; 
    int temp; 

    for(k=0 ; k<m ; ++k) // loops around each columns 
    { 
     for(j=0; j<N-1; j++)// Loop for making sure we compare each column N-1 times since for each run we get one item in the right place 
     { 
       for(i=0; i < N-1 - j; i++) //loop do the adjacent comparison 
       { 
         if (arr[i][k]>arr[i+1][k]) // compare adjacent item 
         { 
           temp=arr[i][k]; 
           arr[i][k]=arr[i+1][k]; 
           arr[i+1][k]=temp; 
         } 
       } 
     } 
    } 

    printArray(arr); 
} 
void SortColumns(int arr[][M]) 
{ int row=0,cols=0,i=0,n=N; 
    int col1=arr[row][cols]; 
    int col2=arr[row][cols]; 
    compareColumns(arr,col1,col2); 

} 
int compareColumns(int arr[][M], int col1, int col2) 
{ 
    int row=0,cols=0,j; 
    for (row=0 ; row < N ; row ++); 
     { 
      for(cols=0 ; cols < M-1 ; cols++) 
      { 
       if(arr[row][cols]>arr[row][cols+1]) 
       { 
        for (j=0 ; j < M-1 ; j++) 
        { 
        col1=arr[row][cols]; 
        col2=arr[row][cols+1]; 
        swapColumns(col1 , col2); 
        } 

       } 
      } 
     } 
    printArray(arr); 
} 
void swapColumns(int col1, int col2) 
{ 
    int temp; 
    temp=col1; 
    col1=col2; 
    col2=temp; 

} 

Кстати является сложность функции compareColumns (п^3)?

Answer 1

Этот алгоритм слишком медленный, вы можете сделать лучше.

Вы можете использовать тот факт, что каждое число находится между 0 и 20 для сортировки столбцов в линейном времени. Для этого используйте вспомогательный массив 20x10, где array [i] [j] показывает, сколько раз значение i появляется в столбце j исходной матрицы. Для примера, первый столбец содержит значения 12, 18, 13, 17, 13, таким образом, мы имели бы:

массив [12] [0] = 1

массив [13] [0] = 2

массив [18] [0] = 1

массив [17] [0] = 1

Построение этого массива занимает O (N) времени для матрицы с п элементов (на самом деле, размер проблемы всегда один и тот же - 5 * 10 = 50)

Aftr, создавая этот массив, теперь у вас есть две возможности:

a) Перезапишите исходную матрицу с отсортированными значениями столбцов. Для этого вы должны войти в каждый столбец j в вспомогательном массиве и просмотреть значения. Например, для первого столбца первое ненулевое значение находится в массиве [12] [0], которое равно 1, поэтому вы пишете «12» в первом столбце исходного массива и увеличиваете количество строк, чтобы вы будете записывать следующее значение в правильное положение. Затем вы увидите, что массив [13] [0] равен 2, поэтому вы должны записать «13» дважды в исходной матрице. Вы продолжаете делать это для каждого столбца. Теперь у вас есть матрица с отсортированными столбцами, и вы можете применить свой метод для лексикографической сортировки между столбцами.

b) Поскольку вы хотите использовать лексикографический порядок между столбцами, вы можете видеть, что это эквивалентно сортировке столбцов по их накопленной сумме. Таким образом, вы можете сохранить еще один дополнительный массив из 10 элементов, где каждый элемент представляет собой структуру, содержащую накопленную сумму для массива [0..20] [j] и позицию j (обратите внимание, что для позиции i массив [i] [ j] * i - действительное значение для суммы). Сортировка этого 10-элементного массива выполняется очень быстро, и теперь вам нужно только перебрать этот отсортированный массив. Для каждой позиции в этом массиве вы используете исходный индекс j (хранящийся в структуре before) для индексации массива [0] [j], а затем перезаписываете исходную матрицу, используя метод, описанный в a). Это имеет то преимущество, что вам вообще не нужно писать какую-либо процедуру сортировки, вы можете использовать свою систему qsort.

Это решение хорошо масштабируется для приемлемых значений. Для матрицы с N элементами построение вспомогательного массива и массива накопленных сумм принимает O (N). Сортировка массива накопленных сумм занимает время, пропорциональное количеству столбцов, а перезапись исходного массива занимает время O (N).

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

Что касается кода, который вы отправили, он очень неполный, попробуйте предоставить нам что-то более полированное.