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

 

선택 정렬(selection sort)

 

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

 

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

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

 

 

 

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

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

c, h

닫기

#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가 같으면 탐색은 성공되고 키값이 발견된 배열의 인덱스를 출력한다.

 

c, h

닫기

#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)

 

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

: 속도가 빠르다

 

 

c, h

닫기

#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;
}

 

 

c, h

닫기

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];

c, h

닫기

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

 

 

 

 

 

 

2차원 배열의 초기화

 

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

c, h

닫기

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

 

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

c, h

닫기

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

 

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

c, h

닫기

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

 

 

 

 

 

 

행렬(matrix)

 

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

 

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

c, h

닫기

#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;
}