C언어 정렬과 행렬에 대해 학습하기

 

선택 정렬(selection sort)

 

: 정렬이 안된 숫자들 중에서 최소 값을 선택하여 배열의 첫번째 요소와 교환한다.

 

5, 3, 8, 1, 2, 7 이라는 숫자를 정렬해본다면?

-> 결과적으로 1, 2, 3, 5, 7, 8 으로 정렬이 되었다.

 

 

 

내부 for 루프로서, (i+1)번째 원소부터 배열의 마지막 원소 중에서 최소값을 찾는다.

현재의 최소값과 비교하여 더 작은 정수가 발견되면 그 정수가 들어있는 인덱스를 least에 저장한다.

#include <stdio.h>
#define SIZE 10

int main(void)
{
    int list[SIZE] = { 3, 2, 9, 7, 1 ; 4, 8, 0, 6, 5};
    int i, j, temp, least;
    
    for(i = 0 ; i < SIZE-1 ; i++)
    {
    	least = i;
        for(j = i + 1 ; j < SIZE ; j++)
            if(list[j] < list[least])
                least = j;

        temp = list[i];
        list[i] = list[least]
        list[least] = temp;
    }
}

 

 

 

- 변수의 값을 서로 교환할 때 주의할 점

 

// 다음과 같이 하면 안됨

score[i] = score[least];  // score[i]의 기존 값은 파괴된다!

score[least] = score[i];

 

// 올바른 방법

temp = list[i];

list[i] = list[least];

list[least] = temp;

 

 

 

 

 

 

순차 탐색 (search algorigm)

 

: 순차 탐색은 배열의 원소를 순서대로 하나씩 꺼내서 탐색키와 비교하여 원하는 값을 찾아가는 방법이다.

 

 

for 루프를 이용하여 list[i]와 key를 비교하는 연산을 배열의 크기만큼 반복한다.

만약 list[i]와 key가 같으면 탐색은 성공되고 키값이 발견된 배열의 인덱스를 출력한다.

 

#include <stdio.h>
#define SIZE 10

int main(void)
{
    int key, i;
    int list[SIZE] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    printf("탐색할 값을 입력하시오: ");
    scanf("%d", &key);
    
    for(i = 0 ; i < SIZE ; i++)
    	if(list[i] == key)
        
    printf("탐색 성공 인덱스= %d\n", i);
    printf("탐색 종료\n");
    
    return 0;
}

 

- 만약 7을 입력하면 탐색 성공 인덱스는 6이 된다.

 

 

 

 

 

 

 

이진 탐색(binary search)

 

: 정렬된 배열의 중앙에 위치한 원소와 비교 되풀이

: 속도가 빠르다

 

 

#include <stdio.h>
#define SIZE 16
int binary_search(int list[], int n, int key)

int main(void)
{
    int key;
    int grade[SIZE] = { 2, 6, 11, 13, 18, 20, 22, 27, 29, 30, 34, 38, 41, 42, 45, 47 };
    
    printf("탐색할 값을 입력하시오: ");
    scanf("%d", &key);
    
    printf("탐색 결과= %d\n", binary_search(grade, SIZE, key));
    
    return 0;
}

 

 

int binary_search(int list[], int n, int key)
{
    int low, high, middle;
    low = 0;
    high = n-1;
    while( low <= high ) {   //아직 숫자들이 남아있으면
    
    	printf("[%d %d]\n", low, high) // 하한과 상한을 출력한다
        middle = (low + high)/2;       // 중간 위치를 계산해서
        if( key == list[middle] )
        	return middle;              // 일치하면 탐색 성공
        else if( key > list[middle] )   // 중간 원소보다 크다면
        	low = middle + 1            // 새로운 값으로 low 설정
        else
        	high = middle - 1          // 새로운 값으로 high 설정
    }
    return - 1 ;
}

 

 

 

 

 

 

 

2차원 배열

 

int s[ROWS][COLS];

 int s[10];    //1차원 배열
 int s[3][10];    //2차원 배열
 int s[5][3][10];    //3차원 배열

 

 

 

 

 

 

2차원 배열의 초기화

 

- 행이 3개, 열이 5개라는 것을 컴퓨터에 알려줌

int s[3][5] = {
    {0, 1, 2, 3, 4},
    {10, 11, 12, 13, 14},
    {20, 21, 22, 23, 24}
};

 

- 열이 5개라는 것을 컴퓨터에 알려줌. 행이 몇개라는 걸 알려주지 않으면 컴퓨터가 알아서 행의 갯수를 캐치함

int s[][5] = {
    {0, 1, 2, 3, 4},
    {10, 11, 12, 13, 14},
    {20, 21, 22, 23, 24}
};

 

- 열이 5개라는 것을 컴퓨터에 알려줌. 마지막 숫자 뒤에 ,를 썼으므로 행은 3개가 생김

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

 

 

 

 

 

 

행렬(matrix)

 

: 자연과학에서 많은 문제를 해결하는데 사용한다.

 

- 2차원 배열을 함수로 전달하기

#include <stdio.h>

#define YEARS 3;
#define PRODUCTS 5;

int sum(int grade[][PRODUCTS]);

int main(void)
{
    int sales[YEARS][PRODUCTS] = {{1,2,3},{4,5,6},{7,8,9}};
    int total_sale;
    
    total_sale = sum(sales);
    printf("총 매출은 %d입니다.\n", total_sale);
    
    return 0;
}

int sum(int grade[][PRODUCTS])
{
    int y,p;
    int total = 0;
    
    for(y = 0 ; y < YEARS ; y++)
    	for(p = 0 ; p < PRODUCTS ; p++)
        	total += grade[y][p];
    
    return total;
}