01_Study►C

[16] 2차원 배열 정렬 (Sort 2D Array)

2차원 배열 정렬 (sortrows)

Matlab에서 제공하는 sortrows 함수를 C언어로 구현한 것

참고자료: 코딩도장 - 버블정렬

2차원 배열 정렬 기능 설명

2차원 배열을 받아서, 각 행의 맨 앞의 값의 크기를 기준으로 오름차순으로 정렬한다.

예를 들어보면

1
2
3
4
5
6
int a[4][3] = {
    {5,3,4,2},
    {4,5,6,3},
    {7,8,9,3},
    {2,4,4,5}
};

위와 같은 배열이 있을 때, 각 행의 맨 앞의 값과 행의 인덱스는 아래와 같다.

1
2
rowVal1 = {{5},{4},{7},{2}};
rowIdx1 = {{0},{1},{2},{3}};

위의 정보를 행의 값에 따라 오름차순으로 정렬하면 아래와 같다.

1
2
rowSortVal1 = {{2},{4},{5},{7}};
rowSortIdx1 = {{3},{1},{0},{2}};

정렬된 행에 맞게 행렬 자체를 정렬하면 아래와 같다.

1
2
3
4
5
6
int aSort[4][3] = {
    {2,4,4,5},
    {4,5,6,3},
    {5,3,4,2},
    {7,8,9,3}
};

따라서, 각 행의 첫 값을 비교하여 바꿀 인덱스를 확인한 다음, 배열에서 해당 행들의 인덱스를 바꿔주면 된다.

C언어로 작성한 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 코딩 도장에서 제공한 기본적인 bubble sort를 내가 필요한 방식으로 수정
// 입력으로 배열의 각 행 첫 열의 값과 인덱스를 담은 배열을 받아오고, 배열의 크기를 받아온다.
// 배열을 입력으로 받아오는 것이기 때문에, 따로 리턴 값을 지정해줄 필요는 없다.
void bubble_sort_modi(int arrVal[], int arrIdx[], int arrSize){ 
    // 임시 저장 변수 선언
    int temp, tempIdx;
    
    // 배열의 사이즈 만큼 반복
    for(int i = 0; i < arrSize; i++){ 
        // 배열의 사이즈 - 1 만큼 반복 (다음 값을 봐야해서)
        for(int j = 0; j < arrSize-1; j++){
            // 현재 값이 다음 값보다 크면
            if(arrVal[j] > arrVal[j+1]){
                // 값을 바꿔라
                temp = arrVal[j];
                arrVal[j] = arrVal[j+1];
                arrVal[j+1] = temp;
                
                // 그리고 해당하는 인덱스의 위치도 바꿔라
                tempIdx = arrIdx[j];
                arrIdx[j] = arrIdx[j+1];
                arrIdx[j+1] = tempIdx;
            }
        }
    }
}

// 입력으로 배열을 받아왔을 때 처리하는 방법과 배열까지 동적으로 선언해서 제공해주는 두 가지의 방법을 작성했다.
// 1. 입력으로 정렬할 배열의 주소를 받아올 때
// 2차원 배열의 경우, 고정된 값으로 선언했을 때에는 첫번째 입력에서 볼 수 있는 것처럼
// (자료형) arr[][열 사이즈]와 같이 선언해줘야한다.
// 입력으로 넣어주는 2차원 배열이 이중 포인터를 이용한 동적 할당으로 선언된 경우 두번째 입력에서 볼 수 있는 것처럼
// (자료형) **sortedArr 로 선언해주면 된다.
// 그리고 행과 열의 사이즈를 입력으로 넣어주면 된다.
void sort2DArr(int arr[][3], int **sortedArr, int row){
    // 0으로 초기화된 값, 인덱스를 위한 배열을 선언
    int *seq = calloc(row, sizeof(int));
    int *seq_idx = calloc(row, sizeof(int));
    
    // 받아온 배열에서 첫 행의 값 꺼내서 넣고, 행의 인덱스 채워넣기
    for (int i = 0; i < row; i++){
        seq[i] = arr[i][0];
        seq_idx[i] = i;
    }

    // 인덱스 정렬하기
    bubble_sort_modi(seq,seq_idx,row);

    // 정렬된 인덱스에 따라서 정렬한 값을 넣을 배열에 값을 복사해서 넣기
    for (int i = 0; i < row; i++){
        memcpy(sortedArr[i],arr[seq_idx[i]],sizeof(int)*3);
    }
    
    // 동적 할당한 배열 메모리 해제
    free(seq);
    free(seq_idx);
}

// 2. 정렬할 배열을 만들어서 리턴해줄 때
// 동적 할당으로 선언된 배열을 이중포인터로 리턴해주고, 행렬의 사이즈를 잘 알려주면 리턴으로 받아서 이용할 수 있다.
int** sort2DArr2(int arr[][3], int row){
    // 0으로 초기화된 값, 인덱스를 위한 배열을 선언
    int *seq = calloc(row, sizeof(int));
    int *seq_idx = calloc(row, sizeof(int));
    
    // 받아온 배열에서 첫 행의 값 꺼내서 넣고, 행의 인덱스 채워넣기
    int **sortedArr = calloc(row, sizeof(int *));
    for (int i = 0; i < row; i++){
        sortedArr[i] = calloc(3, sizeof(int));
    }

    // 받아온 배열에서 첫 행의 값 꺼내서 넣고, 행의 인덱스 채워넣기
    for (int i = 0; i < row; i++){
        seq[i] = arr[i][0];
        seq_idx[i] = i;
    }
	
    // 인덱스 정렬하기
    bubble_sort_modi(seq,seq_idx,row);

    // 정렬된 인덱스에 따라서 정렬한 값을 넣을 배열에 값을 복사해서 넣기
    for (int i = 0; i < row; i++){
        memcpy(sortedArr[i],arr[seq_idx[i]],sizeof(int)*3);
    }
    
    // 동적 할당한 배열 메모리 해제
    free(seq);
    free(seq_idx);

    return sortedArr;
}

테스트코드

테스트 해볼 방법만 살려두고 주석처리하고 실행해야함

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void bubble_sort_modi(int arrVal[], int arrIdx[], int arrSize);
void sort2DArr(int arr[][3], int **sortedArr, int row);
int** sort2DArr2(int arr[][3], int row);

int main(){

    int a[4][3] = {
        {3,2,2},
        {6,7,3},
        {4,5,6},
        {7,9,2}
    };

    // 1번 방법으로 이용할 경우
    int **sortedArr = calloc(4, sizeof(int *));
    for (int i = 0; i < 4; i++){
        sortedArr[i] = calloc(3, sizeof(int));
    }

    int seq[4];
    int seq_idx[4];
    for (int i = 0; i < 4; i++){
        seq[i] = a[i][0];
        seq_idx[i] = i;
    }

    printf("Base a\n");
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    printf("\n");

    sort2DArr(a, sortedArr, 4);

    printf("Sorted a\n");
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            printf("%d ",sortedArr[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    
    // 2번 방법으로 이용할 경우
    int **sortedArr;
    
    printf("Base a\n");
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    printf("\n");    
    
    sortedArr = sort2DArr2(a, 4);

    printf("Sorted a\n");
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            printf("%d ",sortedArr[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    

    // Free
    for(int i = 0; i < 4; i++){
        free(sortedArr[i]);
    }
    free(sortedArr);

    return 0;
}